Dmitry Gavinsky

Mathematical Institute of the Academy of Sciences of the Czech Republic
Department of Mathematical Logic, Algebra and Theoretical Computer Science

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.