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
480 votes
72 answers
178k 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 ...
377 votes
92 answers
112k views

Algorithms from the Book.

Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book. If ...
268 votes
39 answers
136k 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 ...
152 votes
39 answers
45k 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 ...
122 votes
13 answers
12k views

Advice on good research practices

After reading Daniel Apon's question, I started thinking that it might be useful (especially to junior researchers and graduate students like me) to ask a broader and more general question so we can ...
119 votes
15 answers
18k views

What Lecture Notes Should Everyone Read?

There has been several questions with the same scheme as this one: What papers should everyone read What books should everyone read What are the recent TCS books whose drafts are available online ...
102 votes
5 answers
22k 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 ...
94 votes
7 answers
30k views

What is the contribution of lambda calculus to the field of theory of computation?

I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with functions/...
user avatar
  • 5,165
91 votes
14 answers
19k views

What kind of mathematical background is needed for complexity theory?

I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are ...
user avatar
  • 3,741
83 votes
42 answers
17k 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, ...
83 votes
9 answers
10k 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 ...
user avatar
  • 949
82 votes
20 answers
10k views

Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

Please list examples where a theorem from mathematics which was not normally considered to apply in computer science was first used to prove a result in computer science. The best examples are those ...
71 votes
12 answers
9k 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 ...
user avatar
  • 1,645
69 votes
10 answers
8k 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'...
user avatar
66 votes
3 answers
8k views

How do I referee a paper?

Updated below We all know the critical importance of peer-review. It is the main form of quality control and feedback on research. However, to an early-stage researcher (like me), it can sometimes ...
66 votes
3 answers
7k views

Why does Fourier analysis of Boolean functions "work"?

Over the years I have gotten used to seeing many TCS theorems proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform is useful in virtually every subfield of TCS, including ...
user avatar
62 votes
8 answers
3k views

What is the complexity class most closely associated with what the human mind can accomplish quickly?

This question is something I've wondered about for a while. When people describe the P vs. NP problem, they often compare the class NP to creativity. They note that composing a Mozart-quality ...
user avatar
  • 5,080
61 votes
33 answers
4k views

Small steps for better TCS conferences?

Often, when we take part in TCS conferences, we notice some little details that we wish the conference organisers would have taken care of. And when we are organising conferences, we have already ...
60 votes
7 answers
3k views

How to shoot down your proofs

What are general guidelines for checking your proofs? I believe this is important for graduate students like me. I already know what we need to do to prove something, but you always have to check ...
59 votes
6 answers
9k views

How to get a job

I'm new to the site. On mathoverflow this would be community wiki, but I don't see how to set that here. Not a research question, but hopefully of interest to professional theoretical computer ...
58 votes
15 answers
3k 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 ...
user avatar
58 votes
5 answers
31k views

What CS blogs should everyone read?

Many top notch computer science researchers and research groups) maintain active blogs that keep us updated on the latest research in the authors' fields of interest. In most cases, blog posts are ...
57 votes
16 answers
4k views

What tools do you use to write papers?

What tools do you use to write papers? From the little experience that I have, theoreticians spend a large amount of time writing and refining papers, besides actually being creative. That is, ...
57 votes
9 answers
24k views

Explain P = NP problem to 10 year old

It is my first question on this site. I am taking a master's course on theory of computation. How you would explain P = NP problem to a 10 year old child and why it has such a monetary reward on it? ...
55 votes
18 answers
14k views

Most memorable CS paper titles

Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS. It is quite clear that most of us might be attracted to read (or at least glance at) a ...
53 votes
21 answers
4k views

Dinner-table description of theoretical computer science?

I'm often asked what a theoretical computer scientist does. It would be great to have some nice responses to this question. I tend to fall back to technical jargon and people's eyes usually glaze ...
52 votes
11 answers
4k views

If you could rename dynamic programming...

If you could rename dynamic programming, what would you call it?
50 votes
3 answers
7k views

How to find interesting research problems

Despite several years of classes, I'm still at a loss when it comes to choosing a research topic. I've been looking over papers from different areas and spoken with professors, and I'm beginning to ...
user avatar
  • 653
49 votes
6 answers
3k views

Good examples for how to write well in TCS

