Visible Rank and Codes with Locality
by Omar Alrabiah and Venkatesan Guruswami
Theory of Computing, Volume 22(2098), pp. 1-32, 2026
Bibliography with links to cited articles
[1] Noga Alon, Igor Balla, Lior Gishboliner, Adva Mond, and Frank Mousset: The minrank of random graphs over arbitrary fields. Israel J. Math., 235(1):63–77, 2020. [doi:10.1007/s11856-019-1945-8]
[2] Noga Alon and Eyal Lubetzky: The Shannon capacity of a graph and the independence numbers of its powers. IEEE Trans. Inform. Theory, 52(5):2172–2176, 2006. [doi:10.1109/TIT.2006.872856]
[3] Omar Alrabiah and Venkatesan Guruswami: Visible rank and codes with locality. In Proc. 25th Internat. Conf. on Randomization and Computation (RANDOM’21), pp. 57:1–18. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPICS.APPROX/RANDOM.2021.57]
[4] Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar: A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation. In Proc. 55th STOC, pp. 1438–1448. ACM Press, 2023. [doi:10.1145/3564246.3585143, arXiv:2308.15403]
[5] Ziv Bar-Yossef, Yitzhak Birk, T. S. Jayram, and Tomer Kol: Index coding with side information. IEEE Trans. Inform. Theory, 57(3):1479–1494, 2011. Preliminary version in FOCS’06. [doi:10.1109/TIT.2010.2103753]
[6] Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proc. 43rd STOC, pp. 519–528. ACM Press, 2011. [doi:10.1145/1993636.1993705]
[7] Arnab Bhattacharyya, Sivakanth Gopi, and Avishay Tal: Lower bounds for 2-query LCCs over large alphabet. In Proc. 21st Internat. Workshop on Randomization and Computation (RANDOM’17), pp. 30:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.APPROX-RANDOM.2017.30]
[8] Zeev Dvir: Incidence theorems and their applications. Found. Trends Theor. Comp. Sci., 6(4):257–393, 2012. [doi:10.1561/0400000056]
[9] Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, and Avi Wigderson: Spanoids – An abstraction of spanning structures, and a barrier for LCCs. SIAM J. Comput., 49(3):465–496, 2020. [doi:10.1137/19M124647X]
[10] Zeev Dvir, Shubhangi Saraf, and Avi Wigderson: Improved rank bounds for design matrices and a new proof of Kelly’s theorem. Forum of Mathematics, Sigma, 2(e4):1–24, 2014. [doi:10.1017/fms.2014.2]
[11] Zeev Dvir, Shubhangi Saraf, and Avi Wigderson: Superquadratic lower bound for 3-query locally correctable codes over the reals. Theory of Computing, 13(11):1–36, 2017. [doi:10.4086/toc.2017.v013a011]
[12] Zeev Dvir and Amir Shpilka: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput., 36(5), 2007. Preliminary version in STOC’05. [doi:10.1137/05063605X]
[13] Arman Fazeli, Alexander Vardy, and Eitan Yaakobi: Codes for distributed PIR with low storage overhead. In Proc. 2015 Internat. Symp. on Information Theory (ISIT’15), pp. 2852–2856. IEEE Comp. Soc., 2015. [doi:10.1109/ISIT.2015.7282977]
[14] Mathew C. Francis, Dalu Jacob, and Satyabrata Jana: Uniquely restricted matchings in interval graphs. SIAM J. Discr. Math., 32(1):148–172, 2018. [doi:10.1137/16M1074631]
[15] S. Luna Frank-Fischer, Venkatesan Guruswami, and Mary Wootters: Locality via partially lifted codes. In Proc. 21st Internat. Workshop on Randomization and Computation (RANDOM’17), pp. 43:1–17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.APPROX-RANDOM.2017.43]
[16] Harold N. Gabow, Haim Kaplan, and Robert E. Tarjan: Unique maximum matching algorithms. J. Algorithms, 40(2):159–183, 2001. Preliminary version in STOC’99. [doi:10.1006/jagm.2001.1167]
[17] Oded Goldreich, Howard Karloff, Leonard J Schulman, and Luca Trevisan: Lower bounds for linear locally decodable codes and private information retrieval. Comput. Complexity, 15(3):263–296, 2006. [doi:10.1007/s00037-006-0216-3]
[18] Alexander Golovnev, Oded Regev, and Omri Weinstein: The minrank of random graphs. IEEE Trans. Inform. Theory, 64(11):6990–6995, 2018. [doi:10.1109/TIT.2018.2810384]
[19] Martin Charles Golumbic, Tirza Hirst, and Moshe Lewenstein: Uniquely restricted matchings. Algorithmica, 31(2):139–154, 2001. [doi:10.1007/s00453-001-0004-z]
[20] Parikshit Gopalan, Cheng Huang, Huseyin Simitci, and Sergey Yekhanin: On the locality of codeword symbols. IEEE Trans. Inform. Theory, 58(11):6925–6934, 2012. [doi:10.1109/TIT.2012.2208937]
[21] Sivakanth Gopi: Locality in coding theory. Ph. D. thesis, Princeton University, 2018. Available at Princeton.
[22] Alan Guo, Swastik Kopparty, and Madhu Sudan: New affine-invariant codes from lifting. In Proc. 4th Innovations in Theoret. Comp. Sci. Conf. (ITCS’13), pp. 529–540. ACM Press, 2013. [doi:10.1145/2422436.2422494]
[23] Willem H. Haemers: On some problems of Lovász concerning the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(2):231–232, 1979. [doi:10.1109/TIT.1979.1056027]
[24] Thanh Minh Hoang, Meena Mahajan, and Thomas Thierauf: On the bipartite unique perfect matching problem. In Proc. 33rd Internat. Colloq. on Automata, Languages, and Programming (ICALP’06), pp. 453–464. Springer, 2006. [doi:10.1007/11786986_40]
[25] Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin: Erasure coding in windows azure storage. In Proc. 2012 USENIX Annual Technical Conference, General Track (UATC’12). USENIX Association, 2012. Available at USENIX ATC 2012.
[26] Eran Iceland and Alex Samorodnitsky: On coset leader graphs of structured linear codes. Discr. Comput. Geom., 63(3):560–576, 2020. [doi:10.1007/s00454-019-00129-3]
[27] Sankeeth Rao Karingula, Alexander Vardy, and Mary Wootters: Lower bounds on the redundancy of linear codes with disjoint repair groups. In Proc. 2022 Internat. Symp. on Information Theory (ISIT’22), pp. 975–979. IEEE Comp. Soc., 2022. preliminary version by Mary Wootters (2016) available at the author’s website. [doi:10.1109/ISIT50566.2022.9834487]
[28] Jonathan Katz and Luca Trevisan: On the efficiency of local decoding procedures for error-correcting codes. In Proc. 32nd STOC, pp. 80–86. ACM Press, 2000. [doi:10.1145/335305.335315]
[29] Iordanis Kerenidis and Ronald de Wolf: Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. System Sci., 69(3):395–420, 2004. Preliminary version in STOC’03. [doi:10.1016/j.jcss.2004.04.007]
[30] Ray Li and Mary Wootters: Lifted multiplicity codes and the disjoint repair group property. IEEE Trans. Inform. Theory, 67(2):716–725, 2021. [doi:10.1109/TIT.2020.3034962]
[31] Ray Li and Mary Wootters: Improved batch code lower bounds. In Proc. 2022 Internat. Symp. on Information Theory (ISIT’22), pp. 1596–1599. IEEE Comp. Soc., 2022. [doi:10.1109/ISIT50566.2022.9834625]
[32] László Lovász: Communication complexity: A survey. Technical Report CS-TR-204-89, Princeton University, 1989. Available at Princeton.
[33] Sounaka Mishra: On the maximum uniquely restricted matching for bipartite graphs. Electron. Notes Discrete Math., 37:345–350, 2011. [doi:10.1016/j.endm.2011.05.059]
[34] C. Ramya: Recent progress on matrix rigidity – A survey, 2020. [arXiv:2009.09460]
[35] Sankeerth Rao and Alexander Vardy: Lower bound on the redundancy of PIR codes, 2016. [arXiv:1605.01869]
[36] Maheswaran Sathiamoorthy, Megasthenis Asteris, Dimitris Papailiopoulos, Alexandros Dimakis, Ramkumar Vadali, Scott Chen, and Dhruba Borthakur: XORing elephants: Novel erasure codes for big data. Proc. VLDB Endow., 6(5):325–336, 2013. [doi:10.14778/2535573.2488339]
[37] Michael Sipser and Daniel A. Spielman: Expander codes. IEEE Trans. Inform. Theory, 42(6):1710–1722, 1996. [doi:10.1109/18.556667]
[38] Maguy Trefois: Topics in combinatorial matrix theory. Ph. D. thesis, Catholic University of Louvain, 2016. Available at Catholic University of Louvain.
[39] Maguy Trefois and Jean-Charles Delvenne: Zero forcing number, constrained matchings and strong structural controllability. Lin. Alg. Appl., 484:199–218, 2015. [doi:10.1016/j.laa.2015.06.025]
[40] Leslie G. Valiant: Graph-theoretic arguments in low-level complexity. In Proc. Internat. Symp. Math. Foundations of Comp. Sci. (MFCS’77), pp. 162–176. Springer, 1977. [doi:10.1007/3-540-08353-7_135]
[41] David Woodruff: New lower bounds for general locally decodable codes. Electron. Colloq. Comput. Complexity, TR07-006, 2007. [ECCC]
[42] David P. Woodruff: A quadratic lower bound for three-query linear locally decodable codes over any field. J. Comput. Sci. Technol., 27(4):678–686, 2012. [doi:10.1007/s11390-012-1254-8]
[43] Sergey Yekhanin: Locally decodable codes. Found. Trends Theor. Comp. Sci., 6(3):139–255, 2012. [doi:10.1561/0400000030]
[44] David Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number. In Proc. 38th STOC, pp. 681–690. ACM Press, 2006. [doi:10.1145/1132516.1132612]
