Dmitry Gavinsky

Dmitry Gavinsky

Matematický ústav Akademie věd České republiky
Matematická logika a teoretická informatika

Vybrané publikace (abecední řazení spoluautorů)

Bare quantum simultaneity versus classical interactivity in communication complexity.
arXiv

Santha-Vazirani sources, deterministic condensers and very strong extractors, joint with P. Pudlák.
arXiv

The layer complexity of Arthur-Merlin-like communication.
arXiv

A composition theorem for randomized query complexity via max conflict complexity, joint with T. Lee, M. Santha and S. Sanyal.
arXiv

On the randomised query complexity of composition, joint with T. Lee and M. Santha.
arXiv

Quantum versus classical simultaneity in communication complexity.
arXiv

The communication complexity of the inevitable intersection problem.
arXiv

Entangled simultaneity versus classical interactivity in communication complexity.
arXiv

On the joint entropy of d-wise-independent variables, joint with P. Pudlák.
arXiv

Equality, revisited, joint with R. C. Bottesch and H. Klauck.
arXiv

Correlation in hard distributions in communication complexity, joint with R. C. Bottesch and H. Klauck.
arXiv

On the role of shared randomness in simultaneous communication, joint with M. Bavarian and T. Ito.
arXiv ECCC

En route to the log-rank conjecture: new reductions and equivalent formulations, joint with S. Lovett.
ECCC

Partition expanders, joint with P. Pudlák.
arXiv ECCC

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture, joint with O. Meir, O. Weinstein and A. Wigderson.
ECCC

Shared randomness and quantum communication in the multi-party model, joint with T. Ito and G. Wang.
arXiv ECCC

A tail bound for read-k families of functions, joint with S. Lovett, M. Saks and S. Srinivasan.
arXiv ECCC

Pseudorandom generators for read-once ACC₀, joint with S. Lovett and S. Srinivasan.

Quantum money with classical verification.
arXiv

Quantum fingerprints that keep secrets, joint with T. Ito.
arXiv ECCC

A separation of NP and co-NP in multi-party communication complexity, joint with A. Sherstov.
arXiv ECCC

Classical interaction cannot replace quantum non-locality.
arXiv

Quantum predictive learning and communication complexity with single input.
arXiv

Exponential separation of quantum and classical non-interactive multi-party communication complexity, joint with P. Pudlák.
arXiv ECCC

Simultaneous communication protocols with quantum and classical messages, joint with O. Regev and R. de Wolf.
arXiv

Quantum algorithms for evaluating min-max trees, joint with R. Cleve and D. L. Yeung.
arXiv

Classical interaction cannot replace a quantum message.
arXiv ECCC

Entanglement-resistant two-prover interactive proof systems and non-adaptive private information retrieval systems, joint with R. Cleve and R. Jain.
arXiv

Exponential separations for one-way quantum communication complexity, with applications to cryptography, joint with J. Kempe, I. Kerenidis, R. Raz and R. de Wolf.
arXiv

On the role of shared entanglement.
arXiv

Strengths and weaknesses of quantum fingerprinting, joint with J. Kempe and R. de Wolf.
arXiv

Bounded-error quantum state identification and exponential separations in communication complexity, joint with J. Kempe, O. Regev and R. de Wolf.
arXiv

Quantum communication cannot simulate a public coin, joint with J. Kempe and R. de Wolf.
arXiv

PExact = Exact learning, joint with A. Owshanko.

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

PAC = PAExact and other equivalent models in learning, joint with N. Bshouty.

Optimally-smooth adaptive boosting and application to agnostic learning.

On boosting with optimal poly-bounded distributions, joint with N. Bshouty.