37
votes
Most memorable CS paper titles
I did a survey on Twitter about this a while back, results here. A few of my favorites:
Parametric Polymorphism through Runtime Sealing, or, Theorems for Low, Low Prices! by
Jacob Matthews and Amal ...
Community wiki
35
votes
Lipton's most influential results
The Planar Separator Theorem states that in any planar $n$-vertex graph $G$ there exists a set of $O(\sqrt{n})$ vertices whose removal leaves the graph disconnected into at least two roughly balanced ...
Community wiki
30
votes
Most memorable CS paper titles
I used to like quirky titles when I started out in computer science but got bored eventually. Some authors manage to write titles that are clever, memorable and relevant but most attempts at funny ...
Community wiki
30
votes
Problems with big open complexity gaps
The Knot Equivalence Problem.
Given two knots drawn in the plane, are they topologically the same? This problem is known to be decidable, and there do not seem to be any computational complexity ...
29
votes
Most important new papers in computational complexity
The recent paper of László Babai showing that Graph Isomorphism is in Quasi-P is already a classic.
Here is a more accessible exposition of the result published in the ICM 2018 proceedings.
Community wiki
27
votes
Lipton's most influential results
Karp-Lipton Theorem states that $\mathsf{NP}$ cannot have polynomial-size boolean circuits unless the Polynomial hierarchy collapses to its second level.
Two implications of this theorem for ...
26
votes
Most important new papers in computational complexity
In a recent preprint, Harvey and Van Der Hoeven show how to compute Integer multiplication in time $O(n \log n)$ on a multi-tape Turing machine, culminating some 60 years of research (Karatsuba, Toom–...
Community wiki
25
votes
Lipton's most influential results
Random Self-Reducibility of the Permanent. Lipton showed that if there exist an algorithm that correctly computes the permanent of $1-1/(3n)$ fraction of all $\mathbb{F}^{n\times n}$, where $\mathbb{F}...
Community wiki
25
votes
Accepted
EXPSPACE-complete problems
Extending the example pointed out by Emil Jerabek in the comments, $\mathsf{EXPSPACE}$-complete problems arise naturally all over algebraic geometry. This started (I think) with the Ideal Membership ...
25
votes
Counterintuitive results for undergraduates
For a general audience you have to stick to things that they can see. As soon as you start theorizing they'll start up their mobile phones.
Here are some ideas which could be worked out to complete ...
24
votes
Problems with big open complexity gaps
Here's a version of the minimum circuit size problem (MCSP): given the $2^n$ bit truth table of a Boolean function, does it have a circuit of size at most $2^{n/2}$?
Known to be not in $AC0$. ...
24
votes
Problems with big open complexity gaps
The complexity of computing a bit (specified in binary) of an irrational algebraic number (such as $\sqrt{2}$) has the best known upper bound of $\mathsf{P^{{{PP}^{PP}}^{PP}}}$ via a reduction to the ...
23
votes
Accepted
Complexity zoo for unary languages
There is no Zoo-style reference yet, but a recent automata-theoretic survey of Giovanni Pighizzini has been useful to me, especially the slides from his talk.
Giovanni Pighizzini, Investigations on ...
22
votes
Problems with big open complexity gaps
Another natural topological problem, similar in spirit to Peter Shor's answer, is embeddability of 2-dimensional abstract simplicial complexes in $\mathbb{R}^3$. In general it's natural to ask when ...
22
votes
Most important new papers in computational complexity
Importance is in the eyes of the beholder. However, I would say that the Feder–Vardi CSP dichotomy conjecture, proved independently by A. Bulatov and D. Zhuk, is a seminal result.
Community wiki
20
votes
EXPSPACE-complete problems
Many problems that are PSPACE-complete become EXPSPACE-complete when the input is given "succinctly", i.e., via some encoding that lets you describe inputs that would normally be of exponential size.
...
20
votes
Examples of successful derandomization from BPP to P
$SL = L$.
$RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace")...
20
votes
Most important new papers in computational complexity
Non-Uniform ACC Circuit Lower Bounds by Ryan Williams:
https://people.csail.mit.edu/rrw/acc-lbs.pdf
and Classical Verification of Quantum Computations by Urmila Mahadev:
http://ieee-focs.org/FOCS-...
Community wiki
18
votes
Accepted
List of number theoretic or algebraic problems in various complexity classes
Algebraic geometry
Noether's Normalization Lemma (NNL) for explicit varieties is currently only known to be in $\mathsf{EXPSPACE}$ (like general NNL), but is conjectured to be in $\mathsf{P}$ (and is ...
18
votes
Examples of collapsing hierarchies
The analogue of the $\mathsf{NC}$ hierarchy for algebraic circuits is known to collapse to the second level. That is, algebraic circuits of size $n^{O(1)}$ computing a polynomial of degree $n^{O(1)}$ ...
17
votes
Lipton's most influential results
I'm not 100% sure if the explanation below is historically accurate. If it isn't, please feel free to edit or remove.
Mutation testing was invented by Lipton. Mutation testing can be seen as a way to ...
Community wiki
17
votes
Problems with big open complexity gaps
Multicounter automata (MCAs) are finite automata equipped with counters that can be incremented and decremented within one step but only take integers >=0 as numbers. Unlike Minsky machines (aka ...
17
votes
Counterintuitive results for undergraduates
One idea is something simple from streaming algorithms. Probably the best candidate is the majority algorithm. Say you see a stream of numbers $s_1, \ldots, s_n$, one after the other, and you know one ...
17
votes
Possible to do Complexity theory with only counting and Pigeonhole
If you are looking for non-pigeon-hole type arguments, then there is good news: they exist! The pigeon-hole principle is a certain template for proof by contradiction. There are concepts in TCS which ...
16
votes
Lipton's most influential results
Schwartz - Zippel - DeMillo-Lipton Lemma is a fundamental tool in arithmetic complexity: It basically states that if you want to know whether an arithmetic circuit represents the zero polynomial, all ...
Community wiki
16
votes
Examples of successful derandomization from BPP to P
There is basically only one interesting problem in BPP not known to be in P: Polynomial Identity Testing, given an algebraic circuit is the polynomial it generates identically zero. Impagliazzo and ...
16
votes
Accepted
What CS theories are absolutely paramount for someone new to TCS to understand?
(Disclaimer: this answer has a focus on programming languages theory, which is only one of the many disciplines under the TCS umbrella.
Apologies for the length.)
A small digression
You are asking ...
16
votes
Most important new papers in computational complexity
This new paper by Hao Huang [1] (not yet peer-reviewed, as far as I know) probably qualifies... it proves the sensitivity conjecture of Nisan and Szegedy, which has been open for ~30 years.
[1] ...
Community wiki
15
votes
Problems that are hard to prove in $\mathcal{P}$
The famous primality testing problem, shown to be in P in the 2000 paper PRIMES is in P.
Community wiki
15
votes
Languages that we cannot (dis)prove to be Context-Free
Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${\bf t} = 0110100110010110 \cdots $. To give some context, Jean Berstel proved ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
big-list × 166reference-request × 47
soft-question × 45
cc.complexity-theory × 34
ds.algorithms × 22
big-picture × 15
open-problem × 9
graph-theory × 8
co.combinatorics × 8
complexity-classes × 8
ds.data-structures × 8
books × 7
np-hardness × 6
quantum-computing × 6
proofs × 6
survey × 6
graph-algorithms × 5
reductions × 5
research-practice × 5
teaching × 5
lo.logic × 4
it.information-theory × 4
conferences × 4
time-complexity × 3
sat × 3