Dmitry Gavinsky

According to our database, Dmitry Gavinsky authored at least 48 papers between 2001 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2025

Unambiguous Parity-Query Complexity.

Dmitry Gavinsky

Random Struct. Algorithms, 2025

2021

The Layer Complexity of Arthur-Merlin-like Communication.

Dmitry Gavinsky

Theory Comput., 2021

2020

Santha-Vazirani sources, deterministic condensers and very strong extractors.

Dmitry Gavinsky, Pavel Pudlák

Theory Comput. Syst., 2020

The communication complexity of the inevitable intersection problem.

Dmitry Gavinsky

Chic. J. Theor. Comput. Sci., 2020

Bare quantum simultaneity versus classical interactivity in communication complexity.

Dmitry Gavinsky

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Quantum Versus Classical Simultaneity in Communication Complexity.

Dmitry Gavinsky

IEEE Trans. Inf. Theory, 2019

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.

Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

On the randomised query complexity of composition.

Dmitry Gavinsky, Troy Lee, Miklos Santha

CoRR, 2018

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

Quadratically Tight Relations for Randomized Query Complexity.

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Electron. Colloquium Comput. Complex., 2017

A Composition Theorem for Randomized Query Complexity.

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

Communication complexity of inevitable intersection.

Dmitry Gavinsky

CoRR, 2016

Entangled simultaneity versus classical interactivity in communication complexity.

Dmitry Gavinsky

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

A tail bound for read-<i>k</i> families of functions.

Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan

Random Struct. Algorithms, 2015

On the Entropy of Locally-Independent Bernoulli Trials.

Dmitry Gavinsky, Pavel Pudlák

CoRR, 2015

Equality, Revisited.

Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Correlation in Hard Distributions in Communication Complexity.

Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck

Proceedings of the Approximation, 2015

2014

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture.

Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

Proceedings of the Symposium on Theory of Computing, 2014

Partition Expanders.

Dmitry Gavinsky, Pavel Pudlák

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations.

Dmitry Gavinsky, Shachar Lovett

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

On the Role of Shared Randomness in Simultaneous Communication.

Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Quantum fingerprints that keep secrets.

Dmitry Gavinsky, Tsuyoshi Ito

Quantum Inf. Comput., 2013

Shared Randomness and Quantum Communication in the Multi-party Model.

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

A Tail Bound for Read-k Families of Functions.

Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2012

Pseudorandom Generators for Read-Once ACC^0.

Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan

Proceedings of the 27th Conference on Computational Complexity, 2012

Quantum Money with Classical Verification.

Dmitry Gavinsky

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Quantum Algorithm for the Boolean Hidden Shift Problem.

Dmitry Gavinsky, Martin Roetteler, Jérémie Roland

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010

A Separation of NP and coNP in Multiparty Communication Complexity.

Dmitry Gavinsky, Alexander A. Sherstov

Electron. Colloquium Comput. Complex., 2010

Quantum Predictive Learning and Communication Complexity with Single Input.

Dmitry Gavinsky

Proceedings of the COLT 2010, 2010

2009

Entanglement-resistant two-prover interactive proof systems and non-adaptive pir's.

Richard Cleve, Dmitry Gavinsky, Rahul Jain

Quantum Inf. Comput., 2009

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

On the role of shared entanglement.

Dmitry Gavinsky

Quantum Inf. Comput., 2008

Simultaneous Communication Protocols with Quantum and Classical Messages.

Dmitry Gavinsky, Oded Regev, Ronald de Wolf

Chic. J. Theor. Comput. Sci., 2008

Quantum Algorithms for Evaluating Min-MaxTrees.

Richard Cleve, Dmitry Gavinsky, David L. Yonge-Mallo

Proceedings of the Theory of Quantum Computation, 2008

Classical interaction cannot replace a quantum message.

Dmitry Gavinsky

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity.

Dmitry Gavinsky, Pavel Pudlák

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Exponential separations for one-way quantum communication complexity, with applications to cryptography.

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

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

Bounded-error quantum state identification and exponential separations in communication complexity.

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Strengths and Weaknesses of Quantum Fingerprinting.

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

A Note on Shared Randomness and Shared Entanglement in Communication

Dmitry Gavinsky

CoRR, 2005

2004

Quantum solution to the hidden subgroup problem for poly-near-hamiltonian groups.

Dmitry Gavinsky

Quantum Inf. Comput., 2004

Quantum Communication Cannot Simulate a Public Coin

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf

CoRR, 2004

PExact = Exact Learning.

Dmitry Gavinsky, Avi Owshanko

Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2002

On Boosting with Polynomially Bounded Distributions.

Nader H. Bshouty, Dmitry Gavinsky

J. Mach. Learn. Res., 2002

PAC = PAExact and Other Equivalent Models in Learning.

Nader H. Bshouty, Dmitry Gavinsky

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning.

Dmitry Gavinsky

Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002

2001

On Boosting with Optimal Poly-Bounded Distributions.

Nader H. Bshouty, Dmitry Gavinsky

Proceedings of the Computational Learning Theory, 2001