Questions tagged [soft-question]
A soft question is a question (possibly subjective) about the field of theoretical computer science as opposed to being a question in theoretical computer science.
404
questions
2
votes
0
answers
26
views
What are some practical applications of inductive-inductive types?
By "practical applications" I mean in usual programming/industry. I am particularly interested in cases where the inductive-inductive types cannot be easily replaced by inductive-recursive ...
- 121
12
votes
4
answers
1k
views
Where is the model theory in programming language theory?
I have a background in mathematical logic and am trying to learn some programming language theory. In the syntax of, say, first-order logic, one of the first distinctions you learn about is between ...
- 693
2
votes
0
answers
62
views
Open Quantum Analogs to Classical Problems
I am looking for interesting examples of complexity-theoretic and cryptographic problems where we have a significant amount of knowledge about the classical version of the problem, but we have no ...
- 121
2
votes
2
answers
221
views
Resources for hoodie design related to theoretical CS [closed]
I have to design a hoodie for my computer science batch, and I want it to be related to Theoretical computer science. I don't want to slap on some text with HTML-like angle brackets, but actually want ...
- 121
1
vote
1
answer
279
views
Are there 'poision-pill' research questions in TCS?
I intend to double major in CS/Math and go to grad school for TCS. I have some - unorthodox - research ideas I would like to pursue for grad school. At the very least, they are interdisciplinary (...
- 317
4
votes
1
answer
231
views
Does double majoring with math in undergrad help one grasp TCS topics more easier?
I'm a CS major. However, a lot of TCS topics seem to be in the realm of pure math. Should I add a math major to complement understanding and for a future career in TCS?
- 317
18
votes
2
answers
861
views
Why does it matter how difficult a proof is?
I am confused by how the objective worth of CS theory research is assessed.
In the last year, I had been working on formalizing some tasks from a different research field in cs theoretic terms, i.e. ...
- 191
23
votes
1
answer
907
views
FOCS virtual fee $600
I'm not sure this is on topic here, but probably can be best answered by this community, so I'm posting it as a soft-question.
Due to the pandemic, FOCS 2021 will be a virtual conference. Most ...
1
vote
1
answer
167
views
Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)
I'll preface this question by saying I have very little (zero!) knowledge of theoretical computer science, and this post is a genuine attempt to understand something, even if at an intuitive level, ...
7
votes
1
answer
423
views
Which universities in the U.S. are doing research in type theory?
The question is meant to be broad in that recommendations with mentions of the particular areas within type theory research are greatly appreciated. Also, the research need not be conducted in ...
- 173
1
vote
0
answers
62
views
Decision tree vs. pebble game lower bounds
This question concerns two types of lower bounds. In a pebbling lower bound, we are concerned with the complexity of constructing the output from the input. For example, if the only way we could ...
- 693
7
votes
3
answers
1k
views
Is it right to ask a TCS researcher about the real life application of the problem she/he is working on?
I have attended a decent number of TCS conferences. It is good that researchers solve difficult problems. However, I am often interested in the reason why a problem is interesting in the first place. ...
- 1,361
1
vote
0
answers
152
views
I think I may have discovered a new algorithm for a common problem. Now what?
I was trying to solve a common problem the other week and upon checking Stackoverflow there was a solution, but it just seemed like there should be a better way to do it. I thought about it for a ...
- 37
16
votes
6
answers
5k
views
Can theoretical computer science be applied in social sciences?
I'm very new to this field - technically not in it but want to be. I'm very early in my academic career (sophomore at a community college) but decided that I want to add a math major along with my ...
- 317
16
votes
3
answers
4k
views
Reviewing a paper and found a better solution
I was reviewing a paper of a double-blind conference (ML/AI-based conference). The authors improved the approximation bounds for some special instances of a problem.
To understand their proof better, ...
- 1,361
3
votes
2
answers
269
views
How to acknowledge answers of TCS in the paper?
I am researcher in a company from last 5 years.
I have received few answers on Theoretical Computer Science stack exchange regarding my current research work. They are not the main part of the paper ...
- 33
17
votes
1
answer
1k
views
Why most of the top TCS conferences are not double-blind?
I have found that the most notable TCS conferences like FOCS, STOC, SODA, and ICALP are single-blind. That is the authors do not know the identity of reviewers; however, the reviewers know the ...
- 1,361
4
votes
0
answers
106
views
Simple randomized priority queue matching the Fibonacci heap time bounds?
Since the Fibonacci heap was developed, many other priority queues have been invented with equivalent time bounds and a simpler design (e.g. hollow heaps, quake heaps, etc.).
Many classical worst-case ...
- 1,921
16
votes
4
answers
3k
views
Algorithms Careers
I’ve been writing software for a living for a number of years now. I have graduate background in mathematics and I am wondering whether knowledge of higher algorithms is utilized anywhere in industry. ...
- 301
-1
votes
1
answer
152
views
Do theoretical computer scientists work more with proving theorems, or work more with data?
As theoretical computer scientists, do you work more with proving theorems, or do you work more with data?
According to How to Criticize Computer Scientists, computer scientists can be divided into ...
- 109
4
votes
0
answers
170
views
The graph of problem reductions
A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
- 693
3
votes
2
answers
147
views
Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals [closed]
Looking for some lecture videos (introductory level) on logic, models of computation as well as computational complexity/ other theoretical computer science fundamentals
- 237
1
vote
1
answer
174
views
What math courses should I revisit to prepare for a CS Ph.D. (Reinforcement learning and Game Theory)?
I am planning to join a CS Ph.D. program in 6 months. My topics of research will be in the area of Reinforcement Learning and Game Theory. Even though I have a good grasp of these two topics’ ...
- 19
5
votes
1
answer
371
views
Advice on undergraduate research
I am a junior in college who is very interested in doing some sort of REU/research internship in theoretical computer science this summer, as I would like to get research experience before potentially ...
- 59
3
votes
1
answer
413
views
Which are the best universities for a DPhil/PhD in proof theory and automated reasoning?
I'm an undergraduate student studying computer science and I'm interested in doing a PhD after I graduate. I would like to do research in proof theory and automated reasoning, specifically in ...
- 33
1
vote
1
answer
151
views
Publishing by showing falsity of existing results [closed]
Is it valid to publish a minor result related to computer science complexity theory and classes that disproves and falsifies an existing result?
Would that be a valid and respectable endeavor?
- 12.6k
16
votes
2
answers
533
views
Publishing short and simple results
I have a manuscript that has been conference-rejected 3 times up to this point.
Just to clear things up, I am by no means a senior researcher but I am not a junior who cannot judge the strength of my ...
4
votes
1
answer
176
views
Formal theory about explaining algorithms
There is a lot of algorithms written in formal languages, but I have never seen any formal system which target is to explain or give a rationale behind an algorithm. It seems that when constructing ...
4
votes
1
answer
241
views
Should one study undergrad TCS materials before taking grad-level ones? (soft question)
I am a 1st year PhD student. I got a bachelor's degree in CS but I didn't start learning TCS systematically until this year.
This dumb question came to me when I opened an undergrad complexity lecture ...
- 203
32
votes
9
answers
4k
views
Any fundamental papers in TCS which were found to be incorrect/wrong later?
I am asking this question out of curiosity.
I recently encountered this well-known paper on (published in 2009):
the hardness_of_Euclidean_kmeans
The paper showed that the previous NP-hardness ...
- 1,361
16
votes
5
answers
2k
views
Why do TCS papers have author names in alphabetical order of their surnames?
I am currently doing a Ph.D. in Theoretical Computer Science, and any research paper I encountered so far has the author's names in alphabetical order of their surnames.
For example consider the most ...
- 1,361
3
votes
1
answer
260
views
Online TCS Seminars
I want to have a list of online seminars that holds now.
So far I know only about TCS+(https://sites.google.com/site/plustcs/) seminars.
I would like to ask if there are other TCS seminars.
8
votes
0
answers
149
views
How to succeed in remote TCS research as undergraduate
I am participating in a remote summer research program in theoretical computer science due to the current pandemic. I recognize that given the current situation, it may be harder to collaborate with ...
- 81
29
votes
1
answer
1k
views
Are there any public synchronous discussion forums (slack, discord, etc.) for TCS
I'm a 2nd year masters student studying theoretical CS (algorithms to be precise). I would like to know if there are any public synchronous discussion groups (slack, discord, etc.) for TCS. CSTheory ...
- 401
11
votes
4
answers
2k
views
How do conference proceedings add to academic prestige?
I come from mathematics and, for whatever reason, am trying to publish in theoretical computer science. I'm still trying to understand the role of conference proceedings, and I have two specific ...
- 221
6
votes
1
answer
372
views
Is the basis of parity functions the only orthonormal basis for Boolean functions?
Is there another orthonormal basis of functions for Boolean functions? Or, more specifically, besides the parity functions, is there another explicit function (which is common and has a name) that can ...
- 63
10
votes
4
answers
1k
views
What podcast should everybody listen to?
This list was inspired by the lists:
What are the popular science books that inspire TCS?
What Books Should Everyone Read?
What papers should everyone read?
What videos should everybody watch?
I don'...
- 563
3
votes
1
answer
97
views
What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper
I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that:
To the best of our knowledge, ...
- 203
1
vote
1
answer
222
views
Analytic Number theory in TCS [closed]
Are there any applications of analytic number theory in TCS?
- 31
5
votes
0
answers
140
views
Program size versus program running time
Short "naive" question:
Is it true that faster algorithms require longer programs ?
Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) ...
- 22.5k
5
votes
0
answers
202
views
What research is being done in classical complexity theory?
As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as ...
- 633
0
votes
1
answer
210
views
Diving straight into "research" versus studying broadly as an undergrad (soft question)
I'm nearing the end of my first year as an undergraduate and am very confident that I want to pursue a PhD in TCS. Fortunately because I quickly realized what I'm interested in and have a solid ...
- 113
13
votes
0
answers
416
views
What percentage of SODA papers are galactic algorithms?
Consider papers published in major theoretical CS conferences during the last 5 year, where the main result is that there exists an algorithm with some time or space complexity to solve some problem. ...
- 1,537
1
vote
0
answers
26
views
Sorting using comparisons that are not simple mappings of simple comparisons
The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
- 201
4
votes
0
answers
117
views
Status of the Junta Problem (soft question)
Does the learning theory community in general believe that juntas can be learned in polynomial time?
The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
- 187
13
votes
1
answer
304
views
Dialogue writing style & Yuri Gurevich's imaginary student: Quisani
Recently, while I was looking for more sources of crossing sequence in computational complexity theory, I came across the article "Is Randomness 'Native' to Computer Scientist?" written by M. Ferbus-...
- 233
4
votes
1
answer
284
views
What are the criteria for inviting conference papers (e.g. SODA) for special issue?
This is mostly for some immigration related document that I am trying to write and want to reference an online link which mentions that only a select few papers are invited for special issue for SODA ...
- 393
21
votes
1
answer
1k
views
Turing award papers
I was wondering if there are individual publications that have led their authors to win the Turing Prize or if the Turing Prize is the result of a lifetime's work and multiple publications and results....
- 684
3
votes
0
answers
117
views
Metrics for modelling convergence in the lambda-calculus
I wonder if there have been efforts to reconcile the measure approach to termination and Scott's domain theory or other topological models of computation. In other words, can we translate this measure ...
- 929
4
votes
0
answers
223
views
Advice for new grad student [closed]
I'm a first year PhD student in a CS department at what some would probably consider a mid-tier university. I've been reading from Vershynin's High-Dimensional Probability and been trying to learn ...
- 213