Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
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

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")...
usul's user avatar
  • 7,615
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)}$ ...
Robert Andrews's user avatar
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 ...
Lieuwe Vinkhuijzen's user avatar
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 ...
Lance Fortnow's user avatar
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 ...
chi's user avatar
  • 678
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 ...
Jeffrey Shallit's user avatar
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

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 ...
Raghu Meka's user avatar
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 ...
Aryeh's user avatar
  • 10.6k
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 ...
user13136's user avatar
  • 2,477
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 ...
usul's user avatar
  • 7,615
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 ...
user555045's user avatar
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.
Joshua Grochow's user avatar
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.
usul's user avatar
  • 7,615
9 votes

What's new in purely functional data structures since Okasaki?

Following up on the 2012 paper linked above, the work on RRB vectors has since been extended and published in ICFP'15. RRB vector: a practical general purpose immutable sequence http://dl.acm.org/...
Mike Rainey's user avatar
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, ...
Emil Jeřábek's user avatar
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 ...
Pawan Kumar's user avatar
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 ...
Martin Berger's user avatar
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.
Anonymous's user avatar
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 ...
user3483902's user avatar
  • 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".
PMar's user avatar
  • 81
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 ...
Peter Shor 's user avatar

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