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.

Filter by
Sorted by
Tagged with
3
votes
1answer
215 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 ...
5
votes
3answers
457 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'...
12
votes
3answers
583 views

Is it beneficial to regularly read papers outside your field?

What do you think about regularly reading papers outside one's own field, even those which are not related to one's area? My intuition is that it can give a totally different perspective or technique ...
3
votes
0answers
109 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 ...
14
votes
1answer
397 views

Algebraic topology for termination proofs

I'm reading about various ways in which termination proofs of software verifiers are built: ad-hoc methods that detect recursions, term-rewriting, synthesis of lexicographic orderings... From the ad-...
1
vote
1answer
132 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?
16
votes
2answers
448 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 ...
94
votes
5answers
20k views

List of TCS conferences and workshops

I would like to ask for help in compiling a list of as many TCS-related conferences and workshops as possible. My main motivation for doing this is to plan possible blog coverage of more theory ...
70
votes
12answers
8k views

How important is knowing how to program for TCS?

Coming from a more mathematical background, I never really learned how to code. I am starting a PhD in TCS and many people were surprised by how little I knew about programming (and about computer in ...
245
votes
39answers
119k views

What Books Should Everyone Read?

[Timeline] This question has the same spirit of what papers should everyone read and what videos should everybody watch. It asks for remarkable books in different areas of theoretical computer ...
3
votes
1answer
145 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 ...
20
votes
1answer
2k views

How to write the introduction of a research paper?

Apologies if this is too broad a question for this forum, but I'm interested in specific tactics and tips that researchers (in TCS) use to write the introduction of a research paper.
9
votes
6answers
14k views

What is the best text of computation theory/theory of computation?

In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression. I borrowed that book and ...
4
votes
1answer
192 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 ...
31
votes
9answers
3k 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 ...
11
votes
3answers
816 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 ...
26
votes
7answers
3k views

Why would a TCS researcher need funding?

I was reading this. It says ... You won't find yourself as starving for funding like Pure Mathematics. (You'll still always find yourself starving for funding.)... Why do pure mathematicians need ...
4
votes
1answer
183 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.
39
votes
3answers
2k views

Is there a backup/replacement for the Complexity Zoo?

This is a non-technical question, but certainly relevant for the TCS community. If considered inappropriate, feel free to close. The Complexity Zoo webpage (http://qwiki.stanford.edu/index.php/...
80
votes
42answers
16k views

Funny TCS-related papers etc?

What is the funniest TCS-related published work you know? Please include only those that are intended to be funny. Works which are explicitly crafted to be intelligently humorous (rather than, say, ...
63
votes
10answers
7k views

Are there any open problems left about DFAs?

After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don'...
30
votes
2answers
835 views

Proof refutation: Amateur reviews of ambitious CoRR papers

I guess that I read too many ambitious CoRR papers. The problem is that those papers are not peer reviewed, but often sound interesting and pass basic plausibility checks. Or maybe they don't, and I ...
79
votes
9answers
9k views

Are research papers hard to read?

This question may not suit to here, but I couldn't find a better place to ask (it was closed in SO). I find research papers on computer science hard to understand. Of course the subjects are ...
7
votes
0answers
121 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 ...
28
votes
1answer
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 ...
24
votes
19answers
3k views

What tools do you use to give presentations?

I was wondering what tools that people in this field (theoretical computer science) use to create presentations. Since a great deal of computer science is not just writing papers but also giving ...
9
votes
4answers
1k 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 ...
5
votes
1answer
271 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 ...
145
votes
39answers
42k views

What videos should everybody watch?

Stanford University now has a Youtube channel, with free access to HD video of full courses on everything from dynamical systems to quantum entanglement. More conferences and workshops are ...
3
votes
1answer
81 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, ...
1
vote
1answer
157 views

Analytic Number theory in TCS [closed]

Are there any applications of analytic number theory in TCS?
5
votes
0answers
123 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) ...
5
votes
0answers
155 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 ...
0
votes
1answer
132 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 ...
13
votes
0answers
321 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. ...
467
votes
70answers
168k views

What papers should everyone read?

This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different. We all have favorite papers in our own respective ...
1
vote
0answers
18 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 ...
4
votes
0answers
77 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 ...
13
votes
1answer
209 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-...
38
votes
14answers
24k views

How practical is Automata Theory?

There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important ...
4
votes
1answer
166 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 ...
21
votes
1answer
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....
2
votes
0answers
134 views

Quantum advantage beyond the black-box model

Question Aaronson wrote in his thesis that “essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic ...
5
votes
1answer
231 views

Site with collection of exercises in TCS?

Is there a website with a large collection of exercises for theoretical computer science, sorted by topics? I know that many exercises can be found in different textbooks, I'm looking for an online ...
5
votes
2answers
1k views

What to do as a Theoretical computer science PhD student in a free time?

I am a mid-stage theoretical computer science student. Although I have a busy schedule, I still have a one or one a half hour in a day which I devote to reading and solving the question given Jeff ...
1
vote
2answers
150 views

Are patents good sources for academic research?

I'm a freshman Master's student in Computer Science and I need to write a paper for my Operating System class. While looking through research articles using google scholar I found that a lot results ...
4
votes
0answers
191 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 ...
7
votes
2answers
424 views

How to efficiently read the theoretical computer science research papers?

I am a computer science graduate student works in theory. The general advice is to go through the paper and then in the second or third round try to understand the detail. Read the abstract, ...
58
votes
15answers
2k views

Open access journals

With the advent of internet (and common sense) there is more and more demand for open-access research. Several researchers (including me) find it frustrating that published peer-reviewed research ...
2
votes
0answers
130 views

Book recommendation treewidth

I am searching for a good book (or survey paper) on treewidth. I would be delighted if the book/paper surveys multiple approaches to treewidth (eg: structural, algorithmic, `language-theoretic') and ...

1
2 3 4 5
8