Search

Dmitry Gavinsky

Preprints & Publications

A composition theorem for randomized query complexity via max conflict complexity
Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal, Theory of Computing, 18 (2022)
Publication

Entangled simultaneity versus classical interactivity in communication complexity
Dmitry Gavinsky, IEEE Transactions on Information Theory (2020)
Publication

Bare quantum simultaneity versus classical interactivity in communication complexity
Dmitry Gavinsky, ACM Symposium of Theory of Computing (2020)
Publication

Santha-Vazirani sources, deterministic condensers and very strong extractors
Dmitry Gavinsky, Pavel Pudlák, Theory of Computing Systems (2020)
Publication

Quantum versus classical simultaneity in communication complexity
Dmitry Gavinsky, IEEE Transactions on Information Theory, Number: 65, 10, 6466-6483 (2019)
Publication

A Composition Theorem for Randomized Query Complexity
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, arXiv: 1706.00335v2 (2017)
Publication

Quadratically Tight Relations for Randomized Query Complexity
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs, International Computer Science Symposium in Russia, arXiv: 1708.00822v1 (2017)
Publication

On the Joint Entropy of d-Wise-Independent Variables
Dmitry Gavinsky, Pavel Pudlak, Commentationes Mathematicae Universitatis Carolinae, Number: 3, 57, 333-343 (2016)
Publication

Entangled simultaneity versus classical interactivity in communication complexity
Dmitry Gavinsky, Proceedings of ACM STOC, Number: 48 (2016)
Publication

Correlation in Hard Distributions in Communication Complexity
Ralph C. Bottesch, Dmitry Gavinsky, Hartmut Klauck, Proceedings of The International Workshop On Randomization and Computation, Number: 19, 544-572 (2015)
Publication

Equality, Revisited
Ralph C. Bottesch, Dmitry Gavinsky, Hartmut Klauck, International Symposium on Mathematical Foundations of Computer Science (MFCS), Number: 40, 2, 127-138 (2015)
Publication

Browser not supported

Modern websites need modern browsers

To enjoy the full experience, please upgrade your browser

Try this browser
A pie chart showing the count of papers with CQT co-authors in 2024 by journal impact factor

Publications by CQT researchers during 2024 by journal impact factor (IF)​

A pie chart showing the nationality of CQTians by region of the world.

Nationalities of CQT staff and students as of 31 Dec 2024​

A pie chart showing the count of CQTians by categories

Count of CQT staff and students as of 31 Dec 2024​

*Admin count includes only staff directly employed within the Centre. HR, IT and procurement is supported by additional staff working across University centres.