We classify the univariate functions that are relativizable
closure properties of GapP, solving a problem posed by Hertrampf,
Vollmer, and Wagner (Structures '95). We also give a simple proof of
their classification of univariate functions that are relativizable
closure properties of #P.
Theoretical computer scientists have been debating the role of
oracles since the 1970's. This paper illustrates both that oracles
can give us nontrivial insights about the barrier problems in
circuit complexity, and that they need not prevent us from trying to
solve those problems.
First, we ... more >>>
Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA and QMA1 ... more >>>
We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure ... more >>>
Meta-complexity studies the complexity of computational problems about complexity theory, such as the Minimum Circuit Size Problem (MCSP) and its variants. We show that a relativization barrier applies to many important open questions in meta-complexity. We give relativized worlds where:
* MCSP can be solved in deterministic polynomial time, but ... more >>>
Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called *bounded relativization*. For a complexity class $C$, we say that a statement is *$C$-relativizing* if the statement holds relative ... more >>>
