Document Open Access Logo

Equivalence of Systematic Linear Data Structures and Matrix Rigidity

Authors Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.35.pdf
  • Filesize: 0.57 MB
  • 20 pages

Document Identifiers

Author Details

Sivaramakrishnan Natarajan Ramamoorthy
  • University of Washington, Seattle, USA
Cyrus Rashtchian
  • University of California, San Diego, USA

Funding

  • Natarajan Ramamoorthy, Sivaramakrishnan: Supported by the National Science Foundation under agreement CCF-1420268.

Acknowledgements

We thank Paul Beame, Sajin Koroth, Pavel Hrubeš, Pavel Pudlák, Anup Rao, Makrand Sinha, Amir Yehudayoff and Sergey Yekhanin for useful discussions. Special thanks to Paul, Anup, Makrand and Amir for the encouragement to write up these results.

Cite AsGet BibTex

Sivaramakrishnan Natarajan Ramamoorthy and Cyrus Rashtchian. Equivalence of Systematic Linear Data Structures and Matrix Rigidity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.35

Abstract

Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong lower bounds for linear data structures would imply new bounds for rigid matrices. However, their result utilizes an algorithm that requires an NP oracle, and hence, the rigid matrices are not explicit. In this work, we derive an equivalence between rigidity and the systematic linear model of data structures. For the n-dimensional inner product problem with m queries, we prove that lower bounds on the query time imply rigidity lower bounds for the query set itself. In particular, an explicit lower bound of ω(n/r log m) for r redundant storage bits would yield better rigidity parameters than the best bounds due to Alon, Panigrahy, and Yekhanin. We also prove a converse result, showing that rigid matrices directly correspond to hard query sets for the systematic linear model. As an application, we prove that the set of vectors obtained from rank one binary matrices is rigid with parameters matching the known results for explicit sets. This implies that the vector-matrix-vector problem requires query time Ω(n^(3/2)/r) for redundancy r ≥ √n in the systematic linear model, improving a result of Chakraborty, Kamma, and Larsen. Finally, we prove a cell probe lower bound for the vector-matrix-vector problem in the high error regime, improving a result of Chattopadhyay, Koucký, Loff, and Mukhopadhyay.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cell probe models and lower bounds
  • Theory of computation → Circuit complexity
