My Papers

“Thoughtcrime is a dreadful thing, old man... It's insidious. It can get hold of you without your even knowing it.”
George Orwell

2009. D. Gavinsky. Quantum Predictive Learning and Communication Complexity with Single Input.

2008. D. Gavinsky, O. Regev, R. de Wolf. Simultaneous Communication Protocols with Quantum and Classical Messages.

2008. D. Gavinsky. Classical Interaction Cannot Replace Quantum Nonlocality.

2007. R. Cleve, D. Gavinsky, D. L. Yeung. Quantum Algorithms for Evaluating Min-Max Trees.

2007. D. Gavinsky, P. Pudlák. Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity.

2007. R. Cleve, D. Gavinsky, R. Jain. Entanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems.

2007. D. Gavinsky. Classical Interaction Cannot Replace a Quantum Message.

2006. D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, R. de Wolf. Exponential Separations for One-Way Quantum Communication Complexity, with Applications to Cryptography.

2006. D. Gavinsky. On the Role of Shared Entanglement.

2006. D. Gavinsky, J. Kempe, R. de Wolf. Strengths and Weaknesses of Quantum Fingerprinting.

2005. D. Gavinsky, J. Kempe, O. Regev, R. de Wolf. Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity.

2004. D. Gavinsky, A. Owshanko. PExact = Exact Learning.

2003. D. Gavinsky. Quantum Solution to the Hidden Subgroup Problem for Poly-Near-Hamiltonian Groups.

2002. N. Bshouty, D. Gavinsky. PAC = PAExact and Other Equivalent Models in Learning.

2002. D. Gavinsky. Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning.

2001. N. Bshouty, D. Gavinsky. On Boosting with Optimal Poly-Bounded Distributions.

Technical Reports (superseded by later publications)

2008. D. Gavinsky. Predictive Quantum Learning.

2006. D. Gavinsky, J. Kempe, R. de Wolf. Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function.

2005. D. Gavinsky. A Note on Shared Randomness and Shared Entanglement in Communication.

2004. D. Gavinsky, J. Kempe, R. de Wolf. Quantum Communication Cannot Simulate a Public Coin.

2003. D. Gavinsky. Exact = PExact.