On Boosting with Optimal Poly-Bounded Distributions. - Nader H. Bshouty; Dmitry Gavinsky (COLT/EuroCOLT, 2001)

PAC = PAExact and Other Equivalent Models in Learning. - Nader H. Bshouty; Dmitry Gavinsky (FOCS, 2002)

On Boosting with Polynomially Bounded Distributions. - Nader H. Bshouty; Dmitry Gavinsky (J. Mach. Learn. Res., 2002)

Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning. - Dmitry Gavinsky (J. Mach. Learn. Res., 2003)

PExact = Exact Learning. - Dmitry Gavinsky; Avi Owshanko (COLT, 2004)

Quantum Communication Cannot Simulate a Public Coin - Dmitry Gavinsky; Julia Kempe; Ronald de Wolf (CoRR, 2004)

Quantum solution to the hidden subgroup problem for poly-near-hamiltonian groups. - Dmitry Gavinsky (Quantum Inf. Comput., 2004)

A Note on Shared Randomness and Shared Entanglement in Communication - Dmitry Gavinsky (CoRR, 2005)

Strengths and Weaknesses of Quantum Fingerprinting. - Dmitry Gavinsky; Julia Kempe; Ronald de Wolf (CCC, 2006)

Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function. - Dmitry Gavinsky; Julia Kempe; Ronald de Wolf (Electron. Colloquium Comput. Complex., 2006)

Exponential separations for one-way quantum communication complexity, with applications to cryptography. - Dmitry Gavinsky; Julia Kempe; Iordanis Kerenidis; Ran Raz; Ronald de Wolf (STOC, 2007)

Classical Interaction Cannot Replace a Quantum Message. - Dmitry Gavinsky (Electron. Colloquium Comput. Complex., 2007)

Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity. - Dmitry Gavinsky; Pavel Pudlák (Electron. Colloquium Comput. Complex., 2007)

Quantum Algorithms for Evaluating Min-MaxTrees. - Richard Cleve; Dmitry Gavinsky; David L. Yonge-Mallo (TQC, 2008)

Simultaneous Communication Protocols with Quantum and Classical Messages. - Dmitry Gavinsky; Oded Regev 001; Ronald de Wolf (Chic. J. Theor. Comput. Sci., 2008)

On the role of shared entanglement. - Dmitry Gavinsky (Quantum Inf. Comput., 2008)

Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. - Dmitry Gavinsky; Julia Kempe; Iordanis Kerenidis; Ran Raz; Ronald de Wolf (SIAM J. Comput., 2008)

Entanglement-resistant two-prover interactive proof systems and non-adaptive pir's. - Richard Cleve; Dmitry Gavinsky; Rahul Jain 001 (Quantum Inf. Comput., 2009)

Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. - Dmitry Gavinsky; Julia Kempe; Oded Regev 001; Ronald de Wolf (SIAM J. Comput., 2009)

Quantum Fingerprints that Keep Secrets. - Dmitry Gavinsky; Tsuyoshi Ito (Electron. Colloquium Comput. Complex., 2010)

A Separation of NP and coNP in Multiparty Communication Complexity. - Dmitry Gavinsky; Alexander A. Sherstov (Electron. Colloquium Comput. Complex., 2010)

Quantum Algorithm for the Boolean Hidden Shift Problem. - Dmitry Gavinsky; Martin Roetteler; Jérémie Roland (COCOON, 2011)

Quantum Money with Classical Verification. - Dmitry Gavinsky (CCC, 2012)

Pseudorandom Generators for Read-Once ACC^0. - Dmitry Gavinsky; Shachar Lovett; Srikanth Srinivasan 001 (CCC, 2012)

A Tail Bound for Read-k Families of Functions. - Dmitry Gavinsky; Shachar Lovett; Michael E. Saks; Srikanth Srinivasan 001 (Electron. Colloquium Comput. Complex., 2012)

Quantum predictive learning and communication complexity with single input. - Dmitry Gavinsky (Quantum Inf. Comput., 2012)

Shared Randomness and Quantum Communication in the Multi-Party Model. - Dmitry Gavinsky; Tsuyoshi Ito; Guoming Wang (Electron. Colloquium Comput. Complex., 2013)

En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations. - Dmitry Gavinsky; Shachar Lovett (Electron. Colloquium Comput. Complex., 2013)

Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. - Dmitry Gavinsky; Or Meir; Omri Weinstein; Avi Wigderson (Electron. Colloquium Comput. Complex., 2013)

Partition Expanders. - Dmitry Gavinsky; Pavel Pudlák (Electron. Colloquium Comput. Complex., 2014)

Correlation in Hard Distributions in Communication Complexity. - Ralph Bottesch; Dmitry Gavinsky; Hartmut Klauck (APPROX-RANDOM, 2015)

Equality, Revisited. - Ralph Bottesch; Dmitry Gavinsky; Hartmut Klauck (MFCS (2), 2015)

On the Entropy of Locally-Independent Bernoulli Trials. - Dmitry Gavinsky; Pavel Pudlák (CoRR, 2015)

On the Role of Shared Randomness in Simultaneous Communication. - Mohammad Bavarian; Dmitry Gavinsky; Tsuyoshi Ito (Electron. Colloquium Comput. Complex., 2015)

A tail bound for read-k families of functions. - Dmitry Gavinsky; Shachar Lovett; Michael E. Saks; Srikanth Srinivasan 001 (Random Struct. Algorithms, 2015)

Communication complexity of inevitable intersection. - Dmitry Gavinsky (CoRR, 2016)

A Composition Theorem for Randomized Query complexity. - Anurag Anshu; Dmitry Gavinsky; Rahul Jain 001; Srijita Kundu; Troy Lee; Priyanka Mukhopadhyay; Miklos Santha; Swagato Sanyal (Electron. Colloquium Comput. Complex., 2017)

Quadratically Tight Relations for Randomized Query Complexity. - Dmitry Gavinsky; Rahul Jain 001; Hartmut Klauck; Srijita Kundu; Troy Lee; Miklos Santha; Swagato Sanyal; Jevgenijs Vihrovs (Electron. Colloquium Comput. Complex., 2017)

Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. - Dmitry Gavinsky; Or Meir; Omri Weinstein; Avi Wigderson (SIAM J. Comput., 2017)

On the randomised query complexity of composition. - Dmitry Gavinsky; Troy Lee; Miklos Santha (CoRR, 2018)

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. - Dmitry Gavinsky; Troy Lee; Miklos Santha; Swagato Sanyal (ICALP, 2019)

Quantum Versus Classical Simultaneity in Communication Complexity. - Dmitry Gavinsky (IEEE Trans. Inf. Theory, 2019)

The communication complexity of the inevitable intersection problem. - Dmitry Gavinsky (Chic. J. Theor. Comput. Sci., 2020)

Santha-Vazirani sources, deterministic condensers and very strong extractors. - Dmitry Gavinsky; Pavel Pudlák (Theory Comput. Syst., 2020)

Entangled Simultaneity Versus Classical Interactivity in Communication Complexity. - Dmitry Gavinsky (IEEE Trans. Inf. Theory, 2020)

Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity. - Dmitry Gavinsky (IEEE Trans. Inf. Theory, 2021)

The Layer Complexity of Arthur-Merlin-like Communication. - Dmitry Gavinsky (Adv. Math. Commun., 2021)

Unambiguous Parity-Query Complexity. - Dmitry Gavinsky (Random Struct. Algorithms, 2025)