Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KARP-LIPTON THEOREM:
Reports tagged with Karp-Lipton Theorem:
TR01-030 | 25th April 2001
Jin-Yi Cai

#### S_2^p \subseteq ZPP^{NP}

We show that the class ${\rm S}_2^p$ is a subclass of
${{\rm ZPP}^{\rm NP}}$. The proof uses universal hashing, approximate counting
and witness sampling. As a consequence, a collapse first noticed by
Samik Sengupta that the assumption NP has small circuits collapses
PH to ${\rm S}_2^p$
becomes the strongest version ... more >>>

TR09-055 | 10th June 2009
Venkatesan Chakaravarthy, Sambuddha Roy

#### Arthur and Merlin as Oracles

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class.
Our main results are the following: (i) $BPP^{NP}_{||} \subseteq P^{prAM}_{||}$; (ii) $S_2^p \subseteq P^{prAM}$. In addition to providing new upperbounds for the classes $S_2^p$ and $BPP^{NP}_{||}$, these results are interesting ... more >>>

TR10-057 | 1st April 2010
Scott Aaronson, Andrew Drucker

#### A Full Characterization of Quantum Advice

Revisions: 3

We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. ... more >>>

TR19-075 | 25th May 2019
Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams

#### Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

A frontier open problem in circuit complexity is to prove P^NP is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P/poly. Previously, for several classes containing P^NP, including NP^NP, ZPP^NP, and ... more >>>

ISSN 1433-8092 | Imprint