# Tag Info

## Hot answers tagged hierarchy-theorems

### 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)}$ ...
Accepted

### Is $UL\neq PSPACE$ known?

$\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 ...
• 1,743

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

### $DTIME_1(o(n^2))\setminus$ REGULAR

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 ...
• 14.9k
Accepted

### Is Church-pentation implementable in Agda?

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

### Examples of collapsing hierarchies

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

### Examples of collapsing hierarchies

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 ...
• 1,101
Accepted

### Does the space hierarchy theorem generalize to non-uniform computation?

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 ...
• 1,743

### Examples of collapsing hierarchies

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\...
• 14.9k

• 35.9k

### Examples of collapsing hierarchies

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,...
• 376

### Examples of collapsing hierarchies

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 ...
• 14.9k

### What hierarchies and/or hierarchy theorems do you know?

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

### What hierarchies and/or hierarchy theorems do you know?

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

### Examples of collapsing hierarchies

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

### What hierarchies and/or hierarchy theorems do you know?

Lasserre Hierarchy: An Hierarchy of progressively stronger (i.e., tighter, in the sense of integrality gaps) SDP relaxations of fractional polytopes J. Lasserre. An explicit exact SDP relaxation for ...
1 vote

### What hierarchies and/or hierarchy theorems do you know?

Consider the Unambiguous Polynomial Hierarchy, reference here, original reference here for the unambiguous polynomial hierarchy(paywalled). While studying the Boolean hierarchy BH, and classes such ...
1 vote

### What hierarchies and/or hierarchy theorems do you know?

The Polynomial Hierarchy in communication complexity as defined by Babai, Frankl, and Simon (see the original paper here and without the paywall here). The significance of this hierarchy is hard to ...

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