Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > POLYNOMIAL HIERARCHY:
Reports tagged with polynomial hierarchy:
TR08-029 | 7th January 2008
Christian Glaßer, Christian Reitwießner, Victor Selivanov

#### The Shrinking Property for NP and coNP

We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results.

1. NP ... more >>>

TR09-107 | 28th October 2009
Kevin Dick, Chris Umans

#### Improved inapproximability factors for some $\Sigma_2^p$ minimization problems

We give improved inapproximability results for some minimization problems in the second level of the Polynomial-Time Hierarchy. Extending previous work by Umans [Uma99], we show that several variants of DNF minimization are $\Sigma_2^p$-hard to approximate to within factors of $n^{1/3-\epsilon}$ and $n^{1/2-\epsilon}$ (where the previous results achieved $n^{1/4 - \epsilon}$), ... more >>>

TR10-109 | 11th July 2010
Scott Aaronson

#### A Counterexample to the Generalized Linial-Nisan Conjecture

In earlier work, we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that "almost k-wise independent" distributions are indistinguishable from the uniform distribution by constant-depth ... more >>>

TR10-131 | 9th July 2010
Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki

#### The Power of Nondeterminism in Self-Assembly

We investigate the role of nondeterminism in Winfree's abstract Tile Assembly Model (aTAM), which was conceived to model artificial molecular self-assembling systems constructed from DNA. Designing tile systems that assemble shapes, due to the algorithmic richness of the aTAM, is a form of sophisticated "molecular programming". Of particular practical importance ... more >>>

TR10-170 | 11th November 2010
Scott Aaronson, Alex Arkhipov

#### The Computational Complexity of Linear Optics

We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a
model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count ... more >>>

TR12-112 | 7th September 2012
Andrew Drucker

Revisions: 3

Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $OR-compression ... more >>> TR13-189 | 21st December 2013 Periklis Papakonstantinou, Dominik Scheder, Hao Song #### Overlays and Limited Memory Communication Mode(l)s We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models. We introduce the notion of rectangle overlay complexity of a function$f: \{0,1\}^n\times \{0,1\}^n\to\{0,1\}$. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in ... more >>> TR14-075 | 16th May 2014 Holger Dell #### A simple proof that AND-compression of NP-complete problems is hard Revisions: 3 Drucker (2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP is in NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a simple proof of this result. An AND-compression is ... more >>> TR15-065 | 18th April 2015 Benjamin Rossman, Rocco Servedio, Li-Yang Tan #### An average-case depth hierarchy theorem for Boolean circuits We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every$d \geq 2$, there is an explicit$n$-variable Boolean function$f$, computed by a linear-size depth-$d$formula, which is such that any depth-$(d-1)$... more >>> TR15-130 | 11th August 2015 Ronald de Haan #### An Overview of Non-Uniform Parameterized Complexity We consider several non-uniform variants of parameterized complexity classes that have been considered in the literature. We do so in a homogenous notation, allowing a clear comparison of the various variants. Additionally, we consider some novel (non-uniform) parameterized complexity classes that come up in the framework of parameterized knowledge compilation. ... more >>> TR16-039 | 15th March 2016 Adam Bouland, Laura Mancinska, Xue Zhang #### Complexity Classification of Two-Qubit Commuting Hamiltonians We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian$H$which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one ... more >>> TR18-107 | 31st May 2018 Ran Raz, Avishay Tal #### Oracle Separation of BQP and PH We present a distribution$D$over inputs in$\{-1,1\}^{2N}$, such that: (1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time$O(\log N)$, that distinguishes between$D$and the uniform distribution with advantage$\Omega(1/\log N)$. (2) No Boolean circuit of$\mathrm{quasipoly}(N)$... more >>> TR19-131 | 11th September 2019 Lieuwe Vinkhuijzen, André Deutz #### A Simple Proof of Vyalyi's Theorem and some Generalizations In quantum computational complexity theory, the class QMA models the set of problems efficiently verifiable by a quantum computer the same way that NP models this for classical computation. Vyalyi proved that if$\text{QMA}=\text{PP}$then$\text{PH}\subseteq \text{QMA}\$. In this note, we give a simple, self-contained proof of the theorem, using ... more >>>

ISSN 1433-8092 | Imprint