Recent advances on the log-rank conjecture in communication complexity

Shachar Lovett

Type: Preprint

Publication Date: 2014-03-31

Citations: 2

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Recent advances on the log-rank conjecture in communication complexity	2014	Shachar Lovett
+	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
+	A Note on the LogRank Conjecture in Communication Complexity	2023	Vince Grolmusz
+	An additive combinatorics approach to the log-rank conjecture in communication complexity	2011	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+ PDF Chat	A Note on the LogRank Conjecture in Communication Complexity	2023	Vince Grolmusz
+	An additive combinatorics approach to the log-rank conjecture in communication complexity	2011	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+ PDF Chat	Structure in Communication Complexity and Constant-Cost Complexity Classes	2024	Hamed Hatami Pooya Hatami
+ PDF Chat	An Additive Combinatorics Approach Relating Rank to Communication Complexity	2014	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+	The Corruption Bound, Log Rank, and Communication Complexity	2014	Adi Shraibman
+	Log-rank and lifting for AND-functions	2021	Alexander Knop Shachar Lovett Sam McGuire Weiqiang Yuan
+	A direct proof for Lovett's bound on the communication complexity of low rank matrices.	2014	Thomas Rothvoß
+	Information complexity and applications	2019	Mark Braverman
+	A direct proof for Lovett's bound on the communication complexity of low rank matrices	2014	Thomas Rothvoß
+	Communication Complexity (for Algorithm Designers)	2015	Tim Roughgarden
+	Communication Complexity Lower Bounds by Polynomials	1999	Harry Buhrman Ronald de Wolf
+ PDF Chat	Hadamard tensors and lower bounds on multiparty communication complexity	2012	Jeff Ford Anna Gál
+	A discrepancy lower bound for information complexity	2011	Mark Braverman Omri Weinstein
+	A discrepancy lower bound for information complexity	2011	Mark Braverman Omri Weinstein
+ PDF Chat	An XOR Lemma for Deterministic Communication Complexity	2024	S. Purushothaman Iyer Anup Rao

Works That Cite This (2)

Action	Title	Year	Authors
+ PDF Chat	Fourier Sparsity of GF(2) Polynomials	2016	Hing Yin Tsang Ning Xie Shengyu Zhang
+	On 2-level polytopes arising in combinatorial settings	2017	Manuel Aprile Alfonso Cevallos Yuri Faenza

Works Cited by This (13)

Action	Title	Year	Authors
+	On the parity complexity measures of Boolean functions	2010	Zhiqiang Zhang Yaoyun Shi
+ PDF Chat	Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models	2011	Ming Lam Leung Yang Li Shengyu Zhang
+	The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear	1992	Alexander Razborov
+	Rank and chromatic number of a graph	1997	Andreı̌ Kotlov
+ PDF Chat	An Additive Combinatorics Approach Relating Rank to Communication Complexity	2012	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+ PDF Chat	Complexity measures of sign matrices	2007	Nati Linial Shahar Mendelson Gideon Schechtman Adi Shraibman
+	A Bound for the Chromatic Number of a Graph	1976	Cyriel van Nuffelen
+ PDF Chat	On the Bogolyubov–Ruzsa lemma	2012	Tom Sanders
+	On the communication complexity of XOR functions	2009	Ashley Montanaro Tobias J. Osborne
+	On the ?log rank?-conjecture in communication complexity	1995	Ran Raz Boris Spieker