Towards polynomial lower bounds for dynamic problems

2010/06/05 by Mihai Pǎtraşcu · 7 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Conjecture #Discrete mathematics #Dynamic problem #Graph #Logarithm #Mathematical optimization #Mathematics #Modular design #Optimization and Search Problems #Reduction (mathematics) #Set (abstract data type) #Time complexity #Upper and lower bounds

paper · doi:10.1145/1806689.1806772

openalex publication_date 2010/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We 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 dynamic version of set disjointness (the "multiphase problem"), and conjecture that it requires n^Omega(1) time per operation. All our lower bounds follow by easy reduction. (2) We reduce 3SUM to the multiphase problem. Ours is the first nonalgebraic reduction from 3SUM, and allows 3SUM-hardness results for combinatorial problems. For instance, it implies hardness of reporting all triangles in a graph. (3) It is plausible that an unconditional lower bound for the multiphase problem can be established via a number-on-forehead communication game.

Citations

• Polygon Containment and Translational Min-Hausdorff-Distance between Segment Sets are 3SUM-Hard
• Finding, minimizing, and counting weighted subgraphs
• Dynamic Connectivity: Connecting to Networks and Geometry
• Subquadratic Algorithms for 3SUM
• On a class of O(n2) problems in computational geometry

Cited by

• Consequences of Faster Alignment of Sequences
• Bowties and Hourglasses: Intersections of Double-Wedges (or Stabbing and Avoiding Line Segments)
• Improved Subquadratic 3SUM
• Regularity Lemmas and Combinatorial Algorithms
• On Problems Equivalent to (min,+)-Convolution
• Monochromatic Triangles, Triangle Listing and APSP
• Linear-Space Data Structures for Range Mode Query in Arrays
• 3SUM [wikipedia]

Related

• Popular conjectures imply strong lower bounds for dynamic problems
• Higher Lower Bounds from the 3SUM Conjecture
• New Unconditional Hardness Results for Dynamic and Online Problems
• An Adaptive Step Toward the Multiphase Conjecture
• Coarse-Grained Complexity for Dynamic Algorithms