All reports by Author Andrew Drucker:

__
TR20-145
| 23rd September 2020
__

Andrew Drucker#### An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature

__
TR20-027
| 26th February 2020
__

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan#### The Power of Many Samples in Query Complexity

__
TR12-112
| 7th September 2012
__

Andrew Drucker#### New Limits to Classical and Quantum Instance Compression

Revisions: 3

__
TR11-125
| 16th September 2011
__

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

Revisions: 1
,
Comments: 1

__
TR11-073
| 3rd May 2011
__

Andrew Drucker#### Efficient Probabilistically Checkable Debates

__
TR11-008
| 27th January 2011
__

Scott Aaronson, Andrew Drucker#### Advice Coins for Classical and Quantum Computation

__
TR10-080
| 5th May 2010
__

Andrew Drucker#### Improved Direct Product Theorems for Randomized Query Complexity

Revisions: 1

__
TR10-057
| 1st April 2010
__

Scott Aaronson, Andrew Drucker#### A Full Characterization of Quantum Advice

Revisions: 3

__
TR10-019
| 19th February 2010
__

Andrew Drucker#### A PCP Characterization of AM

__
TR09-102
| 21st October 2009
__

Andrew Drucker, Ronald de Wolf#### Quantum Proofs for Classical Theorems

__
TR08-096
| 8th September 2008
__

Andrew Drucker#### Multitask Efficiencies in the Decision Tree Model

__
TR08-051
| 4th April 2008
__

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor#### The Power of Unentanglement

Andrew Drucker

"Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly (here, uniformly); the final payoff to the non-random player is given by some $[0, 1]$-valued function of the move history. Estimating the value of such games under optimal play, and computing ... more >>>

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan

The randomized query complexity $R(f)$ of a boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution $D_0$ over $0$-inputs from a distribution $D_1$ over $1$-inputs, maximized over all pairs $(D_0,D_1)$. We ask: Does this task become easier if we ... more >>>

Andrew Drucker

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

Andrew Drucker

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

Andrew Drucker

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

Scott Aaronson, Andrew Drucker

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

Andrew Drucker

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

Scott Aaronson, Andrew Drucker

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

Andrew Drucker

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

Andrew Drucker, Ronald de Wolf

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

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

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

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