The Corruption Bound, Log Rank, and Communication Complexity

Adi Shraibman

Type: Preprint

Publication Date: 2014-01-01

Citations: 0

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

View Publication

Locations

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

Similar Works

Action	Title	Year	Authors
+ PDF Chat	The corruption bound, log-rank, and communication complexity	2018	Adi Shraibman
+	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
+	En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations	2014	Dmitry Gavinsky Shachar Lovett
+	A direct proof for Lovett's bound on the communication complexity of low rank matrices	2014	Thomas Rothvoß
+	A direct proof for Lovett's bound on the communication complexity of low rank matrices.	2014	Thomas Rothvoß
+	On the ?log rank?-conjecture in communication complexity	1995	Ran Raz Boris Spieker
+ PDF Chat	Communication Complexity (for Algorithm Designers)	2016	Tim Roughgarden
+	Communication Complexity (for Algorithm Designers)	2015	Tim Roughgarden
+	An additive combinatorics approach to the log-rank conjecture in communication complexity	2011	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+	An additive combinatorics approach to the log-rank conjecture in communication complexity	2011	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+	Probabilistic rank and matrix rigidity	2017	Josh Alman Ryan Williams
+ PDF Chat	Communication Complexity (for Algorithm Designers)	2016	Tim Roughgarden
+	Communication Complexity	2010	Dömötör Pálvölgyi
+	Communication Complexity	2010	Dömötör Pálvölgyi
+	The Minrank of Random Graphs	2016	Alexander Golovnev Oded Regev Omri Weinstein
+ PDF Chat	An Additive Combinatorics Approach Relating Rank to Communication Complexity	2014	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+	Log-rank and lifting for AND-functions	2021	Alexander Knop Shachar Lovett Sam McGuire Weiqiang Yuan
+	On Rank vs. Communication Complexity	1994	Noam Nisan Avi Wigderson
+	Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound	2014	Gillat Kol Shay Moran Amir Shpilka Amir Yehudayoff

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors