default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDDmitry Gavinsky
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2021
[j20]Dmitry Gavinsky
:
Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity. IEEE Trans. Inf. Theory 67(10): 6583-6605 (2021)- [j19]Dmitry Gavinsky:
The Layer Complexity of Arthur-Merlin-like Communication. Adv. Math. Commun. 17: 1-28 (2021) - 2020
- [j18]Dmitry Gavinsky:
The communication complexity of the inevitable intersection problem. Chic. J. Theor. Comput. Sci. 2020 (2020) - [j17]Dmitry Gavinsky, Pavel Pudlák:
Santha-Vazirani sources, deterministic condensers and very strong extractors. Theory Comput. Syst. 64(6): 1140-1154 (2020) - [j16]Dmitry Gavinsky:
Entangled Simultaneity Versus Classical Interactivity in Communication Complexity. IEEE Trans. Inf. Theory 66(7): 4641-4651 (2020) - [c25]Dmitry Gavinsky:
Bare quantum simultaneity versus classical interactivity in communication complexity. STOC 2020: 401-411
2010 – 2019
- 2019
- [j15]Dmitry Gavinsky:
Quantum Versus Classical Simultaneity in Communication Complexity. IEEE Trans. Inf. Theory 65(10): 6466-6483 (2019) - [c24]Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal:
A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. ICALP 2019: 64:1-64:13 - [i42]Dmitry Gavinsky, Pavel Pudlák:
Santha-Vazirani sources, deterministic condensers and very strong extractors. CoRR abs/1907.04640 (2019) - [i41]Dmitry Gavinsky:
Bare quantum simultaneity versus classical interactivity in communication complexity. CoRR abs/1911.01381 (2019) - 2018
- [i40]Dmitry Gavinsky, Troy Lee, Miklos Santha:
On the randomised query complexity of composition. CoRR abs/1801.02226 (2018) - [i39]Dmitry Gavinsky:
The layer complexity of Arthur-Merlin-like communication. CoRR abs/1811.04010 (2018) - [i38]Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal:
A composition theorem for randomized query complexity via max conflict complexity. CoRR abs/1811.10752 (2018) - 2017
- [j14]Dmitry Gavinsky, Pavel Pudlák:
Partition Expanders. Theory Comput. Syst. 60(3): 378-395 (2017) - [j13]Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson:
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. SIAM J. Comput. 46(1): 114-131 (2017) - [c23]Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal:
A Composition Theorem for Randomized Query Complexity. FSTTCS 2017: 10:1-10:13 - [i37]Dmitry Gavinsky:
Quantum versus classical simultaneity in communication complexity. CoRR abs/1705.07211 (2017) - [i36]Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal:
A Composition Theorem for Randomized Query Complexity. CoRR abs/1706.00335 (2017) - [i35]Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs:
Quadratically Tight Relations for Randomized Query Complexity. CoRR abs/1708.00822 (2017) - [i34]Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal:
A Composition Theorem for Randomized Query complexity. Electron. Colloquium Comput. Complex. TR17 (2017) - [i33]Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs:
Quadratically Tight Relations for Randomized Query Complexity. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [c22]Dmitry Gavinsky:
Entangled simultaneity versus classical interactivity in communication complexity. STOC 2016: 877-884 - [i32]Dmitry Gavinsky:
Entangled simultaneity versus classical interactivity in communication complexity. CoRR abs/1602.05059 (2016) - [i31]Dmitry Gavinsky:
Communication complexity of inevitable intersection. CoRR abs/1611.08842 (2016) - 2015
- [j12]Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A tail bound for read-k families of functions. Random Struct. Algorithms 47(1): 99-108 (2015) - [c21]Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck:
Correlation in Hard Distributions in Communication Complexity. APPROX-RANDOM 2015: 544-572 - [c20]Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck:
Equality, Revisited. MFCS (2) 2015: 127-138 - [i30]Dmitry Gavinsky, Pavel Pudlák:
On the Entropy of Locally-Independent Bernoulli Trials. CoRR abs/1503.08154 (2015) - [i29]Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck:
Correlation in Hard Distributions in Communication Complexity. CoRR abs/1508.05189 (2015) - [i28]Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito:
On the Role of Shared Randomness in Simultaneous Communication. CoRR abs/1508.06395 (2015) - [i27]Ralph C. Bottesch, Dmitry Gavinsky, Hartmut Klauck:
Equality, Revisited. CoRR abs/1511.01211 (2015) - [i26]Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito:
On the Role of Shared Randomness in Simultaneous Communication. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c19]Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito:
On the Role of Shared Randomness in Simultaneous Communication. ICALP (1) 2014: 150-162 - [c18]Dmitry Gavinsky, Shachar Lovett:
En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations. ICALP (1) 2014: 514-524 - [c17]Dmitry Gavinsky, Pavel Pudlák:
Partition Expanders. STACS 2014: 325-336 - [c16]Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson:
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. STOC 2014: 213-222 - [i25]Dmitry Gavinsky, Pavel Pudlák:
Partition Expanders. CoRR abs/1401.5781 (2014) - [i24]Dmitry Gavinsky, Pavel Pudlák:
Partition Expanders. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j11]Dmitry Gavinsky, Tsuyoshi Ito:
Quantum fingerprints that keep secrets. Quantum Inf. Comput. 13(7-8): 583-606 (2013) - [c15]Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang:
Shared Randomness and Quantum Communication in the Multi-party Model. CCC 2013: 34-43 - [i23]Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang:
Shared Randomness and Quantum Communication in the Multi-Party Model. Electron. Colloquium Comput. Complex. TR13 (2013) - [i22]Dmitry Gavinsky, Shachar Lovett:
En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations. Electron. Colloquium Comput. Complex. TR13 (2013) - [i21]Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson:
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j10]Dmitry Gavinsky:
Quantum predictive learning and communication complexity with single input. Quantum Inf. Comput. 12(7-8): 575-588 (2012) - [c14]Dmitry Gavinsky:
Quantum Money with Classical Verification. CCC 2012: 42-52 - [c13]Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan:
Pseudorandom Generators for Read-Once ACC^0. CCC 2012: 287-297 - [i20]Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A Tail Bound for Read-k Families of Functions. CoRR abs/1205.1478 (2012) - [i19]Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang:
Shared Randomness and Quantum Communication in the Multi-Party Model. CoRR abs/1210.1535 (2012) - [i18]Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A Tail Bound for Read-k Families of Functions. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [c12]Dmitry Gavinsky, Martin Roetteler, Jérémie Roland:
Quantum Algorithm for the Boolean Hidden Shift Problem. COCOON 2011: 158-167 - [i17]Dmitry Gavinsky, Martin Roetteler, Jérémie Roland:
Quantum algorithm for the Boolean hidden shift problem. CoRR abs/1103.3017 (2011) - [i16]Dmitry Gavinsky:
Quantum Money with Classical Verification. CoRR abs/1109.0372 (2011) - 2010
- [j9]Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. Theory Comput. 6(1): 227-245 (2010) - [c11]Dmitry Gavinsky:
Quantum Predictive Learning and Communication Complexity with Single Input. COLT 2010: 207-217 - [i15]Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. CoRR abs/1004.0817 (2010) - [i14]Dmitry Gavinsky, Tsuyoshi Ito:
Quantum Fingerprints that Keep Secrets. CoRR abs/1010.5342 (2010) - [i13]Dmitry Gavinsky, Tsuyoshi Ito:
Quantum Fingerprints that Keep Secrets. Electron. Colloquium Comput. Complex. TR10 (2010) - [i12]Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j8]Richard Cleve, Dmitry Gavinsky, Rahul Jain:
Entanglement-resistant two-prover interactive proof systems and non-adaptive pir's. Quantum Inf. Comput. 9(7&8): 648-656 (2009) - [j7]Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf:
Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. SIAM J. Comput. 39(1): 1-24 (2009) - 2008
- [j6]Dmitry Gavinsky, Oded Regev, Ronald de Wolf:
Simultaneous Communication Protocols with Quantum and Classical Messages. Chic. J. Theor. Comput. Sci. 2008 (2008) - [j5]Dmitry Gavinsky:
On the role of shared entanglement. Quantum Inf. Comput. 8(1): 82-95 (2008) - [j4]Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf:
Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. SIAM J. Comput. 38(5): 1695-1708 (2008) - [c10]Dmitry Gavinsky, Pavel Pudlák:
Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity. CCC 2008: 332-339 - [c9]Dmitry Gavinsky:
Classical interaction cannot replace a quantum message. STOC 2008: 95-102 - [c8]Richard Cleve, Dmitry Gavinsky, David L. Yonge-Mallo:
Quantum Algorithms for Evaluating Min-MaxTrees. TQC 2008: 11-15 - [i11]Dmitry Gavinsky:
Quantum Predictive Learning and Communication Complexity with Single Input. CoRR abs/0812.3429 (2008) - 2007
- [c7]Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf:
Exponential separations for one-way quantum communication complexity, with applications to cryptography. STOC 2007: 516-525 - [i10]Dmitry Gavinsky:
Classical Interaction Cannot Replace a Quantum Message. CoRR abs/quant-ph/0703215 (2007) - [i9]Dmitry Gavinsky:
Classical Interaction Cannot Replace a Quantum Message. Electron. Colloquium Comput. Complex. TR07 (2007) - [i8]Dmitry Gavinsky, Pavel Pudlák:
Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c6]Dmitry Gavinsky, Julia Kempe, Ronald de Wolf:
Strengths and Weaknesses of Quantum Fingerprinting. CCC 2006: 288-298 - [c5]Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf:
Bounded-error quantum state identification and exponential separations in communication complexity. STOC 2006: 594-603 - [i7]Dmitry Gavinsky, Julia Kempe, Ronald de Wolf:
Strengths and Weaknesses of Quantum Fingerprinting. CoRR abs/quant-ph/0603173 (2006) - [i6]Dmitry Gavinsky:
On the Role of Shared Entanglement. CoRR abs/quant-ph/0604052 (2006) - [i5]Dmitry Gavinsky, Julia Kempe, Ronald de Wolf:
Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function. CoRR abs/quant-ph/0607174 (2006) - [i4]Dmitry Gavinsky, Julia Kempe, Ronald de Wolf:
Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [i3]Dmitry Gavinsky:
A Note on Shared Randomness and Shared Entanglement in Communication. CoRR abs/quant-ph/0505088 (2005) - [i2]Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf:
Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. CoRR abs/quant-ph/0511013 (2005) - 2004
- [j3]Dmitry Gavinsky:
Quantum solution to the hidden subgroup problem for poly-near-hamiltonian groups. Quantum Inf. Comput. 4(3): 229-235 (2004) - [c4]Dmitry Gavinsky, Avi Owshanko:
PExact = Exact Learning. COLT 2004: 200-209 - [i1]Dmitry Gavinsky, Julia Kempe, Ronald de Wolf:
Quantum Communication Cannot Simulate a Public Coin. CoRR quant-ph/0411051 (2004) - 2003
- [j2]Dmitry Gavinsky:
Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning. J. Mach. Learn. Res. 4: 101-117 (2003) - 2002
- [j1]Nader H. Bshouty, Dmitry Gavinsky:
On Boosting with Polynomially Bounded Distributions. J. Mach. Learn. Res. 3: 483-506 (2002) - [c3]Dmitry Gavinsky:
Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning. ALT 2002: 98-112 - [c2]Nader H. Bshouty, Dmitry Gavinsky:
PAC = PAExact and Other Equivalent Models in Learning. FOCS 2002: 167-176 - 2001
- [c1]Nader H. Bshouty, Dmitry Gavinsky:
On Boosting with Optimal Poly-Bounded Distributions. COLT/EuroCOLT 2001: 490-506
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-01-21 00:02 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
