Andrew Drucker

According to our database, Andrew Drucker authored at least 26 papers between 2008 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes.

Andrew Drucker, Yuan Li

Proceedings of the Computing and Combinatorics - 29th International Conference, 2023

2022

Guest Editor's Foreword to the RANDOM 2018 Special Issue.

Andrew Drucker

Theory Comput., 2022

2021

Quantum Fan-out: Circuit Optimizations and Technology Modeling.

Pranav Gokhale, Samantha Koretsky, Shilin Huang, Swarnadeep Majumder, Andrew Drucker, Kenneth R. Brown, Frederic T. Chong

Proceedings of the IEEE International Conference on Quantum Computing and Engineering, 2021

2020

A Lower Bound for One-Round Oblivious RAM.

David Cash, Andrew Drucker, Alexander Hoover

IACR Cryptol. ePrint Arch., 2020

Time-Space Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions.

Akshima, David Cash, Andrew Drucker, Hoeteck Wee

IACR Cryptol. ePrint Arch., 2020

An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature.

Andrew Drucker

Electron. Colloquium Comput. Complex., 2020

The Power of Many Samples in Query Complexity.

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

Electron. Colloquium Comput. Complex., 2020

2017

A Note on a Communication Game.

Andrew Drucker

CoRR, 2017

2016

Exponential Time Paradigms Through the Polynomial Time Lens.

Andrew Drucker, Jesper Nederlof, Rahul Santhanam

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2014

On the power of the congested clique model.

Andrew Drucker, Fabian Kuhn, Rotem Oshman

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

2013

High-confidence predictions under adversarial uncertainty.

Andrew Drucker

ACM Trans. Comput. Theory, 2013

Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers.

Andrew Drucker

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

The complexity of joint computation.

Andrew Drucker

PhD thesis, 2012

New Limits to Classical and Quantum Instance Compression.

Andrew Drucker

Electron. Colloquium Comput. Complex., 2012

Improved direct product theorems for randomized query complexity.

Andrew Drucker

Comput. Complex., 2012

The communication complexity of distributed task allocation.

Andrew Drucker, Fabian Kuhn, Rotem Oshman

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

2011

Quantum Proofs for Classical Theorems.

Andrew Drucker, Ronald de Wolf

Theory Comput., 2011

Block sensitivity of minterm-transitive functions.

Andrew Drucker

Theor. Comput. Sci., 2011

Uniform approximation by (quantum) polynomials.

Andrew Drucker, Ronald de Wolf

Quantum Inf. Comput., 2011

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

Andrew Drucker

Electron. Colloquium Comput. Complex., 2011

Efficient Probabilistically Checkable Debates.

Andrew Drucker

Electron. Colloquium Comput. Complex., 2011

Advice Coins for Classical and Quantum Computation.

Scott Aaronson, Andrew Drucker

Electron. Colloquium Comput. Complex., 2011

2010

A PCP Characterization of AM.

Andrew Drucker

Electron. Colloquium Comput. Complex., 2010

A Full Characterization of Quantum Advice.

Scott Aaronson, Andrew Drucker

Electron. Colloquium Comput. Complex., 2010

2009

The Power of Unentanglement.

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

Theory Comput., 2009

2008

Multitask Efficiencies in the Decision Tree Model.

Andrew Drucker

Electron. Colloquium Comput. Complex., 2008