Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming

DOI10.1007/978-3-642-32512-0_41zbMath1345.68128arXiv1205.0968OpenAlexW2963378100MaRDI QIDQ3167419

Ranganath Kondapally, Zhenghui Wang, Amit Chakrabarti

Publication date: 2 November 2012

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.0968

zbMATH Keywords

orthogonalityinformation complexitycommunication complexitycorruptiongap-Hamming distance

Mathematics Subject Classification ID

Related Items (5)

The Simultaneous Communication of Disjointness with Applications to Data Streams ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Superlinear lower bounds for multipass graph processing ⋮ Information lower bounds via self-reducibility ⋮ Rectangles Are Nonnegative Juntas

This page was built for publication: Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming