1.2k citations · 2.5k across the 41 of their papers we have counts for
3 papers · 1 filter
Better Gap-Hamming Lower Bounds via Better Round Elimination
Joshua Brody, Amit Chakrabarti, Oded Regev +2
Gap Hamming Distance is a well-studied problem in communication complexity, in which Alice and Bob have to decide whether the Hamming distance between their respective n-bit inputs…
Quantum Proofs for Classical Theorems
Andrew Drucker, Ronald de Wolf
Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (n…
Non-locality and Communication Complexity
Harry Buhrman, Richard Cleve, Serge Massar +1
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles, like the superposition principle, e…