Andrew Drucker

According to our database, Andrew Drucker authored at least 27 papers between 2008 and 2024.

Collaborative distances:

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

2024

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

Andrew Drucker, Yuan Li

CoRR, 2024

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

Proceedings of the Theory of Cryptography - 18th International Conference, 2020

The Power of Many Samples in Query Complexity.

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

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

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

Andrew Drucker

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

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

Akshima, David Cash, Andrew Drucker, Hoeteck Wee

Proceedings of the Advances in Cryptology - CRYPTO 2020, 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

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

The communication complexity of distributed task allocation.

Andrew Drucker, Fabian Kuhn, Rotem Oshman

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

High-confidence predictions under adversarial uncertainty.

Andrew Drucker

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

New Limits to Classical and Quantum Instance Compression.

Andrew Drucker

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

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

Andrew Drucker

Proceedings of the 27th Conference on Computational Complexity, 2012

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

A PCP Characterization of AM.

Andrew Drucker

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Advice Coins for Classical and Quantum Computation.

Scott Aaronson, Andrew Drucker

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Improved Direct Product Theorems for Randomized Query Complexity.

Andrew Drucker

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Efficient Probabilistically Checkable Debates.

Andrew Drucker

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

A full characterization of quantum advice.

Scott Aaronson, Andrew Drucker

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009

Quantum Proofs for Classical Theorems.

Andrew Drucker, Ronald de Wolf

Electron. Colloquium Comput. Complex., 2009

Multitask Efficiencies in the Decision Tree Model.

Andrew Drucker

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

The Power of Unentanglement.

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

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008