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

12

You can check the following paper: Translational lemmas, polynomial time, and $(\log n)^j$-space by Ronald V. Book (1976). Figures 1 and 2 in the paper give the summary of what is known and what is unknown. I put Theorem 3.10 in the paper here: $DTIME(poly(n)) \neq DSPACE(poly(\log n))$; for every $j \geq 1$, $DTIME(n^j) \neq DSPACE(poly(\log n))$...

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

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

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

8

A paper of Klawe, Paul, Pippenger, and Yannakakis gives an hierarchy theorem for constant depth monotone formulas: http://dl.acm.org/citation.cfm?id=808717 Specifically, for every $k$ it gives a function that can be computed by a formula of depth $k$ and size $n$ but requires formulas of depth $k-1$ of size $\exp(n^{1/k})$.

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

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

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

7

Raz and McKenzie, in Separation of the monotone NC hierarchy, show that the monotone NC hierarchy is strict, and separate monotone NC from monotone P.

6

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

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

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

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

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

4

Isomorphism of $d$-tensors for any $d$ reduces to isomorphism of 3-tensors. 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 strictly harder than ...

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

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

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 Not sure about what kind of results you seek but here what I know for sub-classes of$AC^0$(constant depth and polynomial size Boolean circuits): The separation between$AC^0$and its linear fragment (namely$LAC^0$) is known since 96. It is a result of Chaudhuri and Radhakrishnan : "Deterministic restrictions in circuit complexity". This result seems to ... 3 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$... 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.

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