PaperlayerView exact revision on arXiv

Source-linked AI summary

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak

arXiv:1511.06773v1cs.DS

TL;DR

The paper asks whether the Online Boolean Matrix-Vector Multiplication conjecture can provide a common hardness basis for dynamic problems. It develops reductions through online vector-matrix-vector multiplication and derives tight, strengthened, and new hardness results across many problems.

  • Problem

    The paper studies the online Boolean matrix-vector multiplication problem, where each product Mv_i must be output before the next vector arrives, and asks whether truly subcubic algorithms exist.

  • Method

    The paper uses the OMv conjecture and the intermediate OuMv problem as starting points for reductions to dynamic problems, while addressing polynomial preprocessing and different dimension parameters.

  • Results

    The OMv conjecture yields more than 15 new tight hardness results, matches or improves many prior conjecture-based bounds, and implies strong bounds for the multiphase problem.

  • Takeaways & Limitations

    The conjecture provides a uniform basis for polynomial hardness results across dynamic problems and, if refuted, would imply a fast matrix multiplication algorithm substantially different from Strassen-based approaches.

  • Takeaways & Limitations

    The hardness results use a particular amortization notion and do not subsume the Boolean matrix multiplication-based s-t reachability result, which applies specifically to combinatorial algorithms.

Abstract

from arXiv · show

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an $n\times n$ matrix $M$ and will receive $n$ column-vectors of size $n$, denoted by $v_1,\ldots,v_n$, one by one. After seeing each vector $v_i$, we have to output the product $Mv_i$ before we can see the next vector. A naive algorithm can solve this problem using $O(n^3)$ time in total, and its running time can be slightly improved to $O(n^3/\log^2 n)$ [Williams SODA'07]. We show that a conjecture that there is no truly subcubic ($O(n^{3-ε})$) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, $d$-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "non-Strassen-like algorithms" [Ballard et al. SPAA'11]. The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures, such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase, thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results.

1 Introduction

The paper proposes the OMv conjecture as a common basis for polynomial-time hardness in dynamic problems, unifying and strengthening results previously derived from diverse conjectures. It establishes tight or improved bounds across several problems, including subgraph connectivity and Pagh’s problem, while connecting OMv hardness to Boolean matrix multiplication.

  • Online Boolean Matrix-Vector Multiplication: OMv asks an algorithm to output Mv_i for each of n sequentially revealed vectors before seeing the next vector.The matrix is given initially, and the computation must finish as quickly as possible.
  • OMv-Based Hardness: The paper uses the OMv conjecture to capture shared polynomial-time hardness across a large number of dynamic problems.The approach is intended to unify, simplify, and strengthen hardness results based previously on 3SUM, BMM, triangle detection, and multiphase conjectures.
  • Main Results: More than 15 new tight hardness results are obtained, alongside new results for vertex color distance oracles, restricted top trees, and dynamic densest subgraph.The paper defines tightness through trade-offs involving query time, update time, or approximation guarantees.
  • Main Results: For subgraph connectivity, OMv rules out polynomial-preprocessing algorithms with m^(α−ε) amortized update time and m^(1−α−ε) amortized query time for any 0 ≤ α ≤ 1.This matches the cited upper bound when α = 2/3.
  • Main Results: The OMv conjecture also rules out improvements in several dynamic settings, including exact s-t reachability trade-offs and decremental all-pairs shortest paths with approximation ratio below two.The decremental shortest-path result addresses whether fast matrix multiplication can improve the dynamic setting beyond known bounds.
  • Main Results: For Pagh’s problem, OMv rules out algorithms with polynomial preprocessing, n^(1−ε) update time, and k^(1−ε) query time for any k = poly(n), matching the trivial upper bound.Unlike the previous BMM-based result, this hardness applies to all algorithms, including non-combinatorial ones.
  • OMv and BMM: OMv is linked to combinatorial BMM because reductions can reveal the second matrix one column at a time, while OMv excludes some combinatorial BMM algorithms and Strassen-like block multiplication.Breaking OMv is therefore described as requiring a substantially different fast matrix multiplication approach.

2 Intermediate Problems