I was editing a student manuscript. The student remarked that it would be nice to see examples of quality writing in published work, and I realized that I couldn't really come up with good examples ...
48 votes
8 answers
5k views

Are there non-constructive algorithm existence proofs?

I remember I might have encountered references to problems that have been proven to be solvable with a particular complexity, but with no known algorithm to actually reach this complexity. I struggle ...
user avatar
  • 8,651
47 votes
6 answers
2k views

Ways for a mathematician to stay informed of current research in complexity theory

Complexity theory is a strong secondary interest of mine but it's not my primary research interest, so there is no hope for me to attend all the conferences, read all the blogs, and ensure that the "...
user avatar
  • 7,103
46 votes
17 answers
4k views

Physics results in TCS?

It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are Quantum computation ...
user avatar
45 votes
5 answers
2k views

Historical reasons for adoption of Turing Machine as primary model of computation.

It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more widely-...
user avatar
  • 553
45 votes
5 answers
1k views

Casual tours around proofs

Today Ryan Williams posted an article on the arXiv (previously appeared in SIGACT News) containing a less technical version of his recent ACC lower bound technique. My question is not about the ...
user avatar
44 votes
10 answers
16k views

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
user avatar
  • 607
42 votes
8 answers
3k views

Rigour leading to insight

On MathOverflow, Timothy Gowers asked a question titled "Demonstrating that rigour is important". Most of the discussion there was about cases showing the importance of proof, which people on ...
user avatar
42 votes
8 answers
4k views

What do you do when you cannot make progress on the problem you have been working on?

I am a 2nd year graduate student in theory. I have been working on a problem for the last year (in graph theory/algorithms). Until yesterday I thought I am doing well (I was extending a theorem from a ...
user avatar
  • 1,984
41 votes
4 answers
5k views

Single author papers against my advisor's will?

I am a third year PhD student in an area of theoretical CS that would like advice for a difficult situation with my advisor. My advisor is not involved in my research projects at all. In particular, ...
user avatar
41 votes
6 answers
3k views

Which model of computation is "the best"?

In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
user avatar
41 votes
5 answers
5k views

What would you advise someone who wants to do research as a hobby?

I love doing TCS in my spare time. Lately I have been trying to do some research as a hobby. I'm looking for some extra input from people who do this full-time: Do you think it is possible to do this ...
user avatar
40 votes
14 answers
26k 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 ...
user avatar
40 votes
8 answers
18k views

Why go to theoretical computer science/research?

I'm currently starting on the university [computer science] and there we have lot of opportunities to begin with researching. Before finding this website, I had no intention to go on this way [I ...
40 votes
3 answers
1k views

Selecting papers to read

DISCLAIMER: This is an open ended question and stackexchange puritans would probably feel an extraordinary urge to vote it down to oblivion. However, I cannot think of any other forum more appropriate ...
user avatar
  • 565
40 votes
1 answer
2k views

Importance of single author papers?

I'm a fourth year PhD student in theoretical computer science. I'd like to stay in academia, so I'm thinking about how best to advance my career. Obviously the best way to do that is write lots of ...
user avatar
  • 329
39 votes
7 answers
9k views

How do I get started in theoretical CS ?

I'm a freshmen studying computer science and I already know that I want to go into academia with focus of theoretical comp sci. I already read some of papers referenced in this question and this ...
39 votes
3 answers
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/...
user avatar
38 votes
13 answers
3k views

Inspirational talk for final year high school pupils

I am often asked by my department to give talks to final year high school pupils about the more mathematical elements of computer science. I do my best to pick topics from TCS which might inspire ...
38 votes
3 answers
6k views

Extended Church-Turing Thesis

One of the most discussed questions on the site has been What it Would Mean to Disprove the Church-Turing Thesis. This is partly because Dershowitz and Gurevich published a proof of the Church-Turing ...
user avatar
37 votes
7 answers
3k views

What is the oldest open problem in TCS?

This problem is inspired by this MO question, which I thought was very interesting. What is the oldest open problem in TCS? Clearly this question needs some clarification. First, what is TCS? ...
user avatar
37 votes
5 answers
2k views

When should you say what you know?

What should you do when you see a question raised in public, say here on stack-exchange, that you know the answer to, because you are looking into as part of current research project? For example, I ...

1
2 3 4 5
9