An additive combinatorics approach to the log-rank conjecture in communication complexity

Eli Ben‐Sasson, Shachar Lovett, Noga Ron‐Zewi

Type: Preprint

Publication Date: 2011-11-25

Citations: 7

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	An additive combinatorics approach to the log-rank conjecture in communication complexity	2011	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+ PDF Chat	An Additive Combinatorics Approach Relating Rank to Communication Complexity	2014	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+ PDF Chat	An Additive Combinatorics Approach Relating Rank to Communication Complexity	2012	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+	A Note on the LogRank Conjecture in Communication Complexity	2023	Vince Grolmusz
+	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
+ PDF Chat	A Note on the LogRank Conjecture in Communication Complexity	2023	Vince Grolmusz
+	Refuting approaches to the log-rank conjecture for XOR functions	2023	Hamed Hatami Kaave Hosseini Shachar Lovett Anthony Ostuni
+	On Rank vs. Communication Complexity	1994	Noam Nisan Avi Wigderson
+	On the ?log rank?-conjecture in communication complexity	1995	Ran Raz Boris Spieker
+	En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations	2014	Dmitry Gavinsky Shachar Lovett
+	Log-rank and lifting for AND-functions	2020	Alexander Knop Shachar Lovett Sam McGuire Weiqiang Yuan
+	Matrix discrepancy and the log-rank conjecture	2023	Benny Sudakov István Tomon
+	Log-rank and lifting for AND-functions	2021	Alexander Knop Shachar Lovett Sam McGuire Weiqiang Yuan
+ PDF Chat	None	2017	Shachar Lovett
+ PDF Chat	Quantum Log-Approximate-Rank Conjecture is Also False	2019	Anurag Anshu Naresh Goud Boddu Dave Touchette
+	Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols	2018	Lijie Chen Ruosong Wang
+ PDF Chat	Exponential Separation between Quantum Communication and Logarithm of Approximate Rank	2019	Makrand Sinha Ronald de Wolf
+ PDF Chat	Structure in Communication Complexity and Constant-Cost Complexity Classes	2024	Hamed Hatami Pooya Hatami
+ PDF Chat	An XOR Lemma for Deterministic Communication Complexity	2024	S. Purushothaman Iyer Anup Rao

Works That Cite This (7)

Action	Title	Year	Authors
+ PDF Chat	Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition	2013	Khodakhast Bibak
+ PDF Chat	New bounds for matching vector families	2013	Abhishek Bhowmick Zeev Dvir Shachar Lovett
+ PDF Chat	An Additive Combinatorics Approach Relating Rank to Communication Complexity	2012	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+	Additive combinatorics with a view towards computer science and cryptography: An exposition	2011	Khodakhast Bibak
+ PDF Chat	None	2015	Shachar Lovett
+	New Lower Bounds for Matching Vector Codes	2012	Abhishek Bhowmick Zeev Dvir Shachar Lovett
+	New Lower Bounds for Matching Vector Codes	2012	Abhishek Bhowmick Zeev Dvir Shachar Lovett

Works Cited by This (5)

Action	Title	Year	Authors
+	Rank and chromatic number of a graph	1997	Andreı̌ Kotlov
+	A New Proof of Szemer�di's Theorem for Arithmetic Progressions of Length Four	1998	W. T. Gowers
+	Equivalence of polynomial conjectures in additive combinatorics.	2010	Shachar Lovett
+ PDF Chat	A Note on Freĭman's Theorem in Vector Spaces	2007	Tom Sanders
+ PDF Chat	An equivalence between inverse sumset theorems and inverse conjectures for the<i>U</i><sup>3</sup>norm	2010	Ben Green Terence Tao