This section strengthens OMv-based hardness by allowing polynomial preprocessing, arbitrary dimensions, and related online multiplication variants. It establishes near-tight computation-time barriers that support reductions to dynamic problems.

  • Polynomial preprocessing and arbitrary dimensions: γ-OMv generalizes OMv by permitting preprocessing and rectangular matrices whose minimum dimension is not too small relative to the maximum.The online phase presents n3 vectors sequentially and requires each product before the next vector arrives.
  • Polynomial preprocessing and arbitrary dimensions: Theorem 2.2 rules out γ-OMv algorithms with polynomial preprocessing and computation time ˜˜o(n1n2n3), for any constant γ > 0.The error probability must be at most 1/3.
  • Polynomial preprocessing and arbitrary dimensions: The proof lifts hardness from smaller matrix blocks by partitioning the matrix and vectors, solving each block instance, and aggregating the resulting partial products.Repetition and majority voting preserve the error bound while introducing only polylogarithmic overhead.
  • Polynomial preprocessing and arbitrary dimensions: Corollary 2.4 already excludes sublinear computation under preprocessing time at most (n1n2)1+ϵ for any constant ϵ < 1/2.A faster algorithm would yield a truly subcubic OMv algorithm, contradicting Conjecture 1.1.
  • OuMv and uMv: OuMv returns one bit per vector pair, enabling simpler reductions and stronger query-time lower bounds than starting from full OMv outputs.The paper proves the same ˜˜o(n1n2n3) barrier for γ-OuMv and the ˜˜o(n1n2) barrier for γ-uMv under polynomial preprocessing.
  • OuMv and uMv: The framework further supplies structural OuMv normalizations, including symmetric matrices and vector pairs that are equal or have disjoint supports.These forms are used as useful starting points for subsequent reductions.

3 Hardness for Amortized Fully Dynamic and Worst-case Partially Dynamic Problems

The paper organizes dynamic-problem hardness by update and query-time regimes and summarizes the resulting conditional bounds. Its reductions translate dynamic algorithms into algorithms for uMv.

  • Lower-bound regimes: Sections 3.1 and 3.2 cover regimes excluding simultaneous update/query times ˜˜o(√m), ˜˜o(m) and ˜˜o(m1−δ), ˜˜o(mδ), respectively.The second regime applies for every constant 0 < δ < 1.
  • Lower-bound regimes: The reductions target remaining graph and non-graph problems in Sections 3.3–3.6, including cases with more varied lower-bound parameter forms.The diameter and densest-subgraph reductions receive dedicated sections because they are more involved.
  • Reduction framework: A dynamic algorithm with low worst-case update/query time, or low amortized times when fully dynamic, would yield a contradiction to the OMv Conjecture.The standard reduction preprocesses a graph, then simulates updates and queries to solve uMv.

3.1 Lower Bounds for Graph Problems with High Query Time

The paper reduces online matrix-vector multiplication to dynamic graph problems where only O(√m) updates and one query are needed, yielding high-query-time hardness bounds. These reductions establish tight lower bounds for subgraph connectivity, approximate shortest paths, triangle detection, and related problems.

  • Comparison with upper bounds: The resulting bounds are summarized alongside matching or stronger upper bounds in Tables 4–6, with polylogarithmic factors omitted.Table 5 distinguishes fully dynamic amortized bounds from partially dynamic worst-case bounds.
  • Reductions: O(√m) updates and 1 query suffice to reduce 1-uMv to partially dynamic st-SubConn, approximate st-SP, and triangle detection.The constructions use graphs with Θ(√m) vertices and O(m) edges.
  • Reductions: u^⊤Mv = 1 is encoded as st-connectivity, a distance gap of 3 versus at least 5, or the existence of a triangle.The same bipartite graph framework changes only the queried property and the update operations.
  • Lower bounds: No partially dynamic algorithm can simultaneously achieve poly(m) preprocessing, update time ˜˜o(√m), and query time ˜˜o(m) for the listed problems, assuming the OMv Conjecture.The bound also applies to fully dynamic algorithms with amortized update time.
  • Lower bounds: The reduction runs in O(√m u(m) + q(m)) time, so both sub-√m updates and sub-m queries would contradict the OMv Conjecture.The contradiction uses polynomial preprocessing and the one-query reductions.
  • Consequences: The st-SubConn lower bound transfers to reachability, strong connectivity, bipartite matching, vertex cover, and undirected unit-capacity st-maxflow.These reductions preserve the lower-bound parameters.

