Questions whose answers are a big list of items (books, theorems, software, ...)

learn more… | top users | synonyms

316
votes
5answers
64k views

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 ...
301
votes
68answers
94k 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 ...
292
votes
89answers
92k 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 ...
158
votes
58answers
47k views

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: ...
139
votes
34answers
51k 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 ...
110
votes
34answers
25k 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 ...
89
votes
16answers
10k 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 ...
85
votes
16answers
4k views

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 ...
82
votes
25answers
9k views

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? ...
74
votes
33answers
9k views

What are the recent TCS books whose drafts are available online?

Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online. For instance, the Approximation Algorithms entry of the above post cites ...
71
votes
3answers
7k 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 ...
59
votes
20answers
4k 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 ...
59
votes
12answers
5k 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 ...
57
votes
34answers
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 ...
54
votes
38answers
11k 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, ...
53
votes
17answers
2k views

Applications of TCS to classical mathematics?

We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.). What are some examples of when it has gone the other way around? Here ...
50
votes
3answers
4k 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 ...
49
votes
11answers
4k views

Common false beliefs in theoretical computer science

EDIT AT 10/12/08: I'll try to modified the question so it may interest more people to share their opinions. We NEED your contributions! This post is inspired by the one in MO: Examples of common ...
49
votes
12answers
3k views

Information Theory used to prove neat combinatorial statements?

What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ? Some examples I can think of are related to lower bounds for locally decodable ...
48
votes
16answers
3k 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, ...
47
votes
5answers
4k views

Overarching reasons why problems are in P or BPP

Recently, when talking to a physicist, I claimed that in my experience, when a problem that naively seems like it should take exponential time turns out nontrivially to be in P or BPP, an "overarching ...
46
votes
21answers
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 ...
45
votes
13answers
2k views

For which algorithms is there a large gap between the theoretical analysis and reality?

Two ways of analyzing the efficiency of an algorithm are to put an asymptotic upper bound on its runtime, and to run it and collect experimental data. I wonder if there are known cases where there ...
45
votes
10answers
2k views

Parameterized complexity from P to NP-hard and back again

I'm looking for examples of problems parametrized by a number $k \in \mathbb{N}$, where the problem's hardness is non-monotonic in $k$. Most problems (in my experience) have a single phase transition, ...
45
votes
8answers
8k views

Powerful Algorithms too complex to implement

What are some algorithms of legitimate utility that are simply too complex to implement? Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication ...
44
votes
13answers
5k views

Open problems on the frontiers of TCS

In the thread Major unsolved problems in theoretical computer science?, Iddo Tzameret made the following excellent comment: I think we should distinguish between major open problems that are ...
41
votes
15answers
3k views

Polynomial-time algorithms with huge exponent/constant

Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, ...
40
votes
5answers
819 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 ...
40
votes
2answers
4k views

What are the outstanding questions in purely functional data structures?

This question is inspired by another question about what's new in PFDS since the publication of Okasaki's book in 1998. I'll start with two questions I have: Is there a purely functional set data ...
37
votes
8answers
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 ...
37
votes
10answers
7k views

Uses of algebraic structures in theoretical computer science

I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science ...
37
votes
10answers
2k views

Kolmogorov complexity applications in computational complexity

Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 ...
36
votes
17answers
3k views

Conjectures implying Four Color Theorem

Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are ...
35
votes
11answers
1k views

Using error-correcting codes in theory

What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of ...
32
votes
4answers
1k views

Proofs that expose a deeper structure

The standard proof of the Chernoff bound (from the Randomized Algorithms textbook) uses the Markov inequality and moment generating functions, with a bit of a Taylor expansion thrown in. Nothing too ...
31
votes
13answers
2k views

Easy decision problem, hard search problem

Deciding whether a Nash equilibrium exists is easy (it always does); however, actually finding one is believed to be difficult (it is PPAD-Complete). What are some other examples of problems where ...
31
votes
17answers
2k views

What hierarchies and/or hierarchy theorems do you know?

I am currently writing a survey on hierarchy theorems on TCS. Searching for related papers I noticed that hierarchy is a fundamendal concept not only in TCS and mathematics, but in numerous sciences, ...
31
votes
2answers
2k views

Sum-of-square-roots-hard problems?

The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater ...
30
votes
1answer
1k views

Prerequisite for learning GCT

It seems that Geometric Complexity Theory requires much knowledge of pure maths such as algebraic geometry, representation theory. While I am a CS student and do NOT have classes of very abstract ...
29
votes
14answers
3k views

Book on Probability

While I have passed some courses on probability theory, both in the high school and the university, I have a hard time reading TCS papers when it comes to probability. It seems that the authors of ...
28
votes
9answers
1k views

Surprising Results in Complexity (Not on the Complexity Blog List)

What were the most surprising results in complexity? I think it would be useful to have a list of unexpected/surprising results. This includes both results that were surprising and came out of ...
27
votes
3answers
636 views

An Anthology of Complexity Assumptions

In the paper The Random Oracle Hypothesis Is False, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the random-oracle hypothesis. They argue ...
26
votes
19answers
5k views

Beautiful results in TCS

Recently, a friend of mine (working in TCS) mentioned in a conversation that "he wanted to see/know all (or as much as possible) of the beautiful results in TCS in his lifetime". This kind of made me ...
26
votes
15answers
2k views

Examples where insight from geometry was useful for solving something completely non-geometric

One of the nice things about having evolved in a universe with three spatial dimensions is that we have developed problem solving skills pertaining to objects in space. Thus, for example, we can think ...
25
votes
10answers
2k views

Probabilistic (randomized) algorithms before “modern” computer science appeared

Edit: I choice the answer with highest score by December 06, 2012. This is a soft question. The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms? In ...
25
votes
6answers
691 views

Well known classes of boolean formulas that require exponentially long resolution proofs

You might often find cutting plane methods, variable propagation, branch and bound, clause learning, intelligent backtracking or even handwoven human heuristics in SAT solvers. Yet for decades the ...
25
votes
5answers
742 views

Quantum proofs of classical theorems

I'm interested in examples of problems where a theorem which seemingly has nothing to do with quantum mechanics/information (e.g. states something about purely classical objects) can nevertheless be ...
25
votes
2answers
796 views

Complexity of Topological Properties.

I am a computer scientist taking a course on Topology (a sprinkling of point-set topology heavily flavored with continuum theory). I have become interested in decision problems testing a description ...
24
votes
5answers
2k views

Long-lasting errors in computer science

This is my first question on the cstheory stack, so don't be too rude if I'm violating etiquette somehow ) As we know, in mathematics even famous mathematicians, superstars and geniuses are doing ...
24
votes
2answers
683 views

Advice for attending my first TCS conference

I will be attending my first computer science conference and after reading the advice for how to improve conferences I noticed the several suggestions were about grad students attending their first ...