Breaking the quadratic barrier for 3-LCCs over the Reals

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Type: Preprint

Publication Date: 2013-11-20

Citations: 2

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Breaking the quadratic barrier for 3-LCCs over the Reals	2013	Zeev Dvir Shubhangi Saraf Avi Wigderson
+ PDF Chat	Breaking the quadratic barrier for 3-LCC's over the reals	2014	Zeev Dvir Shubhangi Saraf Avi Wigderson
+ PDF Chat	Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles	2024	Omar Alrabiah Venkatesan Guruswami
+	Lower Bounds for Approximate LDC	2014	Jop Briët Zeev Dvir Guang‐Da Hu Shubhangi Saraf
+	Lower Bounds for Approximate LDC	2014	Jop Briët Zeev Dvir Guang‐Da Hu Shubhangi Saraf
+ PDF Chat	Inapproximability of Sparsest Vector in a Real Subspace	2024	Vijay Bhattiprolu Euiwoong Lee
+ PDF Chat	Local Correction of Linear Functions over the Boolean Cube	2024	Prashanth Amireddy Amik Raj Behera Manaswi Paraashar Srikanth Srinivasan Madhu Sudan
+ PDF Chat	Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs	2024	Pravesh K. Kothari Peter Manohar
+	Tight Lower Bounds for 2-query LCCs over Finite Fields	2011	Arnab Bhattacharyya Zeev Dvir Amir Shpilka Shubhangi Saraf
+	A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2023	Omar Alrabiah Venkatesan Guruswami Pravesh K. Kothari Peter Manohar
+	An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes	2023	Pravesh K. Kothari Peter Manohar
+	Combinatorial lower bounds for 3-query LDCs	2019	Arnab Bhattacharyya L. Sunil Chandran Suprovat Ghoshal
+	An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes	2024	Pravesh K. Kothari Peter Manohar
+	Local Correction of Linear Functions over the Boolean Cube	2024	Prashanth Amireddy Amik Raj Behera Manaswi Paraashar Srikanth Srinivasan Madhu Sudan
+	Globally optimizing small codes in real projective spaces	2019	Dustin G. Mixon Hans Parshall
+	Globally optimizing small codes in real projective spaces	2019	Dustin G. Mixon Hans Parshall
+	Combinatorial lower bounds for 3-query LDCs.	2019	Arnab Bhattacharyya L. Sunil Chandran Suprovat Ghoshal
+	A Lower Bound for Relaxed Locally Decodable Codes	2019	Tom Gur Oded Lachish
+ PDF Chat	Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes	2011	Boaz Barak Zeev Dvir Amir Yehudayoff Avi Wigderson
+	Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes	2010	Boaz Barak Zeev Dvir Avi Wigderson Amir Yehudayoff

Works That Cite This (2)

Action	Title	Year	Authors
+	On Radial Isotropic Position: Theory and Algorithms	2020	Shiri Artstein-Avidan Haim Kaplan Micha Sharir
+	Lower Bounds for Approximate LDC	2014	Jop Briët Zeev Dvir Guang‐Da Hu Shubhangi Saraf

Works Cited by This (5)

Action	Title	Year	Authors
+	Exponential lower bound for 2-query locally decodable codes via a quantum argument	2003	Iordanis Kerenidis Ronald de Wolf
+	On Matrix Rigidity and Locally Self-correctable Codes	2011	Zeev Dvir
+ PDF Chat	Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes	2011	Boaz Barak Zeev Dvir Amir Yehudayoff Avi Wigderson
+	Improved rank bounds for design matrices and a new proof of Kelly's theorem	2012	Zeev Dvir Shubhangi Saraf Avi Wigderson
+ PDF Chat	On a reverse form of the Brascamp-Lieb inequality	1998	Franck Barthe