# Tag Info

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

13

I'd love to be shown wrong, but I don't think there are currently any uniform lower bounds that aren't ultimately based on one of the hierarchy theorems. Our current understanding of how to take advantage of uniformity is really quite limited in that sense. On the other hand, there are many uniform lower bounds that don't follow directly from hierarchy ...

11

Suppose that every circuit of depth $C\log^{k+1} n$ and size $Dn^\ell$ can be converted to an equivalent circuit of depth $C'\log^k n$ and size $D' n^{\ell'}$. Now suppose we are given a circuit of depth $C\log^{k+2} n$ and size $Dn^\ell$, and assume furthermore that it's a levelled circuit (making a circuit levelled only increases the size polynomially). ...

11

$\mathbf{UL}$ is contained in $\mathbf{NL}$, which is contained in $\mathbf{DSPACE}(\log^2 n)$ by Savitch's theorem, which is strictly contained in $\mathbf{PSPACE}$ by the space hierarchy theorem, so $\mathbf{UL}$ is strictly contained in $\mathbf{PSPACE}$. It would be surprising if e.g. $\mathbf{UL} = \mathbf{DSPACE}(\log^2 n)$, but I don't think it's ...

10

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

9

For example, I think you can decide if $\lfloor\log_2|w|\rfloor$ is even in time $O(n\log n)$: you first overwrite the input string with all 1s, and then do $\log n$ passes over the string where you turn every other 1 into a 0 (while skipping 0s that are already there). You keep track of the number of passes modulo 2.

9

According to the paper you linked, I think the answer to the question you want to ask is, "no." Pentation is not definable in a stratified version of system F. The paper says that their system can define every super-elementary function, and all definable functions are super-elementary. The super-elementary functions are level $\mathcal{E}^4$ in 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".

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

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

7

One non-uniform "space hierarchy" that we can prove is a size hierarchy for branching programs. For a Boolean function $f: \{0, 1\}^n \to \{0, 1\}$, let $B(f)$ denote the smallest size of a branching program computing $f$. By an argument analogous to this hierarchy argument for circuit size, one can show that there are constants $\epsilon, c$ so for every ...

5

Typically, fast growing hierarchies are characterized by ordinal notations, which are really just ways to express fast-growing functions (but it's sometimes convenient to see them as ordinals in the mathematical sense). There is a somewhat generic way of assigning an ordinal (notation) to a consistent theory, though it is very non-constructive. For various ...

5

Here is a new hierarchy for context-free languages by Tomoyuki Yamakami. He introduces an oracle mechanism in nondeterministic pushdown automata and notions of Turing and many-one reducibilities. Then a new hierarchy is constructed for Context-free languages (CFL) similar to the polynomial hierarchy. For example, $CFL$, $CFL^{CFL}$, etc. The interesting ...

5

The theory of regular languages of infinite trees gave rise to several hierarchies, that are currently studied, with many questions that are still open. When using automata on infinite trees, the parity condition (or Mostowski condition) is of special interest, because non-deterministic parity automata can express all regular languages of ininite trees, and ...

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

k-SAT collapses at 3, of course.

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

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

4

Regarding your last question: The paper Size-Depth Trade-offs for Threshold Circuits shows that the parity function requires depth-$d$ threshold circuits with $\ge n^{1+\epsilon(d)}$ wires, which is tight up to the function $\epsilon$. But for gates not even $\Omega(n)$ lower bounds are known.

4

Is the separation $\mathsf{AC}^0\subsetneq\mathsf{TC}^0$ by Smolensky something you have been looking for?

3

I don't see the need for your clarification, since through linear speed-up those sets are exactly the same. It is clear why you need to avoid using asymptotics, since $f(n)-g(n)$ and $f(n)$ are asymptotically the same, but not using asymptotics doesn't somehow make the linear speed-up theorem not true. Some further insight can be gained. $g(n)$ is actually $... 3 From this question on cs.stackexchange, I became aware of the genus hierarchy of regular languages. Essentially, you can characterize regular languages based on the minimum genus surface in which the graph of their DFA may be embedded. It is shown in [1] that there exist languages of arbitrarily large genus and that this hierarchy is proper. Bonfante, ... 3 Elaborating on one of the bullet points mentioned by the OP (GoldreichKNR09): there are several hierarchy theorems in property testing and proofs of proximity, relating to the query complexity, the adaptivity, or the testability with regard to number of rounds (for proofs of proximity). See, e.g., Hierarchy Theorems for Property Testing, Oded Goldreich, ... 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)$... 2 Perhaps this recent result (Jan 2020) showing that MIP* = RE. 2 Another nontrivial example comes from the area of average case complexity. Rainer Schuler proves interesting properties of the class he calls$P_{P-comp}$, see [1].$P_{P-comp}$is the class of languages that are accepted in polynomial time on$\mu$-average for every polynomial time computable (P-computable) distribution$\mu$. Naturally,$P\subseteq P_{P-...

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