papers
Publications (10)
quant-ph2008
Simultaneous Communication Protocols with Quantum and Classical Messages
Dmitry Gavinsky, Oded Regev, Ronald de Wolf
cs.CC2017
A Composition Theorem for Randomized Query Complexity
Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5
cs.CC2018
A composition theorem for randomized query complexity via max conflict complexity
Dmitry Gavinsky, Troy Lee, Miklos Santha +1
cs.CC2017
Quadratically Tight Relations for Randomized Query Complexity
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck +5
cs.CC2015
On the Role of Shared Randomness in Simultaneous Communication
Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito
quant-ph2013
Shared Randomness and Quantum Communication in the Multi-Party Model
Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang
cs.CC2015
Correlation in Hard Distributions in Communication Complexity
Ralph C. Bottesch, Dmitry Gavinsky, Hartmut Klauck
quant-ph2012
A quantum query algorithm for the graph collision problem
Dmitry Gavinsky, Tsuyoshi Ito
quant-ph2007
Entanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems
Richard Cleve, Dmitry Gavinsky, Rahul Jain
quant-ph2011
Quantum algorithm for the Boolean hidden shift problem
Dmitry Gavinsky, Martin Roetteler, Jérémie Roland