Dmitry Gavinsky

According to our database, Dmitry Gavinsky authored at least 47 papers between 2001 and 2021.

Collaborative distances:

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

2021

The Layer Complexity of Arthur-Merlin-like Communication.

Dmitry Gavinsky

Theory Comput., 2021

Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity.

Dmitry Gavinsky

IEEE Trans. Inf. Theory, 2021

2020

Entangled Simultaneity Versus Classical Interactivity in Communication Complexity.

Dmitry Gavinsky

IEEE Trans. Inf. Theory, 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

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

Electron. Colloquium Comput. Complex., 2017

2016

Communication complexity of inevitable intersection.

Dmitry Gavinsky

CoRR, 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 Role of Shared Randomness in Simultaneous Communication.

Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito

Electron. Colloquium Comput. Complex., 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

Partition Expanders.

Dmitry Gavinsky, Pavel Pudlák

Electron. Colloquium Comput. Complex., 2014

2013

Quantum fingerprints that keep secrets.

Dmitry Gavinsky, Tsuyoshi Ito

Quantum Inf. Comput., 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

En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations.

Dmitry Gavinsky, Shachar Lovett

Electron. Colloquium Comput. Complex., 2013

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

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

Electron. Colloquium Comput. Complex., 2013

2012

Quantum predictive learning and communication complexity with single input.

Dmitry Gavinsky

Quantum Inf. Comput., 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

Theory Comput., 2010

2009

Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity.

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

SIAM J. Comput., 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

2007

Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity.

Dmitry Gavinsky, Pavel Pudlák

Electron. Colloquium Comput. Complex., 2007

Classical Interaction Cannot Replace a Quantum Message.

Dmitry Gavinsky

Electron. Colloquium Comput. Complex., 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

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

2003

Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning.

Dmitry Gavinsky

J. Mach. Learn. Res., 2003

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 (FOCS 2002), 2002

2001

On Boosting with Optimal Poly-Bounded Distributions.

Nader H. Bshouty, Dmitry Gavinsky

Proceedings of the Computational Learning Theory, 2001