Amir Abboud
ABSTRACT
Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove conditional lower bounds in order to advance our understanding of the class P. The vast majority of these lower bounds are based on one of three famous hypotheses: the 3-SUM conjecture, the APSP conjecture, and the Strong Exponential Time Hypothesis. Only circumstantial evidence is known in support of these hypotheses, and no formal relationship between them is known. In hopes of obtaining "less conditional" and therefore more reliable lower bounds, we consider the conjecture that at least one of the above three hypotheses is true. We design novel reductions from 3-SUM, APSP, and CNF-SAT, and derive interesting consequences of this very plausible conjecture, including: Tight n3-o(1) lower bounds for purely-combinatorial problems about the triangles in unweighted graphs. New n1-o(1) lower bounds for the amortized update and query times of dynamic algorithms for single-source reachability, strongly connected components, and Max-Flow. New n1.5-o(1) lower bound for computing a set of n st-maximum-flow values in a directed graph with n nodes and ~O(n) edges. There is a hierarchy of natural graph problems on n nodes with complexity nc for c ∈ (2,3).
Only slightly non-trivial consequences of this conjecture were known prior to our work. Along the way we also obtain new conditional lower bounds for the Single-Source-Max-Flow problem.
- Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, apsp and diameter. SODA, 2015. Google Scholar
Digital Library
- Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In ICALP (1), pages 1--12, 2013. Google ScholarDigital Library
- Amir Abboud, Kevin Lewi, and Ryan Williams. Losing weight by gaining edges. In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8--10, 2014. Proceedings, pages 1--12, 2014.Google Scholar
- Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. SODA, 2015. Google ScholarDigital Library
- Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. FOCS, 2014. Google ScholarDigital Library
- Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In ICALP (1), pages 39--51, 2014.Google Scholar
- Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8--11, 2014, Proceedings, Part I, pages 114--125, 2014.Google Scholar
- Boris Aronov and Sariel Har-Peled. On approximating the depth and related problems. In Proc. SODA, 2005. Google ScholarDigital Library
- I. Baran, E.D. Demaine, and M. Patraşcu. Subquadratic algorithms for $3$sum. Algorithmica, 50(4):584--596, 2008. Google ScholarDigital Library
- Gill Barequet and Sariel Har-Peled. Some variants of polygonal containment and minimum hausdorff distance undertranslation are 3SUM-hard. In Proc. SODA, pages 862--863, 1999. Google ScholarDigital Library
- M. A. Bender, J. T. Fineman, S. Gilbert, and R. E. Tarjan. A new approach to incremental cycle detection and related problems. CoRR, abs/1112.0784, 2011.Google Scholar
- Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. Listing triangles. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8--11, 2014, Proceedings, Part I, pages 223--234, 2014.Google Scholar
- Michele Borassi, Pierluigi Crescenzi, and Michel Habib. Into the square - on the complexity of quadratic-time solvable problems. CoRR, abs/1407.4972, 2014.Google Scholar
- David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, convolutions, and X+Y. Algorithmica, 69(2):294--314, 2014.Google ScholarCross Ref
- Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. FOCS, 2014. Google ScholarDigital Library
- Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16--20 July 2006, Prague, Czech Republic, pages 252--260, 2006. Google ScholarDigital Library
- Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In Parameterized and Exact Computation, pages 75--85. Springer, 2009. Google ScholarDigital Library
- T. M. Chan. Dynamic subgraph connectivity with geometric applications. SIAM J. Comput., 36(3):681--694, 2006. Google ScholarDigital Library
- T. M. Chan, M. Patraşcu, and L. Roditty. Dynamic connectivity: Connecting to networks and geometry. In FOCS, pages 95--104, 2008. Google ScholarDigital Library
- K. Chen, P. Hsu, and K. Chao. Approximate matching for run-length encoded strings is 3sum-hard. In CPM, pages 168--179. Springer, 2009. Google ScholarDigital Library
- Otfried Cheong, Alon Efrat, and Sariel Har-Peled. On finding a guard that sees most and a shop that sells most. In Proc. SODA, pages 1098--1107, 2004. Google ScholarDigital Library
- Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung. Graph connectivities, network coding, and expander graphs. SIAM Journal on Computing, 42(3):733--751, 2013.Google ScholarCross Ref
- Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6--8 June 2011, pages 273--282, 2011. Google ScholarDigital Library
- Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast Hamiltonicity checking via bases of perfect matchings. In STOC, pages 301--310, 2013. Google ScholarDigital Library
- Evgeny Dantsin and Alexander Wolpert. On moderately exponential time for SAT. In Proc. 13th International Conference on Theory and Applications of Satisfiability Testing, pages 313--325, 2010. Google ScholarDigital Library
- Mark de Berg, Marko de Groot, and Mark H. Overmars. Perfect binary space partitions. Computational Geometry: Theory and Applications, 7(81):81--91, 1997. Google ScholarDigital Library
- C. Demetrescu and G. F. Italiano. Fully dynamic transitive closure: Breaking through the o(n2) barrier. In Proc. FOCS, volume 41, pages 381--389, 2000. Google ScholarDigital Library
- R. Duan. New data structures for subgraph connectivity. In ICALP (1), pages 201--212, 2010. Google ScholarDigital Library
- F. Eisenbrand and F. Grandoni. On the complexity of fixed parameter clique and dominating set. Theor. Comp. Sci., 326(1--3):57--67, 2004. Google ScholarDigital Library
- J. Erickson. New lower bounds for convex hull problems in odd dimensions. SIAM Journal on Computing, 28(4):1198--1214, 1999. Google ScholarDigital Library
- S. Even and Y. Shiloach. An on-line edge-deletion problem. J. ACM, 28(1):1--4, 1981. Google ScholarDigital Library
- D. Frigioni and G. F. Italiano. Dynamically switching vertices in planar graphs. Algorithmica, 28(1):76--103, 2000.Google ScholarDigital Library
- A. Gajentaan and M. Overmars. On a class of o(n2) problems in computational geometry. Computational Geometry, 5(3):165--185, 1995. Google ScholarDigital Library
- François Le Gall. Powers of tensors and fast matrix multiplication. CoRR, abs/1401.7714, 2014.Google Scholar
- B. Haeupler, T. Kavitha, R. Mathew, S. Sen, and R. E. Tarjan. Incremental cycle detection, topological ordering, and strong component maintenance. ACM Transactions on Algorithms, 8(1):3, 2012. Google ScholarDigital Library
- Jianxiu Hao and James B. Orlin. A faster algorithm for finding the minimum cut in a directed graph. J. Algorithms, 17(3):424--446, 1994. Google ScholarDigital Library
- Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi, and Anand Bhalgat. An o(mn) gomory-hu tree construction algorithm for unweighted graphs. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11--13, 2007, pages 605--614, 2007. Google ScholarDigital Library
- Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 674--683, 2014. Google ScholarDigital Library
- E. A. Hirsch. Two new upper bounds for SAT. In Proc. SODA, pages 521--530, 1998. Google ScholarDigital Library
- R. Impagliazzo and R. Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367--375, 2001. Google ScholarDigital Library
- R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512--530, 2001. Google ScholarDigital Library
- G. F. Italiano. Finding paths and deleting edges in directed acyclic graphs. Inf. Process. Lett., 28(1):5--11, 1988. Google ScholarDigital Library
- Z. Jafargholi and E. Viola. 3sum, 3xor, triangles. Electronic Colloquium on Computational Complexity (ECCC), 20:9, 2013.Google Scholar
- Hamidreza Jahanjou, Eric Miles, and Emanuele Viola. Local reductions. CoRR, abs/1311.3171, 2013.Google Scholar
- Allan Grønlund Jørgensen and Seth Pettie. Threesomes, degenerates, and love triangles. CoRR, abs/1404.0799, 2014.Google Scholar
- Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 302--311, 1984. Google ScholarDigital Library
- Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5--7, 2014, pages 217--226, 2014. Google ScholarDigital Library
- Tsvi Kopelowitz, Seth Pettie, and Ely Porat. 3sum hardness in (dynamic) data structures. CoRR, abs/1407.6756, 2014.Google Scholar
- J. Lacki. Improved deterministic algorithms for decremental reachability and strongly connected components. ACM Transactions on Algorithms, 9(3):27, 2013. Google ScholarDigital Library
- Jakub Lacki, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Single source - all sinks max flows in planar digraphs. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20--23, 2012, pages 599--608, 2012. Google ScholarDigital Library
- Yin Tat Lee and Aaron Sidford. Following the path of least resistance : An o(m sqrt(n)) algorithm for the minimum cost flow problem. CoRR, abs/1312.6713, 2013.Google Scholar
- Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs on bounded treewidth are probably optimal. In SODA, pages 777--789, 2011. Google ScholarDigital Library
- J. Erickson M. Soss and M. H. Overmars. Preprocessing chains for fast dihedral rotations is hard or even impossible. Computational Geometry: Theory and Applications, 26(3):235--246, 2002. Google ScholarDigital Library
- Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26--29 October, 2013, Berkeley, CA, USA, pages 253--262, 2013. Google ScholarDigital Library
- Yurii Nesterov and A. S. Nemirovskii. An interior-point method for generalized linear-fractional programming. Math. Program., 69:177--204, 1995. Google ScholarDigital Library
- R. Paturi, P. Pudlák, M. E. Saks, and F. Zane. An improved exponential-time algorithm for k-SAT. J. ACM, 52(3):337--364, 2005. Google ScholarDigital Library
- M. Patraşcu. Towards polynomial lower bounds for dynamic problems. In STOC, pages 603--610, 2010. Google ScholarDigital Library
- M. Patraşcu and E. D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput., 35(4):932--963, 2006. Google ScholarDigital Library
- M. Patraşcu and R. Williams. On the possibility of faster SAT algorithms. In Proc. SODA, pages 1065--1075, 2010. Google ScholarDigital Library
- L. Roditty. Decremental maintenance of strongly connected components. In SODA, pages 1143--1150, 2013. Google ScholarDigital Library
- L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC '13, pages 515--524, New York, NY, USA, 2013. ACM. Google ScholarDigital Library
- L. Roditty and U. Zwick. Improved dynamic reachability algorithms for directed graphs. In FOCS, pages 679--689, 2002. Google ScholarDigital Library
- Liam Roditty and Uri Zwick. On dynamic shortest paths problems. In ESA, pages 580--591, 2004.Google ScholarCross Ref
- P. Sankowski. Dynamic transitive closure via dynamic matrix inverse. In Proc. FOCS, volume 45, pages 509--517, 2004. Google ScholarDigital Library
- U. Schöning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In Proc. FOCS, pages 410--414, 1999. Google ScholarDigital Library
- Jonah Sherman. Nearly maximum flows in nearly linear time. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26--29 October, 2013, Berkeley, CA, USA, pages 263--269, 2013. Google ScholarDigital Library
- Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13--16, 2004, pages 81--90, 2004. Google ScholarDigital Library
- M. Thorup. Near-optimal fully-dynamic graph connectivity. In STOC, pages 343--350, 2000. Google ScholarDigital Library
- V. Vassilevska and R. Williams. Finding, minimizing, and counting weighted subgraphs. In Proc. STOC, pages 455--464, 2009. Google ScholarDigital Library
- R. Williams. A new algorithm for optimal constraint satisfaction and its implications. In Proc. ICALP, pages 1227--1237, 2004.Google ScholarCross Ref
- Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 664--673, 2014. Google ScholarDigital Library
- Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In SODA, pages 1867--1877, 2014. Google ScholarDigital Library
- V. Vassilevska Williams and R. Williams. Subcubic equivalences between path, matrix and triangle problems. In Proc. FOCS, pages 645--654, 2010. Google ScholarDigital Library
- Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 887--898, 2012. Google ScholarDigital Library
Index Terms
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Recommendations
Towards polynomial lower bounds for dynamic problems
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computingWe consider a number of dynamic problems with no known poly-logarithmic upper bounds, and show that they require nΩ(1) time per operation, unless 3SUM has strongly subquadratic algorithms. Our result is modular: (1) We describe a carefully-chosen ...
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove conditional lower bounds in order to advance our understanding of the class P. The vast majority of these lower bounds are based on one of three famous hypotheses: ...
On basing one-way functions on NP-hardness
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingWe consider the possibility of basing one-way functions on NP-Hardness; that is, we study possible reductions from a worst-case decision problem to the task of average-case inverting a polynomial-time computable function f. Our main findings are the ...
Comments