Most Popular
1500 questions
623
votes
6 answers
What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:
IntMap (also invented by Okasaki in 1998, but not present in that…
jkff
- 8,941
- 3
- 23
- 33
490
votes
72 answers
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 areas of theory. Every once in a while, one finds a…
Ryan Williams
- 27,465
- 7
- 115
- 164
381
votes
92 answers
Algorithms from the Book
Paul Erdős 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 God had a similar book for algorithms, what…
Aryabhata
- 1,855
- 3
- 21
- 29
328
votes
29 answers
Core algorithms deployed
To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of examples where core algorithms have been deployed in…
Manu
- 7,659
- 3
- 37
- 42
272
votes
39 answers
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 science.
The books can be math-oriented, yet you may…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
261
votes
11 answers
What is the enlightenment I'm supposed to attain after studying finite automata?
I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we study deterministic and non-deterministic finite…
PhD
- 5,305
- 5
- 25
- 40
234
votes
60 answers
Major unsolved problems in theoretical computer science?
Wikipedia only lists two problems under "unsolved problems in computer science":
P = NP?
The existence of one-way functions
What are other major problems that should be added to this list?
Rules:
Only one problem per answer
Provide a brief…
Shane
- 2,233
- 3
- 26
- 25
232
votes
11 answers
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct?
Also on topic: where else (on the internet) is its correctness being discussed?
Note: the focus of this question text has changed over time. See question comments for…
Warren Schudy
- 1,689
- 3
- 9
- 9
157
votes
39 answers
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 videotaping their talks. What are videos online that you…
Aaron Sterling
- 6,994
- 6
- 42
- 74
145
votes
2 answers
Super Mario Galaxy problem
Suppose Mario is walking on the surface of a planet. If he starts walking from a known location, in a fixed direction, for a predetermined distance, how quickly can we determine where he will stop?
More formally, suppose we are given a convex…
Jeffε
- 23,129
- 10
- 96
- 163
141
votes
30 answers
Problems Between P and NPC
Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? Artificial examples coming directly from the proof of…
Lev Reyzin
- 11,968
- 13
- 63
- 103
129
votes
11 answers
How hard is unshuffling a string?
A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPP and SSISI. Let me call a string square if it is a shuffle of two…
Jeffε
- 23,129
- 10
- 96
- 163
124
votes
13 answers
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 learn from the experience of more senior…
Kaveh
- 21,577
- 8
- 82
- 183
123
votes
18 answers
Examples of the price of abstraction?
Theoretical computer science has provided some examples of "the price of abstraction." The two most prominent are for Gaussian elimination and sorting. Namely:
It is known that Gaussian elimination is optimal for, say, computing the determinant…
Joshua Grochow
- 37,260
- 4
- 129
- 228
123
votes
15 answers
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
what videos should everybody watch
I was reluctant…
Sadeq Dousti
- 16,479
- 9
- 69
- 152