3.2 Lower Bounds for Graph Problems with a Trade-off

By choosing asymmetric matrix dimensions, the paper derives update-query trade-offs for dynamic graph problems. The resulting bounds cover single-source subgraph connectivity, approximate shortest paths, and vertex-color distance oracles.

  • Trade-off reductions: m^(1−δ) updates and m^δ queries reduce (1−δ, δ)-uMv to several dynamic graph problems, enabling a tunable update-query lower-bound trade-off.Here m^δ = n1 and m^(1−δ) = n2.
  • Encodings: The reductions encode u^⊤Mv = 1 using connectivity, distance gaps of 2 versus 4, or vertex-color distances of 1 versus at least 3.The update and query counts depend on which vector is represented by graph changes and which is tested by queries.
  • Vertex-color distance: The vertex-color distance oracle reduction uses O(m^δ) color changes and O(m^(1−δ)) queries on graphs with O(m) edges and O(m^δ + m^(1−δ)) vertices.The distance gap is 1 versus at least 3 for queried colors.
  • Lower bounds: No partially dynamic algorithm can achieve update time ˜˜o(m^δ) and query time ˜˜o(m^(1−δ)) simultaneously for ss-SubConn, ss-SP, or vertex-color distance oracles.The statement assumes polynomial preprocessing and error probability at most 1/3.
  • Approximation barriers: For vertex-color distance oracles, improving the approximation ratio below 3 requires Ω(n) update or query time in dense graphs when δ = 1/2 and m = n^2.The paper also connects this barrier to improving dynamic Steiner tree through better vertex-color distance oracles.

3.3 Lower Bounds for Graph Problems with other Parameters

Further reductions extend OMv-based hardness to approximate s-t shortest paths and d-failure connectivity, including bounds parameterized by batch size and approximation factors. Some bounds are tight for existing algorithms, while update-time improvements alone may remain possible.

  • Approximate st-SP: O(√n) updates and 1 query reduce uMv to partially dynamic (3−ε)-approximate st-SP.The construction subdivides edges so distances distinguish the encoded cases.
  • Approximate st-SP: No partially dynamic (3−ε)-approximate st-SP algorithm achieves poly(n) preprocessing, update time ˜˜o(√n), and query time ˜˜o(n), assuming OMv.The same lower bound applies to fully dynamic algorithms with amortized update time.
  • d-failure connectivity: One batch of O(m^δ) updates and O(m^(1−δ)) queries reduces (δ/(1−δ))-uMv to d-failure connectivity.The batch turns off up to d vertices, with d = m^δ.
  • d-failure connectivity: No d-failure connectivity algorithm can simultaneously use update time ˜˜o(d^(1/δ)) and query time ˜˜o(d) under the stated graph-size and preprocessing conditions.This holds for δ ∈ (0, 1/2] and error probability at most 1/3.
  • Tightness: The existing d-failure connectivity query bound is tight against significant improvement when update time remains polynomial in d, but improving update time alone does not contradict OMv.The paper derives this by choosing δ arbitrarily close to zero.

3.4 Lower Bounds for Non-graph Problems

