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,595
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
  • 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

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

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 ...
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
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 ...
Aryeh's user avatar
  • 10.3k
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

Problems with big open complexity gaps

The Skolem problem (given a linear recurrence with integer base cases and integer coefficients, does it ever reach the value 0) is known to be NP-hard and not known to be decidable. As far as I know ...
David Eppstein's user avatar
11 votes

Uncertainties in GCT program

It depends what you count as "the GCT program." Consider the specific suggestion (GCT I, GCT II) to use the vanishing/nonvanishing of certain multiplicities in the orbit closures of the determinant ...
Joshua Grochow's user avatar
11 votes
Accepted

Major open problems on polynomial kernel (non) existence

Currently, I would say the 3 major open cases are: Directed feedback vertex set (make a given digraph acyclic by deleting at most k vertices) parameterized by the size of the solution Planar Vertex ...
Bart Jansen's user avatar
  • 5,255
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,595
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 ...
harold's user avatar
  • 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.
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,595
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 Books Should Everyone Read?

Writing Mathematics Donald E. Knuth, Tracy Larrabee, and Paul M. Roberts, "Mathematical Writing", 1989 (pdf)
9 votes

Polynomial-time algorithms with huge exponent/constant

In their ICALP 2014 paper, Andreas Björklund and Thore Husfeldt give the first (randomized) polynomial algorithm that computes 2 disjoint paths with minimum total length (sum of the two paths length) ...
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 ...

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