37
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 Ahmed, ESOP 2008 DOI:10.1007/978-3-540-78739-6_2
F-ing Modules by Andreas Rossberg, Claudio Russo, and Derek Dreyer, TLDI 2010
Cons should not cons its arguments ...
35
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 components. Moreover, such a set can be found in linear time. This (tight) result, proved by Lipton and Tarjan (improving on a previous result by Ungar) is a ...
30
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 titles results in unnecessarily long, uninformative and kludgy phrases that I find difficult to remember and look up.
There are papers like Pnueli's The Temporal ...
30
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 obstructions to its being in P. The best upper bound currently known on its time complexity seems to be a tower of $2$s of height $c^n$, where $c = 10^{10^{6}}$, ...
29
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.
27
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 complexity theory:
$\mathsf{NP}$ probably has no polynomial-size boolean circuits; proving lower bounds on circuit sizes is therefore a possible approach for ...
26
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–Cook, Schönhage–Strassen, Fürer, Harvey–Van Der Hoeven–Lecerf). The paper has not yet been peer-reviewed, but prior work of the authors on this problem makes it ...
25
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}$ is a finite field of size at least $3n$, then this algorithm can be used as a black box to compute the permanent of any matrix with high probability.
The ...
25
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 Problem (Mayr–Meyer and Mayr) and hence the computation of Gröbner bases. This was then extended to the computation of syzygies (Bayer and Stillman). ...
25
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 examples:
There is a surface which has only one side.
A curve may fill an entire square.
There are constant width curves other than a circle.
It is possible to ...
24
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$. Contained in $NP$. Generally believed to be $NP$-hard, but this is open. I believe it's not even known to be $AC0[2]$-hard. Indeed, recent work with Cody Murray (to ...
24
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 problem $\mathsf{BitSLP}$ which known to have this upper bound [ABD14]. On the other hand we do not even know if this problem is harder than computing the ...
23
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 Automata and Languages over a Unary Alphabet, CIAA 2014. doi:10.1007/978-3-319-08846-4_3
22
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 can we effectively/efficiently decide that an abstract $k$-dimensional simplicial complex can be embedded in $\mathbb{R}^d$. For $k=1$ and $d=2$ this is the graph ...
22
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.
20
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.
Here is an example on finite automata (equivalently, on directed graphs with labeled edges): deciding whether two automata accept the same language (have the ...
20
$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") that $SL = L$, where $S$ stands for "symmetric" and $SL$ is an intermediate class between $RL$ and $L$.
The idea is that you can think of a randomized ...
20
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-2018-Papers/pdfs/59f259.pdf
seem like good candidates
19
Some graph classes allow polynomial-time algorithms for problems that are NP-hard for the class of all graphs. For instance, for perfect graphs, one can find a largest independent set in polynomial time (thanks to vzn in a comment for jogging my memory). Via a product construction, this also allows a unified explanation for several apparently quite ...
19
Lattice-basis reduction (LLL algorithm). This the basis for efficient integer polynomial factorization and some efficient cryptanalytic algorithms like breaking of linear-congruential generators and low-degree RSA. In some sense you can view the Euclidean algorithm as a special case.
18
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 in $\mathsf{P}$ assuming that PIT can be black-box derandomized). Update 4/18/18: It was recently shown that for the variety $\overline{\mathsf{VP}}$ it is in $...
18
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)}$ can be rebalanced to have depth $O(\log^2 n)$ while only increasing the size by a polynomial factor. This is due to Valiant, Skyum, Berkowitz, and Rackoff. It ...
17
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 measure the quality or effectiveness of a test suite. The key idea is to inject faults into the program to be tested (i.e. to mutate the program), preferably ...
17
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 counter automata), MCAs are not allowed to test whether a counter is zero.
One of the algorithmic problems with a huge gap related to MSCs is the Reachability ...
17
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 number occurs more than half the time, but you don't know which one. How can you find the majority number if you can only remember two numbers at a time? The ...
17
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 are not proof by contradiction, and therefore, in particular, are not instances of the pigeon-hole principle. There are also proofs by contradiction where the ...
16
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 you need is to evaluate the circuit on one input. Then you'll obtain a nonzero value with good probability if the circuit does not represent the zero polynomial....
16
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 Kabanets show that PIT in P would imply some circuit lower bounds. So circuit lower bounds are the only reason (but a pretty good one) that we believe P = BPP.
16
(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 for topics in TCS which
are "hot" in theoretical CS right now
are useful for innovative applications in software/hardware in the next future
From the way you ...
16
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] Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Hao Huang. Manuscript, 2019. https://arxiv.org/abs/1907.00847
Only top voted, non community-wiki answers of a minimum length are eligible