The paper applies OMv reductions beyond graph problems, obtaining amortized hardness for Pagh’s problem, Langerman’s zero prefix sum problem, and Erickson’s problem. These results unify several previously diverse conjecture-based arguments.

  • Overview: The reductions in this section mimic prior constructions but yield amortized lower bounds, whereas the earlier results gave worst-case bounds.The paper applies this strategy to non-graph problems.
  • Pagh’s problem: For Pagh’s problem, k updates and n queries solve γ-uMv, implying no algorithm with update time ˜˜o(n) and query time ˜˜o(k) when k = n^γ.The reduction uses polynomial preprocessing over k initial sets in universe [n].
  • Langerman’s problem: O(√n) updates and O(√n) queries reduce 1-uMv to Langerman’s zero prefix sum problem on an array of size O(n).Rows encode matrix entries, while vector updates and prefix-sum queries test the matrix-vector product.
  • Langerman’s problem: No Langerman algorithm with polynomial preprocessing, amortized update time ˜˜o(√n), and query time ˜˜o(√n) is consistent with the OMv Conjecture.The reduction resets the array between vector pairs and invokes OuMv hardness.
  • Erickson’s problem: For Erickson’s problem, no algorithm with polynomial preprocessing, amortized update time ˜˜o(n), and query time ˜˜o(n^2) exists unless the OMv Conjecture fails.The reduction uses O(n·n3) updates and n3 queries to solve 1-OuMv.

3.5 (2 −ϵ) Approximate Diameter on Weighted Graphs

The section reduces γ-uMv to fully dynamic (2 −ϵ)-approximate diameter on {0,1}-weighted graphs. Assuming the OMv Conjecture, this yields a near-√n update-time and near-n query-time hardness bound.

  • Hardness result: OMv-hardness holds for maintaining a (2 −ϵ)-approximation of diameter in fully dynamic {0,1}-weighted graphs.The reduction applies only in the fully dynamic setting, unlike several earlier reductions.
  • Reduction: A γ-uMv instance is encoded using vector graphs with upper and lower clique halves, plus zero-weight matching edges and two special vertices.Each vector graph has √n2 vertices in each half, and matrix rows are represented by separate vector graphs.
  • Reduction: The construction uses O(n1√n2) vertices, n2 + O(n1√n2) updates, and n1 queries for each γ-uMv instance.Stages modify connections for rows selected by u, query the diameter, and undo the updates before the next stage.
  • Correctness: If u⊤Mv = 1, some cross-half pair has distance at least 2, so the diameter is 2.The missing matrix-vector intersection prevents a one-edge path for a selected pair.
  • Hardness result: There is no fully dynamic algorithm with polynomial preprocessing, amortized update time ˜˜o(√n), and query time ˜˜o(n) for (2 −ϵ)-approximate diameter.The lower bound holds with error probability at most 1/3.

3.6 Densest Subgraph Problem

The section gives a partially dynamic reduction from 1-uMv to densest subgraph. Under the OMv Conjecture, it rules out simultaneous sub-n1/3 update and sub-n2/3 query times with polynomial preprocessing.

  • Reduction: 1-uMv reduces to densest subgraph using a graph with Θ(n3) vertices, Θ(n) updates, and one query.The graph is built from bit, row, and column gadgets derived from M, then updated according to u and v.
  • Correctness: A set has density at least (k+7)/(k+6) if and only if u⊤Mv = 1.When an intersecting set bit exists, the corresponding row, bit, and column gadgets form k + 6 vertices and k + 7 edges.
  • Correctness: The reduction normalizes candidate dense subgraphs by taking complete bit, row, or column gadgets, or only special vertices where appropriate.Removing incomplete gadgets does not reduce density under the stated assumptions and lemma.
  • Hardness result: Unless the OMv Conjecture fails, no partially dynamic densest-subgraph algorithm has polynomial preprocessing, worst-case update time ˜˜o(n1/3), and query time ˜˜o(n2/3).The same statement holds for fully dynamic algorithms with amortized update time.

4 Hardness for Total Update Time of Partially Dynamic Problems

