Better Gap-Hamming Lower Bounds via Better Round Elimination
From MaRDI portal
Publication:3588428
DOI10.1007/978-3-642-15369-3_36zbMath1305.68091OpenAlexW2129719258WikidataQ59792824 ScholiaQ59792824MaRDI QIDQ3588428
Joshua Brody, Amit Chakrabarti, Thomas Vidick, Oded Regev, Ronald de Wolf
Publication date: 10 September 2010
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://authors.library.caltech.edu/93990/
Related Items
Sketching and Embedding are Equivalent for Norms ⋮ Anticoncentration and the Exact Gap-Hamming Problem ⋮ One-Sided Error Communication Complexity of Gap Hamming Distance. ⋮ Property testing lower bounds via communication complexity