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–...
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
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
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)}$ ...
- 903
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 ...
- 2,194
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 ...
- 688
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
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 ...
- 6,985
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
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.6k
12
votes
Obscure characterizations of the regular languages
I know it is frowned upon to promote one's own results, but it turns out that I wrote an article precisely on this topic. So let me add a few characterizations of regular languages not already ...
- 5,111
11
votes
Parameterized complexity from P to NP-hard and back again
This is an interesting (and surprising) example for a P $\to$ NP-hard $\to$ P $\to$ NP-hard $\to \cdots$ phase transition:
Deciding if a complete graph on $n$ vertices, in which each vertex has a ...
- 2,487
11
votes
Most important new papers in computational complexity
It’s one year beyond the 10-year limit, but “Delegating Computation: Interactive Proofs for Muggles” by Goldwasser, Kalai, and Rothblum has been a hugely influential paper. The main result is that ...
11
votes
What are examples of recent relatively simple 'toolbox algorithms'?
More attention has been given recently to sketching and streaming data structures, such as Bloom Filters, Count Min Sketch, HyperLogLog.
Related, and also gaining popularity, are linear-algebra-based ...
- 7,788
11
votes
What are examples of recent relatively simple 'toolbox algorithms'?
Suffix arrays, with linear time construction. There are various algorithms, they're relatively approachable, and applications are plenty. SA-IS dates to 2009.
Soft heaps, they're not that complex, and ...
- 211
10
votes
Examples of collapsing hierarchies
The AM hierarchy (constant-round interactive proofs) collapses to AM (Babai-Moran '88), but we don't yet know whether NP=MA=AM.
- 38.5k
10
votes
What are examples of recent relatively simple 'toolbox algorithms'?
Quantum algorithms would fit this, if one has time to introduce the model -- specifically, Grover search and possibly Shor's algorithm.
- 7,788
9
votes
What are semantic classes that have a syntactic equivalent?
FWIW, the ostensibly semantic class APP defined in [1] was shown to be syntactic in [2].
[1] Valentine Kabanets, Charles Rackoff, Stephen A. Cook, Efficiently
approximable real-valued functions, ...
- 18.6k
8
votes
Examples of the price of abstraction?
Reingold's algorithm solves undirected s-t connectivity in logarithmic space.
If we use a pointer machine, which maintains pointers as abstract objects without a total ordering, the problem can no ...
8
votes
Sufficient conditions for the collapse of Polynomial Hierarchy (PH)
Here is another interesting condition under which Polynomial-hierarchy collapses to third level: Suppose an NP-complete language has a random self-reduction (non-adaptive), Then the polynomial ...
- 251
8
votes
Accepted
List of (unsolved) complexity problems arising from PL
Pippenger's (1) from 1996 shows that (under some assumptions) strict (CBV) functional programming languages are asympotically slower than imperative languages. It is open whether Pippenger's result ...
- 11.6k
8
votes
Stephen Hawking's impact on computer science
He didn't have any major impact on computer science.
His writing in computer science are limited to popsci and more recently raising public concerns about AI.
- 91
8
votes
Examples of collapsing hierarchies
Interesting result from Quantum Computing, though, If it fits into your requirements of what hierarchies you are looking at, is at discretion. The QMA hierarchy collapse result of Harrow, Montanaro ...
- 1,261
8
votes
Examples of collapsing hierarchies
When I was in graduate school, I once presented for a class a paper from a STOC conference (mid-80's) entitled "The Strong Exponential Hierarchy Collapses".
- 81
8
votes
Examples of collapsing hierarchies
Barrington’s theorem: if $\def\bp{\mathrm{BP}}\bp_k$ denotes the class of languages computable by polynomial-size width-$k$ branching programs, we have
$$\bp_1\subsetneq\bp_2\subsetneq\bp_3\subseteq\...
- 18.6k
8
votes
What are examples of recent relatively simple 'toolbox algorithms'?
You could look at the multiplicative weights update method. Specific instances of this technique have been known since the 1950s, but it's only been recognized as a very useful general algorithmic ...
- 25k
7
votes
What videos should everybody watch?
CS Theory Toolkit by Prof. Ryan O'Donnell.
Great for newbies, and includes interesting viewing angle on various topics:
https://www.youtube.com/playlist?list=PLm3J0oaFux3ZYpFLwwrlv_EHH9wtH6pnX
7
votes
Common false beliefs in theoretical computer science
Superpolynomial time complexity cannot be in P. While this appears easy to believe, it is actually a false belief.
Formally, we may think that if $f(n)$ is a superpolynomial function, then ${\mathsf {...
Only top scored, non community-wiki answers of a minimum length are eligible