Document Open Access Logo

The Orthogonal Vectors Conjecture for Branching Programs and Formulas

Authors Daniel M. Kane, Richard Ryan Williams

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.48.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Daniel M. Kane
  • CSE and Mathematics, UC San Diego, La Jolla CA, USA
Richard Ryan Williams
  • EECS and CSAIL, MIT, 32 Vassar St., Cambridge MA, USA

Funding

  • Kane, Daniel M.: Supported by NSF Award CCF-1553288 (CAREER) and a Sloan Research Fellowship.
  • Williams, Richard Ryan: Supported by NSF CCF-1741615 (CAREER: Common Links in Algorithms and Complexity). Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Cite AsGet BibTex

Daniel M. Kane and Richard Ryan Williams. The Orthogonal Vectors Conjecture for Branching Programs and Formulas. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.48

Abstract

In the Orthogonal Vectors (OV) problem, we wish to determine if there is an orthogonal pair of vectors among n Boolean vectors in d dimensions. The OV Conjecture (OVC) posits that OV requires n^{2-o(1)} time to solve, for all d=omega(log n). Assuming the OVC, optimal time lower bounds have been proved for many prominent problems in P, such as Edit Distance, Frechet Distance, Longest Common Subsequence, and approximating the diameter of a graph. We prove that OVC is true in several computational models of interest: - For all sufficiently large n and d, OV for n vectors in {0,1}^d has branching program complexity Theta~(n * min(n,2^d)). In particular, the lower and upper bounds match up to polylog factors. - OV has Boolean formula complexity Theta~(n * min(n,2^d)), over all complete bases of O(1) fan-in. - OV requires Theta~(n * min(n,2^d)) wires, in formulas comprised of gates computing arbitrary symmetric functions of unbounded fan-in. Our lower bounds basically match the best known (quadratic) lower bounds for any explicit function in those models. Analogous lower bounds hold for many related problems shown to be hard under OVC, such as Batch Partial Match, Batch Subset Queries, and Batch Hamming Nearest Neighbors, all of which have very succinct reductions to OV. The proofs use a certain kind of input restriction that is different from typical random restrictions where variables are assigned independently. We give a sense in which independent random restrictions cannot be used to show hardness, in that OVC is false in the "average case" even for AC^0 formulas: For all p in (0,1) there is a delta_p > 0 such that for every n and d, OV instances with input bits independently set to 1 with probability p (and 0 otherwise) can be solved with AC^0 formulas of O(n^{2-delta_p}) size, on all but a o_n(1) fraction of instances. Moreover, lim_{p - > 1}delta_p = 1.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • fine-grained complexity
  • orthogonal vectors
  • branching programs
  • symmetric functions
  • Boolean formulas

Metrics

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

