Name
Title | ||
|---|---|---|
Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits. |
Abstract | ||
|---|---|---|
We give an overview of a recent result [RST15] showing that the polynomial hierarchy is in finite relative to a random oracle. Since the early 1980s it has been known that this result would follow from a certain \"average-case depth hierarchy theorem\" for Boolean circuits. In this article we present some background and history of related relativized separations; sketch the argument showing how the polynomial hierarchy result follows from the circuit lower bound; and explain the techniques underlying the new circuit lower bound. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2852040.2852052 | SIGACT News |
Field | DocType | Volume |
Karp–Lipton theorem,Polynomial hierarchy,Discrete mathematics,Boolean circuit,Combinatorics,Structural complexity theory,Analytical hierarchy,Arithmetical hierarchy,Hierarchy,Fast-growing hierarchy,Mathematics | Journal | 46 |
Issue | Citations | PageRank |
4 | 1 | 0.36 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Benjamin Rossman | 1 | 4 | 4.28 |
| Rocco A. Servedio | 2 | 1656 | 133.28 |
| Li-Yang Tan | 3 | 159 | 24.26 |