Volume 76, Issue 3

November 2016

Special Issue: Information Complexity and Applications

Issue Editors:

10 articles in this issue

Guest Editorial for Information Complexity and Applications
Mark Braverman
David P. Woodruff
EditorialNotes 05 July 2016 Pages: 595 - 596
Common Information and Unique Disjointness
Gábor Braun
Sebastian Pokutta
OriginalPaper 22 February 2016 Pages: 597 - 629
Deterministic Compression with Uncertain Priors
Elad Haramaty
Madhu Sudan
OriginalPaper 04 January 2016 Pages: 630 - 653
Superlinear Lower Bounds for Multipass Graph Processing
Venkatesan Guruswami
Krzysztof Onak
OriginalPaper 21 March 2016 Pages: 654 - 683
Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication
Mika Göös
Toniann Pitassi
Thomas Watson
OriginalPaper 19 January 2016 Pages: 684 - 719
A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity
Rahul Jain
Attila Pereszlényi
Penghui Yao
OriginalPaper 18 December 2015 Pages: 720 - 748
Towards a Reverse Newman’s Theorem in Interactive Information Complexity
Joshua Brody
Harry Buhrman
Nikolay Vereshchagin
OriginalPaper Open access 12 January 2016 Pages: 749 - 781
Direct Sum Fails for Zero-Error Average Communication
Gillat Kol
Shay Moran
Amir Yehudayoff
OriginalPaper 28 March 2016 Pages: 782 - 795
Certifying Equality With Limited Interaction
Joshua Brody
Amit Chakrabarti
Grigory Yaroslavtsev
OriginalPaper 19 May 2016 Pages: 796 - 845
A Discrepancy Lower Bound for Information Complexity
Mark Braverman
Omri Weinstein
OriginalPaper 30 November 2015 Pages: 846 - 864

Search