Keywords
  • matrix rigidity
  • systematic linear data structures
  • cell probe model
  • communication complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Pankaj K. Agarwal. Geometric Range searching. In CRC Handbook of Computational Geometry. CRC, 1997. Google Scholar
  2. Miklós Ajtai. A Lower Bound for Finding Predecessors in Yao’s Cell Probe Model. Combinatorica, 8(3), 1988. Google Scholar
  3. Josh Alman and Ryan Williams. Probabilistic Rank and Matrix Rigidity. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 641-652. ACM, 2017. Google Scholar
  4. Noga Alon and Gil Cohen. On Rigid Matrices and U-Polynomials. Computational Complexity, 24(4):851-879, December 2015. Google Scholar
  5. Noga Alon, Rina Panigrahy, and Sergey Yekhanin. Deterministic Approximation Algorithms for the Nearest Codeword Problem. In APPROX '09 / RANDOM '09, pages 339-351, 2009. Google Scholar
  6. V. L. Artazarov, E. A. Dinic, D. A. Kronrod, and I. A. Faradzev. On Economical Construction of the Transitive Closure of a Directed Graph. Soviet Math. Dokl., 11:1209-1210, 1970. Google Scholar
  7. Joshua Brody and Kasper Green Larsen. Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures. Theory of Computing, 11(19):471-489, 2015. Google Scholar
  8. Diptarka Chakraborty, Lior Kamma, and Kasper Green Larsen. Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication. In Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1297-1306, 2018. Google Scholar
  9. Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Simulation Beats Richness: New Data-Structure Lower Bounds. In Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1013-1020, 2018. Google Scholar
  10. Raphaël Clifford, Allan Grønlund, and Kasper Green Larsen. New Unconditional Hardness Results for Dynamic and Online Problems. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 1089-1107, 2015. Google Scholar
  11. Henry Corrigan-Gibbs and Dmitry Kogan. The Function-Inversion Problem: Barriers and Opportunities. Electronic Colloquium on Computational Complexity (ECCC), 25:182, 2018. Google Scholar
  12. Zeev Dvir and Benjamin Edelman. Matrix Rigidity and the Croot-Lev-Pach Lemma. arXiv preprint, 2017. URL: http://arxiv.org/abs/1708.01646.
  13. Zeev Dvir, Alexander Golovnev, and Omri Weinstein. Static Data Structure Lower Bounds Imply Rigidity. In Proc. 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 967-978, 2019. see https://arxiv.org/abs/1811.02725v3. URL: https://doi.org/10.1145/3313276.3316348.
  14. Zeev Dvir and Allen Liu. Fourier and Circulant Matrices Are Not Rigid. In 34th Computational Complexity Conference (CCC 2019), volume 137, pages 17:1-17:23, 2019. Google Scholar
  15. Michael Fredman and Michael Saks. The Cell Probe Complexity of Dynamic Data Structures. In ACM Symposium on Theory of Computing (STOC), 1989. Google Scholar
  16. Joel Friedman. A Note on Matrix Rigidity. Combinatorica, 13(2):235-239, June 1993. Google Scholar
  17. Anna Gál and Peter Bro Miltersen. The Cell Probe Complexity of Succinct Data Structures. Theoretical Computer Science, 379(3):405-417, 2007. Google Scholar
  18. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In Proc. 47th Annual ACM Symposium on Theory of Computing (STOC), pages 21-30, 2015. Google Scholar
  19. Stasys Jukna and Georg Schnitger. Min-Rank Conjecture for Log-Depth Circuits. Journal of Computer and System Sciences, 77(6):1023-1038, 2011. Google Scholar
  20. Kasper Green Larsen. Higher Cell Probe Lower Bounds for Evaluating Polynomials. In FOCS, pages 293-301. IEEE Computer Society, 2012. Google Scholar
  21. Kasper Green Larsen. The Cell Probe Complexity of Dynamic Range Counting. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 85-94, 2012. Google Scholar
  22. Kasper Green Larsen, Omri Weinstein, and Huacheng Yu. Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. In Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 978-989, 2018. Google Scholar
  23. Kasper Green Larsen and Ryan Williams. Faster Online Matrix-Vector Multiplication. In Proc. 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2182-2189, 2017. Google Scholar
  24. Satyanarayana V. Lokam. Complexity Lower Bounds Using Linear Algebra. Foundations and Trends® in Theoretical Computer Science, 4(1–2):1-155, 2009. URL: https://doi.org/10.1561/0400000011.
  25. Peter Bro Miltersen. Lower Bounds for Union-Split-Find Related Problems on Random Access Machines. In Proceedings of the 26th Annual Symposium on the Theory of Computing, pages 625-634, New York, May 1994. ACM Press. Google Scholar
  26. Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On Data Structures and Asymmetric Communication Complexity. Journal of Computer and System Sciences, 57(1):37-49, 1998. Google Scholar
  27. Rina Panigrahy, Kunal Talwar, and Udi Wieder. Lower Bounds on Near Neighbor Search via Metric Expansion. In Proc. 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 805-814, 2010. Google Scholar
  28. Mihai Pǎtraşcu. Unifying the Landscape of Cell-Probe Lower Bounds. SIAM Journal on Computing, 40(3):827-847, 2011. See also FOCS'08, URL: https://arxiv.org/abs/1010.3783.
  29. Mihai Pǎtraşcu and Erik D. Demaine. Logarithmic Lower Bounds in the Cell-Probe Model. SIAM Journal on Computing, 35(4):932-963, 2006. See also STOC'04, SODA'04. Google Scholar
  30. Mihai Pǎtraşcu and Mikkel Thorup. Higher Lower Bounds for Near-Neighbor and Further Rich Problems. SIAM Journal on Computing, 39(2):730-741, 2010. See also FOCS'06. Google Scholar
  31. Pavel Pudlák, Vojtech Rödl, and Jirí Sgall. Boolean Circuits, Tensor Ranks, and Communication Complexity. SIAM Journal on Computing, 26(3):605-633, 1997. Google Scholar
  32. Anup Rao and Amir Yehudayoff. Communication Complexity. preprint at URL: https://homes.cs.washington.edu/~anuprao/pubs/book.pdf.
  33. M.A. Shokrollahi, D.A. Spielman, and V. Stemann. A Remark on Matrix Rigidity. Information Processing Letters, 64(6):283-285, 1997. URL: https://doi.org/10.1016/S0020-0190(97)00190-7.
  34. Amir Shpilka and Amir Yehudayoff. Arithmetic Circuits: A Survey of Recent Results and Open Questions. Foundations and Trendsregistered in Theoretical Computer Science, 5(3-4):207-388, 2010. Google Scholar
  35. Leslie G. Valiant. Graph-Theoretic Arguments in Low-Level Complexity. In Jozef Gruska, editor, Mathematical Foundations of Computer Science, pages 162-176, 1977. Google Scholar
  36. Leslie G. Valiant. Why Is Boolean Complexity Theory Difficult? In Poceedings of the London Mathematical Society Symposium on Boolean Function Complexity, pages 84-94, New York, NY, USA, 1992. Cambridge University Press. URL: http://dl.acm.org/citation.cfm?id=167687.167712.
  37. Emanuele Viola. On the Power of Small-Depth Computation. Foundations and Trendsregistered in Theoretical Computer Science, 5(1):1-72, 2009. Google Scholar
  38. Emanuele Viola. Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC), 25:186, 2018. Google Scholar
  39. Henning Wunderlich. On a Theorem of Razborov. Computational Complexity, 21(3):431-477, 2012. Google Scholar
  40. Andrew Yao. Should Tables be Sorted? JACM: Journal of the ACM, 28, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact