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")...
- 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)}$ ...
- 743
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 ...
- 1,934
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 ...
- 8,616
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
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,967
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 ...
- 131
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.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 ...
- 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 ...
- 50.9k
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 ...
- 36.9k
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 ...
- 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 ...
- 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 ...
- 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.
- 36.9k
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,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/...
- 91
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, ...
- 16.9k
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