«FEB
MAR
MAY »
17
2019
2020
2021 »
97 captures
3 Oct 19 - 1 Jul 23
Close
Help
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
Communication complexity of inevitable intersection
.
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
0
, 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
.