18

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)}$ can be rebalanced to have depth $O(\log^2 n)$ while only increasing the size by a polynomial factor. This is due to Valiant, Skyum, Berkowitz, and Rackoff. It ...


10

The AM hierarchy (constant-round interactive proofs) collapses to AM (Babai-Moran '88), but we don't yet know whether NP=MA=AM.


8

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 where QMA(2) =QMA(k) for k >= 2. More collapsing results: The $PL$ (Probabilistic Logspace) hierarchy collapses, ie $ PLH$ = $PL$. See paper here. . The ...


8

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


7

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\bp_4\subseteq\bp_5=\bigcup_{k\in\mathrm N}\bp_k=\mathrm{NC}^1.$$ Note that $\bp_4\subseteq\mathrm{AC}^0[6]$, hence likely $\bp_4\subsetneq\bp_5$.


5

Recall that for any prime $p$, the modulo-$p$ counting hierarchy $\def\modph#1{\mathrm{Mod}_{#1}\mathrm{PH}}\modph p$ is defined as the smallest class of languages such that $\mathrm{NP}^{\modph p}\let\sset\subseteq\sset\modph p$, $\oplus_p\mathrm P^{\modph p}\sset\modph p$. Toda’s theorem ensures that it collapses to $$\modph p=\mathrm{BP}\cdot\oplus_p\...


5

The parity acceptance condition for automata on infinite words induces a hierarchy of type $\Sigma_i/\Pi_i$, noted $[0,i]$ and $[1,i+1]$ with $i\in\mathbb N$. The parity condition of level $[a,b]$ works as follows: each state is labelled with an integer in $[a,b]$, and an infinite run is accepting iff the largest integer appearing infinitely often is even. ...


5

From computability theory we have the Ershov hierarchy, or rather its "naive linearization." The goal of the Ershov hierarchy is to analyze the $\Delta^0_2$ sets - that is, the sets computable from the halting problem $\emptyset'$. The starting point is to generalize the c.e. sets: A set is $1$-c.e. iff it is c.e., and a set is co-$1$-c.e. if it ...


5

k-SAT collapses at 3, of course.


5

Well one piece of evidence against PP being in BQP is that PP contains QMA, which is the NP equivalent of BQP.


5

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 longer be solved with a constant number of pointers. Paper "Pointer Programs and Undirected Reachability" by Schopp and Hofmann https://ulrichschoepp.de/...


4

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


4

Simons Institute for the Theory of Computing: https://www.youtube.com/user/SimonsInstitute/featured Institute for Advanced Study: https://www.youtube.com/user/videosfromIAS/featured Prinston TCS: https://www.youtube.com/channel/UCyGLYDvZ5BD5oYCIVv995HA/featured Stanford Computer Science Theory: https://www.youtube.com/user/StanfordCSTheory/featured ...


4

There is a list of open problems in computational geometry. It is edited and maintained by Demaine, Mitchell, and O'Rourke.


4

With three counters (or any larger amount) you can recognize precisely the recursively enumerable sets $A \subset \mathbb{N}$. With two counters, you cannot recognize the prime numbers or $e$th powers of natural numbers for fixed $e \geq 2$. Two heads are already quite powerful: the sets $\{2^n \;|\; n \in A\}$ you can accept are precisely the ones where $A$ ...


4

Isomorphism of $d$-tensors for any $d$ reduces to isomorphism of 3-tensors. (G.-Qiao, ITCS '21). 3-Tensor Isomorphism is at least as hard as Graph Isomorphism, and seems quite a bit harder (the current best algorithm is not asymptotically better than the trivial $q^{O(n^2)}$ algorithm for $n \times n \times n$ tensors over $\mathbb{F}_q$). This seems ...


3

The bounded (relational) width hierarchy of constraint satisfaction problem templates collapses: this was proved in Barto, Libor, The collapse of the bounded width hierarchy, J. Log. Comput. 26, No. 3, 923-943 (2016). ZBL1353.68107. The same result was also proved independently by Andrei Bulatov in an unpublished manuscript (link) around the same time. The ...


3

While the OP indicated they do not like it as it is a collapse to the first level, I think this deserves a mention because it is probably the most prominent example of something that was originally conceived and studied as a hierarchy until it was shown to collapse: The alternating logspace hierarchy $\Sigma_k^{\log}=\Sigma_k\text-\mathrm{SPACE}(\log n)$ ...


3

There is a list of open problems in graph theory and combinatorics collected and maintained by Douglas B. West. This page maintains a list of lists of open problems in parameterized complexity.


3

Algorithmic Game Theory Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 24 de set. de 2007 History of Computer Science COOPER, S. Barry; VAN LEEUWEN, Jan (Ed.). Alan Turing: His work and impact. Elsevier, 2013. Learning theory Kearns, Michael J., Umesh Virkumar Vazirani, and Umesh Vazirani....


2

Perhaps this recent result (Jan 2020) showing that MIP* = RE.


2

There's the TLCA List of Open Problems, collecting unsolved problems in $\lambda$-calculi and related areas, such as proof theory, semantics and theory of programming languages. It is maintained by Ryu Hasegawa, Luca Paolini and Paweł Urzyczyn. There's also a related list, the RTA list of open problems, concerning rewriting theory. At some point it was ...


2

Here is a new quantum computing podcast, by Vincent Russo, William Slofstra, and Henry Yuen: Nonlocal: a quantum computing podcast (https://nonlocal.libsyn.com/) This podcast takes you behind the scenes into the world of quantum computing research: through conversations with researchers, we explore the latest and most exciting ideas in the field. The ...


2

I like very much the TCS+ series of online seminars: https://sites.google.com/site/plustcs/


2

Technically it's an AI podcast but I love Lex Fridman's series: https://www.youtube.com/playlist?list=PLrAXtmErZgOdP_8GztsuKi9nrraNbKKp4 Theoretical CS does pop up in at least a few episodes.


2

A more recent open list of problems can be seen in the open problem session videos of the 2019 Workshop on Kernelization (WorKer 2019) (Session 1, Session 2). Several of the problems mentioned already remain open: Directed Feedback Vertex Set and Planar Vertex Deletion parameterized by the number $k$ of vertex deletions as mentioned by Bart remain open. The ...


2

This question was posted more than 8 years ago, and much progress was done since then. However, many questions remain open, even very natural ones like sampling a random graph with prescribed clustering coefficient. Also, sampling simple graphs (no loop, no multi-edge) with prescribed degree sequence made much progress but remains difficult. I would like to ...


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