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-01-01

Citations: 2

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

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - 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 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
+	On Rank vs. Communication Complexity	1994	Noam Nisan Avi Wigderson
+	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
+ PDF Chat	None	2017	Shachar Lovett
+ PDF Chat	Quantum Log-Approximate-Rank Conjecture is Also False	2019	Anurag Anshu Naresh Goud Boddu Dave Touchette
+	Log-rank and lifting for AND-functions	2021	Alexander Knop Shachar Lovett Sam McGuire Weiqiang Yuan
+ PDF Chat	Structure in Communication Complexity and Constant-Cost Complexity Classes	2024	Hamed Hatami Pooya Hatami
+	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
+	Exponential Separation between Quantum Communication and Logarithm of Approximate Rank	2018	Makrand Sinha de Wolf Ronald

Works That Cite This (2)

Action	Title	Year	Authors
+ 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

Works Cited by This (11)

Action	Title	Year	Authors
+	From affine to two-source extractors via approximate duality	2011	Noga Ron‐Zewi Eli Ben‐Sasson
+	Rank and chromatic number of a graph	1997	Andreı̌ Kotlov
+	A Bound for the Chromatic Number of a Graph	1976	Cyriel van Nuffelen
+	Finite field models in additive combinatorics	2005	Ben Green
+	A statistical theorem of set addition	1994	Antal Balog Endre Szemer�di
+ PDF Chat	Freiman's Theorem in Finite Fields via Extremal Set Theory	2009	Ben Green Terence Tao
+	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
+	A probabilistic technique for finding almost-periods of convolutions	2010	Ernie Croot Olof Sisask
+ PDF Chat	A Note on Freĭman's Theorem in Vector Spaces	2007	Tom Sanders