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.
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–...
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 ...
  • 27.6k
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 ...
  • 2,299
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.
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")...
  • 7,185
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-...
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

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 ...
  • 1,417
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

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 ...
  • 668
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] ...
15 votes

Major unsolved problems in distributed systems?

The distributed time complexity of numerous graph problems is still an open question. In general, distributed graph algorithms is an area in which we would expect to have (at least asymptotically) ...
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 ...
15 votes

Most important new papers in computational complexity

Subhash Khot, Dor Minzer and Muli Safra's 2018 work "Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion" has gotten us "half way" to the Unique Games Conjecture and is methodologically ...
14 votes

Most important new papers in computational complexity

"On the possibility of faster SAT algorithms" by Pătraşcu & Williams (SODA 2010). It gives tight relations between the complexity of solving CNF-SAT and the complexity of some polynomial problems (...
13 votes

Major unsolved problems in theoretical computer science?

Summary Table for Answers Open Problems Matrix Multiplication: Can multiplication of $n$ by $n$ matrices be done in $O(n^2)$ operations? Graph Isomorphism: Is Graph Isomorphism in P? Factoring: Is ...
13 votes

Counterintuitive results for undergraduates

The volume of a unit sphere of dimension $n$ first grows as $n$ grows ($2,\pi,4\pi/3,\dots$) but starts decreasing for $n=6$ and eventually converges to $0$ as $n\to\infty$.
  • 8,223
13 votes

Examples of successful derandomization from BPP to P

Besides polynomial identity testing, one other very important problem known to be in BPP but not in P is approximating the permanent of a non-negative matrix or even the number of perfect matchings in ...
12 votes

Problems with big open complexity gaps

$\mathsf{QMA}(2)$ (Quantum Merlin-Arthur with two unentangled provers): certainly $\mathsf{QMA}$-hard, but only known to be in $\mathsf{NEXP}$.
12 votes

Problems not known to be PSPACE-complete

Retrograde Chess. It is $PSPACE$-complete if you are allowed to have arbitrarily many kings and none of them can be in check at any time. If no (or only one per player) kings are allowed, it is known ...
12 votes

Complexity zoo for unary languages

One interesting question about complexity classes over a unary alphabet that is not in the above references is the strength of Valiant's class #P1, the class of counting problems over a unary alphabet ...
12 votes

Languages that we cannot (dis)prove to be Context-Free

How about the language $L_{TP}$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is ...
  • 10.2k

Only top scored, non community-wiki answers of a minimum length are eligible