# Tag Info

### Most memorable CS paper titles

I did a survey on Twitter about this a while back, results here. A few of my favorites: Parametric Polymorphism through Runtime Sealing, or, Theorems for Low, Low Prices! by Jacob Matthews and Amal ...

### Lipton's most influential results

The Planar Separator Theorem states that in any planar $n$-vertex graph $G$ there exists a set of $O(\sqrt{n})$ vertices whose removal leaves the graph disconnected into at least two roughly balanced ...

### Most memorable CS paper titles

I used to like quirky titles when I started out in computer science but got bored eventually. Some authors manage to write titles that are clever, memorable and relevant but most attempts at funny ...

### 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 ...
• 23.8k

### 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.

### Lipton's most influential results

Karp-Lipton Theorem states that $\mathsf{NP}$ cannot have polynomial-size boolean circuits unless the Polynomial hierarchy collapses to its second level. Two implications of this theorem for ...

### 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–...