References

  1. Pairwise comparison of bit vectors, January 20, 2017. URL: https://cstheory.stackexchange.com/questions/37361/pairwise-comparison-of-bit-vectors.
  2. Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Or Zamir. Subtree Isomorphism Revisited. In SODA, pages 1256-1271, 2016. Google Scholar
  3. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight Hardness Results for LCS and Other Sequence Similarity Measures. In FOCS, pages 59-78, 2015. Google Scholar
  4. Amir Abboud and Virginia Vassilevska Williams. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In FOCS, pages 434-443, 2014. Google Scholar
  5. Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In SODA, pages 377-391. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  6. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of Faster Alignment of Sequences. In ICALP, pages 39-51, 2014. Google Scholar
  7. Amir Abboud, Richard Ryan Williams, and Huacheng Yu. More Applications of the Polynomial Method to Algorithm Design. In SODA, pages 218-230, 2015. Google Scholar
  8. Thomas Dybdahl Ahle, Rasmus Pagh, Ilya P. Razenshteyn, and Francesco Silvestri. On the Complexity of Inner Product Similarity Join. In PODS, pages 151-164, 2016. Google Scholar
  9. Arturs Backurs and Piotr Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). In STOC, pages 51-58, 2015. Google Scholar
  10. Arturs Backurs and Piotr Indyk. Which Regular Expression Patterns Are Hard to Match? In FOCS, pages 457-466, 2016. Google Scholar
  11. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-Case Fine-Grained Hardness. IACR Cryptology ePrint Archive, 2017:202, 2017. URL: http://eprint.iacr.org/2017/202.
  12. Allan Borodin. On Relating Time and Space to Size and Depth. SIAM J. Comput., 6(4):733-744, 1977. URL: http://dx.doi.org/10.1137/0206054.
  13. Karl Bringmann. Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In FOCS, pages 661-670, 2014. Google Scholar
  14. Karl Bringmann and Marvin Künnemann. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In FOCS, pages 79-97, 2015. Google Scholar
  15. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. JoCG, 7(2):46-76, 2016. Google Scholar
  16. Kevin Buchin, Maike Buchin, Maximilian Konzack, Wolfgang Mulzer, and André Schulz. Fine-grained analysis of problems on curves. In EuroCG, Lugano, Switzerland, 2016. Google Scholar
  17. Massimo Cairo, Roberto Grossi, and Romeo Rizzi. New Bounds for Approximating Extremal Distances in Undirected Graphs. In SODA, pages 363-376, 2016. Google Scholar
  18. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The Complexity of Satisfiability of Small Depth Circuits. In Parameterized and Exact Complexity (IWPEC), pages 75-85, 2009. Google Scholar
  19. Timothy M. Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. In SODA, pages 1246-1255, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch87.
  20. Krishnendu Chatterjee, Wolfgang Dvorák, Monika Henzinger, and Veronika Loitzenbauer. Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction. In LICS, pages 197-206, 2016. Google Scholar
  21. Shiva Chaudhuri and Jaikumar Radhakrishnan. Deterministic restrictions in circuit complexity. In STOC, pages 30-36. ACM, 1996. Google Scholar
  22. Lijie Chen and Ryan Williams. An Equivalence Class for Orthogonal Vectors. In SODA, page to appear, 2019. Google Scholar
  23. Jacob Evald and Søren Dahlgaard. Tight Hardness Results for Distance and Centrality Problems in Constant Degree Graphs. CoRR, abs/1609.08403, 2016. URL: http://arxiv.org/abs/1609.08403.
  24. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and R. Ryan Williams. Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. In SODA, pages 2162-2181, 2017. Google Scholar
  25. Johan Håstad. Almost Optimal Lower Bounds for Small Depth Circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 6-20, 1986. Google Scholar
  26. Costas S. Iliopoulos and Jakub Radoszewski. Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties. In 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, June 27-29, 2016, Tel Aviv, Israel, pages 8:1-8:12, 2016. Google Scholar
  27. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  28. Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer-Verlag, 2012. Google Scholar
  29. V. M. Khrapchenko. The complexity of the realization of symmetrical functions by formulae. Mathematical notes of the Academy of Sciences of the USSR, 11(1):70-76, 1972. Google Scholar
  30. Marvin Künnemanm, Ramamohan Paturi, and Stefan Schneider. On the Fine-grained Complexity of One-Dimensional Dynamic Programming. CoRR, abs/1703.00941, 2017. URL: http://arxiv.org/abs/1703.00941.
  31. Nancy A. Lynch. Log Space Recognition and Translation of Parenthesis Languages. J. ACM, 24(4):583-590, 1977. URL: http://dx.doi.org/10.1145/322033.322037.
  32. E. I. Nechiporuk. On a Boolean function. Doklady of the Academy of Sciences of the USSR, 169(4):765-766, 1966. English translation in Soviet Mathematics Doklady 7:4, pages 999-1000. Google Scholar
  33. Paul Pritchard. A Fast Bit-Parallel Algorithm for Computing the Subset Partial Order. Algorithmica, 24(1):76-86, 1999. Google Scholar
  34. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515-524, 2013. Google Scholar
  35. Michael Wehar. Intersection Non-Emptiness for Tree-Shaped Finite Automata. Available at http://michaelwehar.com/documents/TreeShaped.pdf, February 2016.
  36. Richard Ryan Williams. Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 2:1-2:17, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.2.
  37. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. See also ICALP'04. Google Scholar
  38. Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In SODA, pages 1867-1877, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.135.
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