Tight Lower Bounds for 2-query LCCs over Finite Fields

Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, Shubhangi Saraf

Type: Article

Publication Date: 2011-10-01

Citations: 14

DOI: https://doi.org/10.1109/focs.2011.28

Similar Works

Action	Title	Year	Authors
+	Lower bounds for 2-query LCCs over large alphabet	2016	Arnab Bhattacharyya Sivakanth Gopi Avishay Tal
+ PDF Chat	Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions	2022	Jeremiah Blocki Kuan Cheng Elena Grigorescu Xin Li Yu Zheng Minshen Zhu
+ PDF Chat	Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles	2024	Omar Alrabiah Venkatesan Guruswami
+	Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions	2021	Jeremiah Blocki Kuan Cheng Elena Grigorescu Xin Li Yu Zheng Minshen Zhu
+	Outlaw distributions and locally decodable codes	2016	Jop Briët Zeev Dvir Sivakanth Gopi
+	Outlaw distributions and locally decodable codes	2016	Jop Briët Zeev Dvir Sivakanth Gopi
+	Lower bounds for constant query affine-invariant LCCs and LTCs	2015	Arnab Bhattacharyya Sivakanth Gopi
+	Lower bounds for constant query affine-invariant LCCs and LTCs	2015	Arnab Bhattacharyya Sivakanth Gopi
+ 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
+ PDF Chat	Breaking the quadratic barrier for 3-LCC's over the reals	2014	Zeev Dvir Shubhangi Saraf Avi Wigderson
+	Locally Decodable/Correctable Codes for Insertions and Deletions	2020	Alexander R. Block Jeremiah Blocki Elena Grigorescu Shubhang Kulkarni Minshen Zhu
+ PDF Chat	Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs	2017	Arnab Bhattacharyya Sivakanth Gopi
+	Breaking the quadratic barrier for 3-LCCs over the Reals	2013	Zeev Dvir Shubhangi Saraf Avi Wigderson
+	Breaking the quadratic barrier for 3-LCCs over the Reals	2013	Zeev Dvir Shubhangi Saraf Avi Wigderson
+	Outlaw distributions and locally decodable codes	2017	Jop Briët Zeev Dvir Sivakanth Gopi
+	An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes	2024	Pravesh K. Kothari Peter Manohar
+ PDF Chat	Local Correction of Linear Functions over the Boolean Cube	2024	Prashanth Amireddy Amik Raj Behera Manaswi Paraashar Srikanth Srinivasan Madhu Sudan
+	Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes	2010	Boaz Barak Zeev Dvir Avi Wigderson Amir Yehudayoff
+	Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes	2010	Boaz Barak Zeev Dvir Avi Wigderson Amir Yehudayoff
+	Dense locally testable codes cannot have constant rate and distance	2010	Irit Dinur Tali Kaufman

Works That Cite This (10)

Action	Title	Year	Authors
+	Tight Lower Bounds for 2-query LCCs over Finite Fields	2011	Arnab Bhattacharyya Zeev Dvir Amir Shpilka Shubhangi Saraf
+ PDF Chat	Incidence Theorems and Their Applications	2012	Zeev Dvir
+ PDF Chat	Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition	2013	Khodakhast Bibak
+	Tight lower bounds for 2-query LCCs over finite fields.	2011	Arnab Bhattacharyya Zeev Dvir Shubhangi Saraf Amir Shpilka
+ PDF Chat	IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM	2014	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
+	A Lower Bound for Relaxed Locally Decodable Codes	2019	Tom Gur Oded Lachish
+ PDF Chat	Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs	2017	Arnab Bhattacharyya Sivakanth Gopi
+ PDF Chat	SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY	2014	Albert Ai Zeev Dvir Shubhangi Saraf Avi Wigderson
+ PDF Chat	Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case	2024	Srinivasan Arunachalam João F. Doriguello

Works Cited by This (12)

Action	Title	Year	Authors
+	Sums of Finite Sets	1996	Imre Z. Ruzsa
+	On a question of Erdős and Moser	2005	Benny Sudakov Endre Szemerédi Van H. Vu
+	Tight Lower Bounds for 2-query LCCs over Finite Fields	2011	Arnab Bhattacharyya Zeev Dvir Amir Shpilka Shubhangi Saraf
+	On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry	1983	József Beck
+	A statistical theorem of set addition	1994	Antal Balog Endre Szemer�di
+	On Matrix Rigidity and Locally Self-correctable Codes	2011	Zeev Dvir
+	Perturbed Identity Matrices Have High Rank: Proof and Applications	2008	Noga Alon
+	A New Proof of Szemer�di's Theorem for Arithmetic Progressions of Length Four	1998	W. T. Gowers
+	Exponential lower bound for 2-query locally decodable codes via a quantum argument	2003	Iordanis Kerenidis Ronald de Wolf
+ 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