Dmitry Gavinsky

Orcid: 0000-0002-0729-7631

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

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
The Layer Complexity of Arthur-Merlin-like Communication.
Theory Comput., 2021

Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity.
IEEE Trans. Inf. Theory, 2021

2020
Entangled Simultaneity Versus Classical Interactivity in Communication Complexity.
IEEE Trans. Inf. Theory, 2020

Santha-Vazirani sources, deterministic condensers and very strong extractors.
Theory Comput. Syst., 2020

The communication complexity of the inevitable intersection problem.
Chic. J. Theor. Comput. Sci., 2020

2019
Quantum Versus Classical Simultaneity in Communication Complexity.
IEEE Trans. Inf. Theory, 2019

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
On the randomised query complexity of composition.
CoRR, 2018

2017
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation.
SIAM J. Comput., 2017

Quadratically Tight Relations for Randomized Query Complexity.
Electron. Colloquium Comput. Complex., 2017

A Composition Theorem for Randomized Query complexity.
Electron. Colloquium Comput. Complex., 2017

2016
Communication complexity of inevitable intersection.
CoRR, 2016

2015
A tail bound for read-<i>k</i> families of functions.
Random Struct. Algorithms, 2015

On the Role of Shared Randomness in Simultaneous Communication.
Electron. Colloquium Comput. Complex., 2015

On the Entropy of Locally-Independent Bernoulli Trials.
CoRR, 2015

Equality, Revisited.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Correlation in Hard Distributions in Communication Complexity.
Proceedings of the Approximation, 2015

2014
Partition Expanders.
Electron. Colloquium Comput. Complex., 2014

2013
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture.
Electron. Colloquium Comput. Complex., 2013

En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations.
Electron. Colloquium Comput. Complex., 2013

Shared Randomness and Quantum Communication in the Multi-Party Model.
Electron. Colloquium Comput. Complex., 2013

2012
Quantum predictive learning and communication complexity with single input.
Quantum Inf. Comput., 2012

A Tail Bound for Read-k Families of Functions.
Electron. Colloquium Comput. Complex., 2012

Pseudorandom Generators for Read-Once ACC^0.
Proceedings of the 27th Conference on Computational Complexity, 2012

Quantum Money with Classical Verification.
Proceedings of the 27th Conference on Computational Complexity, 2012

2011
Quantum Algorithm for the Boolean Hidden Shift Problem.
Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010
A Separation of NP and coNP in Multiparty Communication Complexity.
Electron. Colloquium Comput. Complex., 2010

Quantum Fingerprints that Keep Secrets.
Electron. Colloquium Comput. Complex., 2010

2009
Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity.
SIAM J. Comput., 2009

Entanglement-resistant two-prover interactive proof systems and non-adaptive pir's.
Quantum Inf. Comput., 2009

2008
Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography.
SIAM J. Comput., 2008

On the role of shared entanglement.
Quantum Inf. Comput., 2008

Simultaneous Communication Protocols with Quantum and Classical Messages.
Chic. J. Theor. Comput. Sci., 2008

Quantum Algorithms for Evaluating Min-MaxTrees.
Proceedings of the Theory of Quantum Computation, 2008

2007
Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity.
Electron. Colloquium Comput. Complex., 2007

Classical Interaction Cannot Replace a Quantum Message.
Electron. Colloquium Comput. Complex., 2007

Exponential separations for one-way quantum communication complexity, with applications to cryptography.
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.
Electron. Colloquium Comput. Complex., 2006

Strengths and Weaknesses of Quantum Fingerprinting.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005
A Note on Shared Randomness and Shared Entanglement in Communication
CoRR, 2005

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

Quantum Communication Cannot Simulate a Public Coin
CoRR, 2004

PExact = Exact Learning.
Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

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

2002
On Boosting with Polynomially Bounded Distributions.
J. Mach. Learn. Res., 2002

PAC = PAExact and Other Equivalent Models in Learning.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
On Boosting with Optimal Poly-Bounded Distributions.
Proceedings of the Computational Learning Theory, 2001


  Loading...