Dmitry Gavinsky

88 papers A* 10A 6B 1Misc 1Journal 63Unranked 7

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Unambiguous Parity-Query Complexity. Random Struct. Algorithms Dmitry Gavinsky
2021	J	`jnl`	Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity. IEEE Trans. Inf. Theory Dmitry Gavinsky
2021	J	`jnl`	The Layer Complexity of Arthur-Merlin-like Communication. Theory Comput. Dmitry Gavinsky
2020	A*	`conf`	Bare quantum simultaneity versus classical interactivity in communication complexity. STOC Dmitry Gavinsky
2020	J	`jnl`	Entangled Simultaneity Versus Classical Interactivity in Communication Complexity. IEEE Trans. Inf. Theory Dmitry Gavinsky
2020	J	`jnl`	Santha-Vazirani sources, deterministic condensers and very strong extractors. Theory Comput. Syst. Dmitry Gavinsky, Pavel Pudlák
2020	J	`jnl`	The communication complexity of the inevitable intersection problem. Chic. J. Theor. Comput. Sci. Dmitry Gavinsky
2019	A*	`conf`	A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. ICALP Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
2019	J	`jnl`	Bare quantum simultaneity versus classical interactivity in communication complexity. CoRR Dmitry Gavinsky
2019	J	`jnl`	Quantum Versus Classical Simultaneity in Communication Complexity. IEEE Trans. Inf. Theory Dmitry Gavinsky
2019	J	`jnl`	Santha-Vazirani sources, deterministic condensers and very strong extractors. CoRR Dmitry Gavinsky, Pavel Pudlák
2018	J	`jnl`	A composition theorem for randomized query complexity via max conflict complexity. CoRR Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
2018	J	`jnl`	On the randomised query complexity of composition. CoRR Dmitry Gavinsky, Troy Lee, Miklos Santha
2018	J	`jnl`	The layer complexity of Arthur-Merlin-like communication. CoRR Dmitry Gavinsky
2017	—	`conf`	A Composition Theorem for Randomized Query Complexity. FSTTCS Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
2017	J	`jnl`	A Composition Theorem for Randomized Query Complexity. CoRR Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
2017	J	`jnl`	A Composition Theorem for Randomized Query complexity. Electron. Colloquium Comput. Complex. Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
2017	J	`jnl`	Partition Expanders. Theory Comput. Syst. Dmitry Gavinsky, Pavel Pudlák
2017	J	`jnl`	Quadratically Tight Relations for Randomized Query Complexity. CoRR Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2017	J	`jnl`	Quadratically Tight Relations for Randomized Query Complexity. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2017	J	`jnl`	Quantum versus classical simultaneity in communication complexity. CoRR Dmitry Gavinsky
2017	J	`jnl`	Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. SIAM J. Comput. Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
2016	J	`jnl`	Communication complexity of inevitable intersection. CoRR Dmitry Gavinsky
2016	A*	`conf`	Entangled simultaneity versus classical interactivity in communication complexity. STOC Dmitry Gavinsky
2016	J	`jnl`	Entangled simultaneity versus classical interactivity in communication complexity. CoRR Dmitry Gavinsky
2015	J	`jnl`	A tail bound for read- Random Struct. Algorithms Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
2015	—	`conf`	Correlation in Hard Distributions in Communication Complexity. APPROX-RANDOM Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
2015	J	`jnl`	Correlation in Hard Distributions in Communication Complexity. CoRR Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
2015	—	`conf`	Equality, Revisited. MFCS (2) Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
2015	J	`jnl`	Equality, Revisited. CoRR Ralph C. Bottesch, Dmitry Gavinsky, Hartmut Klauck
2015	J	`jnl`	On the Entropy of Locally-Independent Bernoulli Trials. CoRR Dmitry Gavinsky, Pavel Pudlák
2015	J	`jnl`	On the Role of Shared Randomness in Simultaneous Communication. CoRR Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito
2015	J	`jnl`	On the Role of Shared Randomness in Simultaneous Communication. Electron. Colloquium Comput. Complex. Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito
2014	—	`conf`	En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations. ICALP (1) Dmitry Gavinsky, Shachar Lovett
2014	—	`conf`	On the Role of Shared Randomness in Simultaneous Communication. ICALP (1) Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito
2014	A	`conf`	Partition Expanders. STACS Dmitry Gavinsky, Pavel Pudlák
2014	J	`jnl`	Partition Expanders. CoRR Dmitry Gavinsky, Pavel Pudlák
2014	J	`jnl`	Partition Expanders. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Pavel Pudlák
2014	A*	`conf`	Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. STOC Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
2013	J	`jnl`	En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Shachar Lovett
2013	J	`jnl`	Quantum fingerprints that keep secrets. Quantum Inf. Comput. Dmitry Gavinsky, Tsuyoshi Ito
2013	J	`jnl`	Shared Randomness and Quantum Communication in the Multi-Party Model. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang
2013	A	`conf`	Shared Randomness and Quantum Communication in the Multi-party Model. CCC Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang
2013	J	`jnl`	Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
2012	J	`jnl`	A Tail Bound for Read-k Families of Functions CoRR Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
2012	J	`jnl`	A Tail Bound for Read-k Families of Functions. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
2012	A	`conf`	Pseudorandom Generators for Read-Once ACC^0. CCC Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan
2012	A	`conf`	Quantum Money with Classical Verification. CCC Dmitry Gavinsky
2012	J	`jnl`	Quantum predictive learning and communication complexity with single input. Quantum Inf. Comput. Dmitry Gavinsky
2012	J	`jnl`	Shared Randomness and Quantum Communication in the Multi-Party Model CoRR Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang
2011	Misc	`conf`	Quantum Algorithm for the Boolean Hidden Shift Problem. COCOON Dmitry Gavinsky, Martin Roetteler, Jérémie Roland
2011	J	`jnl`	Quantum Money with Classical Verification CoRR Dmitry Gavinsky
2011	J	`jnl`	Quantum algorithm for the Boolean hidden shift problem CoRR Dmitry Gavinsky, Martin Roetteler, Jérémie Roland
2010	J	`jnl`	A Separation of NP and coNP in Multiparty Communication Complexity CoRR Dmitry Gavinsky, Alexander A. Sherstov
2010	J	`jnl`	A Separation of NP and coNP in Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Alexander A. Sherstov
2010	J	`jnl`	A Separation of NP and coNP in Multiparty Communication Complexity. Theory Comput. Dmitry Gavinsky, Alexander A. Sherstov
2010	J	`jnl`	Quantum Fingerprints that Keep Secrets CoRR Dmitry Gavinsky, Tsuyoshi Ito
2010	J	`jnl`	Quantum Fingerprints that Keep Secrets. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Tsuyoshi Ito
2010	A*	`conf`	Quantum Predictive Learning and Communication Complexity with Single Input. COLT Dmitry Gavinsky
2009	J	`jnl`	Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. SIAM J. Comput. Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf
2009	J	`jnl`	Entanglement-resistant two-prover interactive proof systems and non-adaptive pir's. Quantum Inf. Comput. Richard Cleve, Dmitry Gavinsky, Rahul Jain
2008	A*	`conf`	Classical interaction cannot replace a quantum message. STOC Dmitry Gavinsky
2008	J	`jnl`	Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. SIAM J. Comput. Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf
2008	A	`conf`	Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity. CCC Dmitry Gavinsky, Pavel Pudlák
2008	J	`jnl`	On the role of shared entanglement. Quantum Inf. Comput. Dmitry Gavinsky
2008	—	`conf`	Quantum Algorithms for Evaluating Min-MaxTrees. TQC Richard Cleve, Dmitry Gavinsky, David L. Yonge-Mallo
2008	J	`jnl`	Quantum Predictive Learning and Communication Complexity with Single Input. CoRR Dmitry Gavinsky
2008	J	`jnl`	Simultaneous Communication Protocols with Quantum and Classical Messages. Chic. J. Theor. Comput. Sci. Dmitry Gavinsky, Oded Regev, Ronald de Wolf
2007	J	`jnl`	Classical Interaction Cannot Replace a Quantum Message CoRR Dmitry Gavinsky
2007	J	`jnl`	Classical Interaction Cannot Replace a Quantum Message. Electron. Colloquium Comput. Complex. Dmitry Gavinsky
2007	J	`jnl`	Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Pavel Pudlák
2007	A*	`conf`	Exponential separations for one-way quantum communication complexity, with applications to cryptography. STOC Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf
2006	A*	`conf`	Bounded-error quantum state identification and exponential separations in communication complexity. STOC Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf
2006	J	`jnl`	Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function CoRR Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
2006	J	`jnl`	Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
2006	J	`jnl`	On the Role of Shared Entanglement CoRR Dmitry Gavinsky
2006	J	`jnl`	Strengths and Weaknesses of Quantum Fingerprinting CoRR Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
2006	A	`conf`	Strengths and Weaknesses of Quantum Fingerprinting. CCC Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
2005	J	`jnl`	A Note on Shared Randomness and Shared Entanglement in Communication CoRR Dmitry Gavinsky
2005	J	`jnl`	Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity CoRR Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf
2004	A*	`conf`	PExact = Exact Learning. COLT Dmitry Gavinsky, Avi Owshanko
2004	J	`jnl`	Quantum Communication Cannot Simulate a Public Coin CoRR Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
2004	J	`jnl`	Quantum solution to the hidden subgroup problem for poly-near-hamiltonian groups. Quantum Inf. Comput. Dmitry Gavinsky
2003	J	`jnl`	Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning. J. Mach. Learn. Res. Dmitry Gavinsky
2002	J	`jnl`	On Boosting with Polynomially Bounded Distributions. J. Mach. Learn. Res. Nader H. Bshouty, Dmitry Gavinsky
2002	B	`conf`	Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning. ALT Dmitry Gavinsky
2002	A*	`conf`	PAC = PAExact and Other Equivalent Models in Learning. FOCS Nader H. Bshouty, Dmitry Gavinsky
2001	—	`conf`	On Boosting with Optimal Poly-Bounded Distributions. COLT/EuroCOLT Nader H. Bshouty, Dmitry Gavinsky