Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Andrew Drucker:

TR12-112 | 7th September 2012
Andrew Drucker

New Limits to Classical and Quantum Instance Compression

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

TR11-125 | 16th September 2011
Andrew Drucker

Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators

Revisions: 1 , Comments: 1

We study the circuit complexity of Boolean operators, i.e., collections of Boolean functions defined over a common input. Our focus is the well-studied model in which arbitrary Boolean functions are allowed as gates, and in which a circuit's complexity is measured by its depth and number of wires. We show ... more >>>

TR11-073 | 3rd May 2011
Andrew Drucker

Efficient Probabilistically Checkable Debates

Probabilistically checkable debate systems (PCDSs) are debates between two competing provers, in which a polynomial-time verifier inspects a constant number of bits of the debate. It was shown by Condon, Feigenbaum, Lund, and Shor that every language in PSPACE has a PCDS in which the debate length is polynomially bounded. ... more >>>

TR11-008 | 27th January 2011
Scott Aaronson, Andrew Drucker

Advice Coins for Classical and Quantum Computation

We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states ... more >>>

TR10-080 | 5th May 2010
Andrew Drucker

Improved Direct Product Theorems for Randomized Query Complexity

Revisions: 1

The direct product problem is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of $k$ independent inputs scales with $k$.
We prove the following direct product theorem (DPT) for query complexity: if every $T$-query algorithm
has success probability at ... 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 >>>

TR10-019 | 19th February 2010
Andrew Drucker

A PCP Characterization of AM

We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class $\mathsf{AM}$. This gives a `PCP characterization' of $\mathsf{AM}$ analogous to the PCP Theorem for $\mathsf{NP}$. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, ... more >>>

TR09-102 | 21st October 2009
Andrew Drucker, Ronald de Wolf

Quantum Proofs for Classical Theorems

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (non-quantum) areas. In this paper we survey these results and the quantum toolbox they use.

more >>>

TR08-096 | 8th September 2008
Andrew Drucker

Multitask Efficiencies in the Decision Tree Model

In Direct Sum problems [KRW], one tries to show that for a given computational model, the complexity of computing a collection $F = \{f_1(x_1), \ldots f_l(x_l)\}$ of finite functions on independent inputs is approximately the sum of their individual complexities. In this paper, by contrast, we study the diversity of ... more >>>

TR08-051 | 4th April 2008
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The Power of Unentanglement

The class QMA(k), introduced by Kobayashi et al., consists
of all languages that can be verified using k unentangled quantum
proofs. Many of the simplest questions about this class have remained
embarrassingly open: for example, can we give any evidence that k
quantum proofs are more powerful than one? Can ... more >>>

ISSN 1433-8092 | Imprint