My Publications

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

• A Tail Bound for Read-k Families of Functions.
  D. Gavinsky, S. Lovett, M. Saks and S. Srinivasan.
  arXiv:1205.1478  ECCC TR12-051
  Submitted.
  
  
• Pseudorandom Generators for Read-Once ACC0.
  D. Gavinsky, S. Lovett and S. Srinivasan.
  Accepted to the 27th Computational Complexity Conference (CCC), 2012 (conference version).
  
  
• Quantum Money with Classical Verification.
  D. Gavinsky.
  arXiv:1109.0372
  Accepted to the 27th Computational Complexity Conference (CCC), 2012.
  
  
• Quantum Fingerprints that Keep Secrets.
  D. Gavinsky and T. Ito.
  arXiv:1010.5342  ECCC TR10-165
  Submitted to a journal.
  
  
• A Separation of NP and coNP in Multiparty Communication Complexity.
  D. Gavinsky and A. Sherstov.
  arXiv:1004.0817  ECCC TR10-060
  Theory of Computing, Volume 6, Article 10, 2010.
  
  
• Classical Interaction Cannot Replace Quantum Nonlocality.
  D. Gavinsky.
  arXiv:0901.0956
  12th Workshop on Quantum Information Processing (QIP), 2009.
  Submitted to a journal.
  
  
• Quantum Predictive Learning and Communication Complexity with Single Input.
  D. Gavinsky.
  arXiv:0812.3429
  12th Workshop on Quantum Information Processing (QIP), 2009.
  Proceedings of the 23rd Conference on Computational Learning Theory (COLT), pages 207-217, 2010.
  Quantum Information & Computation, Volume 12(7-8), pages 575-588, 2012.
  
  
• Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity.
  D. Gavinsky and P. Pudlák.
  arXiv:0708.0859  ECCC TR07-074
  Proceedings of the 23rd Computational Complexity Conference (CCC), pages 332-339, 2008.
  
  
• Simultaneous Communication Protocols with Quantum and Classical Messages.
  D. Gavinsky, O. Regev and R. de Wolf.
  arXiv:0807.2758
  Chicago Journal of Theoretical Computer Science, Article 7, 2008.
  
  
• Quantum Algorithms for Evaluating Min-Max Trees.
  R. Cleve, D. Gavinsky and D. L. Yeung.
  arXiv:0710.5794
  Proceedings of the 3rd Workshop on Theory of Quantum Computation, Communication and Cryptography (TQC), 2008.
  Lecture Notes in Computer Science, Volume 5106, Volume 5106 (special issue on TQC'08), pages 11-15, 2008.
  
  
• Classical Interaction Cannot Replace a Quantum Message.
  D. Gavinsky.
  quant-ph/0703215  ECCC TR07-058
  Proceedings of the 40th Symposium on Theory of Computing (STOC), pages 95-102, 2008.
  
  
• Entanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems.
  R. Cleve, D. Gavinsky and R. Jain.
  arXiv:0707.1729
  7th Asian Conference on Quantum Information Science (AQIS), 2007.
  Quantum Information & Computation, Volume 9(7), pages 648-656, 2009.
  
  
• Exponential Separations for One-Way Quantum Communication Complexity, with Applications to Cryptography.
  D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz and R. de Wolf.
  quant-ph/0611209
  Proceedings of the 39th Symposium on Theory of Computing (STOC), pages 516-525, 2007.
  SIAM Journal of Computing, Volume 38(5), pages 1695-1708, 2008.
  
  
• On the Role of Shared Entanglement.
  D. Gavinsky.
  quant-ph/0604052
  7th Asian Conference on Quantum Information Science (AQIS), 2007.
  Quantum Information & Computation, Volume 8(1-2), pages 82-95, 2008.
  
  
• Strengths and Weaknesses of Quantum Fingerprinting.
  D. Gavinsky, J. Kempe and R. de Wolf.
  quant-ph/0603173
  Proceedings of the 21st Computational Complexity Conference (CCC), pages 288-298, 2006.
  
  
• Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity.
  D. Gavinsky, J. Kempe, O. Regev and R. de Wolf.
  quant-ph/0511013
  9th Workshop on Quantum Information Processing (QIP), 2006.
  Proceedings of the 38th Symposium on Theory of Computing (STOC), pages 594-603, 2006.
  SIAM Journal of Computing, Volume 39(1) (special issue on STOC'06), pages 1-24, 2009.
  
  
• Quantum Communication Cannot Simulate a Public Coin.
  D. Gavinsky, J. Kempe and R. de Wolf.
  quant-ph/0411051
  8th Workshop on Quantum Information Processing (QIP), 2005.
  
  
• PExact = Exact Learning.
  D. Gavinsky and A. Owshanko.
  Proceedings of the 17th Conference on Computational Learning Theory (COLT), pages 200-209, 2004.
  
  
• Quantum Solution to the Hidden Subgroup Problem for Poly-Near-Hamiltonian Groups.
  D. Gavinsky.
  ERATO Conference on Quantum Information Science, 2003.
  Quantum Information & Computation, Volume 4(3), pages 229-235, 2004.
  
  
• PAC = PAExact and Other Equivalent Models in Learning.
  N. Bshouty and D. Gavinsky.
  Proceedings of the 43th Annual Symposium on Foundations of Computer Science (FOCS), pages 167-176, 2002.
  
  
• Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning.
  D. Gavinsky.
  Proceedings of the 13th International Conference on Algorithmic Learning Theory (ALT), pages 98-112, 2002.
  Journal of Machine Learning Research, Volume 4, pages 101-117, 2003.
  
  
• On Boosting with Optimal Poly-Bounded Distributions.
  N. Bshouty and D. Gavinsky.
  Proceedings of the 14th Conference on Computational Learning Theory (COLT), pages 490-506, 2001.
  Journal of Machine Learning Research, Volume 3 (special issue on COLT'01), pages 483-506, 2002.