A discrepancy lower bound for information complexity

Mark Braverman, Omri Weinstein

Type: Preprint

Publication Date: 2011-01-01

Citations: 19

DOI: https://doi.org/10.48550/arxiv.1112.2000

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	A discrepancy lower bound for information complexity	2011	Mark Braverman Omri Weinstein
+	Tension Bounds for Information Complexity	2014	Manoj Prabhakaran Vinod M. Prabhakaran
+	Tension Bounds for Information Complexity	2014	Manoj Prabhakaran Vinod M. Prabhakaran
+ PDF Chat	Strong XOR Lemma for Information Complexity	2024	Pachara Sawettamalya Huacheng Yu
+	Strong XOR Lemma for Communication with Bounded Rounds	2022	Huacheng Yu
+	A near-optimal direct-sum theorem for communication complexity	2020	Rahul Jain
+	Recent advances on the log-rank conjecture in communication complexity	2014	Shachar Lovett
+	Recent advances on the log-rank conjecture in communication complexity	2014	Shachar Lovett
+	A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity	2015	Rahul Jain Attila Pereszlényi Penghui Yao
+	A near-optimal direct-sum theorem for communication complexity.	2020	Rahul Jain
+	Near-optimal bounds on bounded-round quantum communication complexity of disjointness	2015	Mark Braverman Ankit Garg Young Kun Ko Jieming Mao Dave Touchette
+	Near-optimal bounds on bounded-round quantum communication complexity of disjointness	2015	Mark Braverman Ankit Garg Young Kun Ko Jieming Mao Dave Touchette
+	Inner Product and Set Disjointness: Beyond Logarithmically Many Parties	2017	Vladimir V. Podolskii Alexander A. Sherstov
+ PDF Chat	Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity	2024	Simon Mackenzie Abdallah Saffidine
+	On the role of private coins in unbounded-round Information Complexity.	2014	Alexander Kozachinsky
+	A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences	2009	Joshua Brody Amit Chakrabarti
+ PDF Chat	A Discrepancy Lower Bound for Information Complexity	2012	Mark Braverman Omri Weinstein
+ PDF Chat	A Discrepancy Lower Bound for Information Complexity	2015	Mark Braverman Omri Weinstein
+ PDF Chat	A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences	2009	Joshua Brody Amit Chakrabarti
+	Trading information complexity for error	2017	Yuval Dagan Yuval Filmus Hamed Hatami Yaqiao Li

Works That Cite This (5)

Action	Title	Year	Authors
+	A strong direct product theorem in terms of the smooth rectangle bound	2012	Rahul Jain Penghui Yao
+	Small Value Parallel Repetition for General Games	2015	Mark Braverman Ankit Garg
+	Superlinear lower bounds for multipass graph processing	2012	Venkatesan Guruswami Krzysztof Onak
+ PDF Chat	Superlinear Lower Bounds for Multipass Graph Processing	2013	Venkatesan Guruswami Krzysztof Onak
+	Information Complexity and the Quest for Interactive Compression (A Survey).	2015	Omri Weinstein

Works Cited by This (0)

Action	Title	Year	Authors