Dmitry Gavinsky

Publication Activity (10 Years)

Years Active: 2001-2021
Publications (10 Years): 24

Top Topics

Universal Relation

Quantum Mechanics

Communication Overhead

Top Venues

Electron. Colloquium Comput. Complex.

IEEE Trans. Inf. Theory

Publications

Dmitry Gavinsky
Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity. IEEE Trans. Inf. Theory 67 (10) (2021)
Dmitry Gavinsky
The Layer Complexity of Arthur-Merlin-like Communication. Theory Comput. 17 (2021)
Dmitry Gavinsky
Bare quantum simultaneity versus classical interactivity in communication complexity. STOC (2020)
Dmitry Gavinsky
Entangled Simultaneity Versus Classical Interactivity in Communication Complexity. IEEE Trans. Inf. Theory 66 (7) (2020)
Dmitry Gavinsky, Pavel Pudlák
Santha-Vazirani sources, deterministic condensers and very strong extractors. Theory Comput. Syst. 64 (6) (2020)
Dmitry Gavinsky
The communication complexity of the inevitable intersection problem. Chic. J. Theor. Comput. Sci. 2020 (2020)
Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. ICALP (2019)
Dmitry Gavinsky
Quantum Versus Classical Simultaneity in Communication Complexity. IEEE Trans. Inf. Theory 65 (10) (2019)
Dmitry Gavinsky, Pavel Pudlák
Santha-Vazirani sources, deterministic condensers and very strong extractors. CoRR (2019)
Dmitry Gavinsky
Bare quantum simultaneity versus classical interactivity in communication complexity. CoRR (2019)
Dmitry Gavinsky, Troy Lee, Miklos Santha
On the randomised query complexity of composition. CoRR (2018)
Dmitry Gavinsky
The layer complexity of Arthur-Merlin-like communication. CoRR (2018)
Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
A composition theorem for randomized query complexity via max conflict complexity. CoRR (2018)
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
Quadratically Tight Relations for Randomized Query Complexity. Electron. Colloquium Comput. Complex. 24 (2017)
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. SIAM J. Comput. 46 (1) (2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query Complexity. FSTTCS (2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query complexity. Electron. Colloquium Comput. Complex. 24 (2017)
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
Quadratically Tight Relations for Randomized Query Complexity. CoRR (2017)
Dmitry Gavinsky
Quantum versus classical simultaneity in communication complexity. CoRR (2017)
Dmitry Gavinsky, Pavel Pudlák
Partition Expanders. Theory Comput. Syst. 60 (3) (2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query Complexity. CoRR (2017)
Dmitry Gavinsky
Entangled simultaneity versus classical interactivity in communication complexity. CoRR (2016)
Dmitry Gavinsky
Entangled simultaneity versus classical interactivity in communication complexity. STOC (2016)
Dmitry Gavinsky
Communication complexity of inevitable intersection. CoRR (2016)
Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito
On the Role of Shared Randomness in Simultaneous Communication. CoRR (2015)
Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
Correlation in Hard Distributions in Communication Complexity. CoRR (2015)
Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
families of functions. Random Struct. Algorithms 47 (1) (2015)
Ralph C. Bottesch, Dmitry Gavinsky, Hartmut Klauck
Equality, Revisited. CoRR (2015)
Dmitry Gavinsky, Pavel Pudlák
On the Entropy of Locally-Independent Bernoulli Trials. CoRR (2015)
Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito
On the Role of Shared Randomness in Simultaneous Communication. Electron. Colloquium Comput. Complex. 22 (2015)
Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
Correlation in Hard Distributions in Communication Complexity. APPROX-RANDOM (2015)
Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
Equality, Revisited. MFCS (2) (2015)
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. STOC (2014)
Dmitry Gavinsky, Pavel Pudlák
Partition Expanders. CoRR (2014)
Dmitry Gavinsky, Pavel Pudlák
Partition Expanders. STACS (2014)
Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito
On the Role of Shared Randomness in Simultaneous Communication. ICALP (1) (2014)
Dmitry Gavinsky, Pavel Pudlák
Partition Expanders. Electron. Colloquium Comput. Complex. 21 (2014)
Dmitry Gavinsky, Shachar Lovett
En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations. ICALP (1) (2014)
Dmitry Gavinsky, Shachar Lovett
En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations. Electron. Colloquium Comput. Complex. 20 (2013)
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. Electron. Colloquium Comput. Complex. 20 (2013)
Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang
Shared Randomness and Quantum Communication in the Multi-party Model. Computational Complexity Conference (2013)
Dmitry Gavinsky, Tsuyoshi Ito
Quantum fingerprints that keep secrets. Quantum Inf. Comput. 13 (7-8) (2013)
Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang
Shared Randomness and Quantum Communication in the Multi-Party Model. Electron. Colloquium Comput. Complex. 20 (2013)
Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan
Pseudorandom Generators for Read-Once ACC^0. Computational Complexity Conference (2012)
Dmitry Gavinsky
Quantum predictive learning and communication complexity with single input. Quantum Inf. Comput. 12 (7-8) (2012)
Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang
Shared Randomness and Quantum Communication in the Multi-Party Model CoRR (2012)
Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
A Tail Bound for Read-k Families of Functions CoRR (2012)
Dmitry Gavinsky
Quantum Money with Classical Verification. Computational Complexity Conference (2012)
Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
A Tail Bound for Read-k Families of Functions. Electron. Colloquium Comput. Complex. 19 (2012)
Dmitry Gavinsky
Quantum Money with Classical Verification CoRR (2011)
Dmitry Gavinsky, Martin Roetteler, Jérémie Roland
Quantum Algorithm for the Boolean Hidden Shift Problem. COCOON (2011)
Dmitry Gavinsky, Martin Roetteler, Jérémie Roland
Quantum algorithm for the Boolean hidden shift problem CoRR (2011)
Dmitry Gavinsky, Alexander A. Sherstov
A Separation of NP and coNP in Multiparty Communication Complexity. Theory Comput. 6 (1) (2010)
Dmitry Gavinsky
Quantum Predictive Learning and Communication Complexity with Single Input. COLT (2010)
Dmitry Gavinsky, Alexander A. Sherstov
A Separation of NP and coNP in Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. 17 (2010)
Dmitry Gavinsky, Tsuyoshi Ito
Quantum Fingerprints that Keep Secrets CoRR (2010)
Dmitry Gavinsky, Alexander A. Sherstov
A Separation of NP and coNP in Multiparty Communication Complexity CoRR (2010)
Dmitry Gavinsky, Tsuyoshi Ito
Quantum Fingerprints that Keep Secrets. Electron. Colloquium Comput. Complex. 17 (2010)
Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf
Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. SIAM J. Comput. 39 (1) (2009)
Richard Cleve, Dmitry Gavinsky, Rahul Jain
Entanglement-resistant two-prover interactive proof systems and non-adaptive pir's. Quantum Inf. Comput. 9 (7&8) (2009)
Dmitry Gavinsky, Oded Regev, Ronald de Wolf
Simultaneous Communication Protocols with Quantum and Classical Messages. Chic. J. Theor. Comput. Sci. 2008 (2008)
Dmitry Gavinsky
On the role of shared entanglement. Quantum Inf. Comput. 8 (1) (2008)
Dmitry Gavinsky
Classical interaction cannot replace a quantum message. STOC (2008)
Dmitry Gavinsky
Quantum Predictive Learning and Communication Complexity with Single Input. CoRR (2008)
Dmitry Gavinsky, Pavel Pudlák
Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity. Computational Complexity Conference (2008)
Richard Cleve, Dmitry Gavinsky, David L. Yonge-Mallo
Quantum Algorithms for Evaluating Min-MaxTrees. TQC (2008)
Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf
Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. SIAM J. Comput. 38 (5) (2008)
Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf
Exponential separations for one-way quantum communication complexity, with applications to cryptography. STOC (2007)
Dmitry Gavinsky
Classical Interaction Cannot Replace a Quantum Message. Electron. Colloquium Comput. Complex. 14 (058) (2007)
Dmitry Gavinsky, Pavel Pudlák
Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity. Electron. Colloquium Comput. Complex. 14 (074) (2007)
Dmitry Gavinsky
Classical Interaction Cannot Replace a Quantum Message CoRR (2007)
Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
Strengths and Weaknesses of Quantum Fingerprinting. Computational Complexity Conference (2006)
Dmitry Gavinsky
On the Role of Shared Entanglement CoRR (2006)
Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
Strengths and Weaknesses of Quantum Fingerprinting CoRR (2006)
Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf
Bounded-error quantum state identification and exponential separations in communication complexity. STOC (2006)
Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function CoRR (2006)
Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function. Electron. Colloquium Comput. Complex. 13 (086) (2006)
Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf
Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity CoRR (2005)
Dmitry Gavinsky
A Note on Shared Randomness and Shared Entanglement in Communication CoRR (2005)
Dmitry Gavinsky, Avi Owshanko
PExact = Exact Learning. COLT (2004)
Dmitry Gavinsky
Quantum solution to the hidden subgroup problem for poly-near-hamiltonian groups. Quantum Inf. Comput. 4 (3) (2004)
Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
Quantum Communication Cannot Simulate a Public Coin CoRR (2004)
Dmitry Gavinsky
Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning. J. Mach. Learn. Res. 4 (2003)
Dmitry Gavinsky
Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning. ALT (2002)
Nader H. Bshouty, Dmitry Gavinsky
PAC = PAExact and Other Equivalent Models in Learning. FOCS (2002)
Nader H. Bshouty, Dmitry Gavinsky
On Boosting with Polynomially Bounded Distributions. J. Mach. Learn. Res. 3 (2002)
Nader H. Bshouty, Dmitry Gavinsky
On Boosting with Optimal Poly-Bounded Distributions. COLT/EuroCOLT (2001)