This section derives total-update-time lower bounds for partially dynamic graph problems by reducing OuMv to dynamic shortest paths, matching, single-source shortest paths, approximate all-pairs shortest paths, and transitive closure.

  • Reduction framework: The reductions preprocess a graph encoding M, then use updates and queries to distinguish whether each online product u_t⊤Mv_t equals 1.The approach is presented symmetrically for incremental and decremental settings when applicable.
  • s-t shortest path: For st-SP, 1-OuMv reduces to √m queries on a graph with Θ(√m) vertices and O(m) edges.Distances are 2t + 1 when the product is 1 and at least 2t + 2 otherwise.
  • s-t shortest path: No partially dynamic st-SP algorithm achieves polynomial preprocessing, total update time ˜˜o(m3/2), and query time ˜˜o(m), unless the OMv Conjecture fails.For m = Θ(n2), this gives no ˜˜o(n3) total update time and ˜˜o(n2) query time, matching an O(mn) upper bound.
  • Maximum matching: For bipartite maximum matching, the reduction uses Θ(m) vertices and edges and √m queries, detecting whether deletions reduce matching size by dt − 1 or dt.The distinction is caused by an augmenting path exactly when an online matrix-vector product is 1.
  • Maximum matching: No partially dynamic bipartite maximum-matching algorithm has polynomial preprocessing, total update time ˜˜o(m3/2), and query time ˜˜o(m) on the stated sparse-graph regime.The hardness proof applies only to sparse graphs.
  • Other problems: For constant δ ∈ (0, 1/2], OMv implies no partially dynamic algorithm for ss-SP, (2 versus 4) ap-SP, or transitive closure with total update time ˜˜o(mn) and query time ˜˜o(mδ).The reductions use Θ(mδ + m1−δ) vertices and Θ(m) edges.

5 Further Discussions

The discussion develops OMv-based multiphase lower bounds and identifies open questions about coverage, update-time models, determinism, and query-update trade-offs. It also records several scope limitations of the techniques.

  • Multiphase problem: The multiphase problem preprocesses M, receives v, and answers whether (Mv)i = 1 for a queried index i, with τ controlling phase costs.Its three phases use O(n1n2τ), O(n2τ), and O(τ) time respectively.
  • Multiphase problem: An algorithm for multiphase with update time τ yields γ-OMv in O((n1n2 + n2n3 + n1n3)τ) time.The reduction runs phase 2 for every online vector and phase 3 for every matrix row and vector.
  • Multiphase problem: Unless the OMv Conjecture fails, multiphase requires τ = ˜˜Ω(min{n1,n2}).This improves the previously cited 3SUM-based bound for the equal-parameter setting.
  • Dynamic consequences: The framework converts multiphase algorithms into amortized update/query lower bounds for dynamic objects, including subgraph connectivity.For subgraph connectivity with n1 = n2 = n, the resulting amortized cost cannot be ˜˜o(n) unless OMv fails.
  • Open problems and limitations: The paper does not provide tight lower bounds for many problems, including minimum cut and several partially dynamic problems with asymmetric difficulty between update directions.Known techniques generally apply to both incremental and decremental settings, making one-sided hardness challenging.
  • Open problems and limitations: Open directions include worst-case rather than amortized update hardness, deterministic-only hardness, and tight query-update trade-offs.For subgraph connectivity, the paper gives an Ω(m1−α) query requirement for O(mα) updates and notes matching upper bounds at α = 4/5 and 2/3.

A Conjectures (from [AVW14])

This section states five conjectures asserting time lower bounds for 3SUM, APSP, SAT, triangle detection, and combinatorial Boolean matrix multiplication.

  • 3SUM: 3SUM is conjectured to require n^{2−o(1)} expected time in the Word RAM model for detecting a+b=c among three distinct set elements.The set contains n integers from {−n^3, ..., n^3}, and words have O(log n) bits.
  • APSP: APSP is conjectured to require n^{3−o(1)} expected time to compute all-pairs distances in an n-node weighted graph.Edge weights lie in {1, ..., n^c} for a constant c, under the Word RAM model.
  • SETH: SETH conjectures that, for every ε>0, some fixed-width CNF-SAT problem cannot be solved in O*(2^{(1−ε)n}) time.The O* notation hides polynomial factors.
  • Triangle: Triangle detection is conjectured to require m^{1+δ−o(1)} expected time for some constant δ>0 in an m-edge graph.The task is deciding whether the graph contains a triangle in the Word RAM model.
  • Combinatorial BMM: Combinatorial Boolean matrix multiplication is conjectured to require n^{3−o(1)} expected time for multiplying two n×n Boolean matrices.The conjecture applies to combinatorial algorithms in the Word RAM model with O(log n)-bit words.
Loading 1511.06773v1…