CS Paper Radar

Unconditional Boolean Dynamic Lower Bounds from Disjointness

Young Kun Ko

cs.DS cs.CC ·submitted 2026-10-07 21:00 UTC · v3
theory

Abstract

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

Comment
48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised. v3: changed title, revised introduction and exposition, clarified appendix reductions, and updated references

Closest papers

Nearest neighbours by meaning across the whole index.

Amortized Cell-Probe Lower Bounds for Dynamic Boolean Problems

cs.DS cs.CC ·2026-11-08 ·Young Kun Ko
theoryhot direction similarity 0.76
Abstract · 20 pages

We prove the first unconditional amortized $Ω\big((\log N/\log\log N)^2\big)$ cell-probe lower bound for a Boolean dynamic problem. For insert-only multiphase Disjointness with $N$ query sets over $[N]$ and word size $w=Θ(\log N)$, a fixed distribution of interleaved insertions and queries forces this expected average cost per operation, excluding preprocessing. The bound allows sufficiently small constant error for each query of every fixed legal sequence and imposes no restriction on individual operation costs. It transfers to incremental directed reachability, incremental subgraph connectivity, and fully dynamic triangle detection. We also prove $t_q=Ω\big((\log N/\log(t_uw))^2\big)$ for amortized insertion time $1\le t_u=N^{o(1)}$ and expected query time $t_q$, when the number of insertions before the final query is not announced in advance. We reach the quadratic-logarithmic scale with bounded error by combining interleaving with the 2.5-round communication framework [Ko26a, Ko26b] and controlling errors among accepted simulations.

0.27

Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries

cs.DS ·2026-08-19 ·Dominik Kempa, Tomasz Kociumaka
publishedtheory similarity 0.71
Abstract · Full version of a SODA 2027 paper

For a text $T$ of length $n$ over an alphabet of size $σ$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_σn)^ε)$ time using $O(n\logσ)$ bits, for any constant $ε>0$. Yet no nontrivial time-space lower bound for suffix-array queries in compact space was known. We give the first such lower bound: in the cell-probe model with $Θ(\log n)$-bit words, every deterministic $S$-bit data structure with $S\ge n$ answering suffix-array queries on binary strings of length at most $n$ has worst-case query time $Ω(\log\log n/\log((S/n)\log\log n))$. Hence, structures with $O(n(\log\log n)^{O(1)})$ bits need $Ω(\log\log n/\log\log\log n)$ query time, while constant query time requires $Ω(n\log^εn)$ bits for some constant $ε>0$, matching known upper bounds. In particular, no such $O(n)$-bit structure supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leqσ\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.

0.48

Asymptotically Optimal Bounds for Counting Near-Minimum Circuits in Regular Matroids

cs.DM math.CO ·2026-11-11 ·Robert P. Streit
theory similarity 0.70
Abstract · 28 pages

For a regular matroid on $m$ elements with positive weights and weighted girth $g_w$, we prove that the number of circuits of weight at most $αg_w$ is bounded by $(Km)^{2α}$, for every real $α\ge1$ and an absolute constant $K$. This improves the previous $m^{O(α^2)}$ bound of Gurjar and Vishnoi and matches classic graph cut and cycle counting bounds of Karger and Subramanian. We also show this is asymptotically optimal for all real $α\geq 1$ under the Erdős girth conjecture, while unconditional optimality holds for half-integer $α$ by prior results. As consequences, we resolve a recent conjecture by Khanna, Putterman, and Song implying the existence of a parallel basis search algorithm for regular matroids terminating in logarithmically many rounds of independence queries, and obtain improved bounds on the number of near-minimum weight codewords in regular codes and near-shortest vectors in totally unimodular lattices under $\ell_p$-norms.

0.23

Query Complexity of Testing Structured Parenthesis Languages

cs.DS cs.CC ·2026-09-29 ·Tim Jackman, Diptaksho Palit, Sofya Raskhodnikova
theory similarity 0.69
Abstract

We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query access to a word and must distinguish valid inputs from words that are far in Hamming distance, while inspecting only a sublinear number of positions. Our results sharpen the boundary between constant-query testability and polynomial query complexity. First, we prove an $Ω(n^{2/5})$ lower bound for testing Dyck languages $D_m$ with any fixed number $m\ge2$ of parenthesis types, improving the previous $Ω(n^{1/5})$ lower bound of Fischer, Magniez, and Starikovskaya (SODA `18) and nearly matching their upper bound of $O(n^{2/5+o(1)})$. Furthermore, we show that all nonadaptive algorithms for these problems require $Ω(n^{1/2})$ queries. Our lower bounds use a Pólya-urn process to construct the hard distribution; Second, we identify a broad class of weighted-parenthesis languages, which we call {\em excursion languages,} that remain constant-query testable. These languages encode bounded-step walks that stay nonnegative and return to zero. For every fixed excursion language, we give a nonadaptive tester with query complexity $O(1/\varepsilon^2)$, and we prove this dependence on $\varepsilon$ is optimal, even for adaptive algorithms. As a special case, we obtain the tight $Θ(1/\varepsilon^2)$ query complexity of testing $D_1$, improving the previous $O(\log(1/\varepsilon)/\varepsilon^2)$ upper bound and giving the first matching two-sided-error lower bound. Third, we construct a simple hard language, Hidden String, that is generated by a deterministic linear grammar but nevertheless requires $Ω(n^{2/5})$ adaptive queries and $Ω(n^{1/2})$ nonadaptive queries to test. This shows that polynomial query complexity appears even for highly restricted string languages.

0.18

Vertex Deletion on $H$-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation Schemes

cs.DS cs.DM ·2026-11-06 ·Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
similarity 0.68
Abstract

We study vertex-deletion problems on string graphs and, more generally, on graphs excluding a fixed graph as an induced minor. For every fixed graph $H$, fixed nonnegative integer $t$, and fixed monadic second-order formula $φ$, we consider the problem of finding a minimum-cardinality set $S$ such that $G-S$ has treewidth at most $t$ and satisfies $φ$. This captures classic problems such as Vertex Cover, Feedback Vertex Set, and deletion to graphs of any fixed bounded treewidth. We give an algorithm with running time $2^{k^{2/3} \log^{O(1)} k}n^{O(1)}$ on $H$-induced-minor-free graphs, where $k$ is the optimum deletion-set size. This resolves in the affirmative the open problem highlighted by Bonnet and Rzążewski [Algorithmica 2019] and Berthe, Bougeret, Gonçalves, and Raymond [ICALP 2025] regarding the existence of a subexponential parameterized algorithm for Feedback Vertex Set on string graphs. Our algorithm significantly improves over existing parameterized algorithms for more restricted classes of problems on more restricted classes of graphs. When the property defined by $φ$ is hereditary, we also obtain a quasi-polynomial time approximation scheme, namely an algorithm that produces a $(1+\varepsilon)$-approximate solution in quasi-polynomial time. Both the sub-exponential algorithm and the quasi-polynomial time approximation scheme build on the same new structural and algorithmic insights.

0.20

Constant-Factor Matching-Size Estimation in Random-Order Streams

cs.DS ·2026-11-16 ·Alireza Farhadi, Mohammad Hajiaghayi, Morteza Monemizadeh
similarity 0.68
Abstract

We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using $O(\log^2 n)$ bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least $2/3$, does not require the number of edges in advance, and has worst-case total running time $O((m+1)\log(n+2))$ on a word RAM. Kapralov, Khanna, and Sudan (SODA 2014) obtained a polylogarithmic approximation in polylogarithmic space. Kapralov, Mitrović, Norouzi-Fard, and Tardos (SODA 2020) subsequently gave a constant-factor approximation from independent uniform edge samples and an $O(\log^2 n)$-approximation in random order. We obtain a constant factor in the latter model with the same $O(\log^2 n)$ space bound. The main ingredient is a comparison between the memory states of a recursive sampling algorithm under sampling with and without replacement. We account jointly for the sampled edges retained by the recursion and the positions at which they arrived. Randomized thresholds limit the additional information stored in numerical counters. A bound on the expected work of the entire recursion then removes the loss from its logarithmic depth. The resulting estimator repeatedly improves a coarse estimate while storing only one recursion stack.

0.11

Square-Root Pass Semi-Streaming Algorithms for Digraph Problems

cs.DS ·2026-11-02 ·Prantar Ghosh, Amirhossein Janfaza
theory similarity 0.68
Abstract

We study directed graph problems in the semi-streaming model where we are restricted to $\widetilde{O}(n):=O(n\cdot \text{polylog}(n))$ space for processing the edge stream of an $n$-node graph and can make one or a few passes to solve the given problem. A longstanding open problem in multipass streaming is determining the number of semi-streaming passes needed to solve directed $s,t$-reachability: there is an exponential gap---$Ω(\log n/\log \log n)$ vs $n^{1/2+o(1)}$---between the best-known lower and upper bounds. Several related fundamental digraph problems, e.g., topological sorting, acyclicity testing, and decomposition into strongly connected components (SCCs), are known to have the same semi-streaming pass lower bound. However, no $o(n/\text{polylog}(n))$-pass upper bound was known for any of them. Our main result achieves an $n^{1/2+o(1)}$-pass semi-streaming algorithm for each of these problems. As a corollary, we get algorithms with the same pass and space usage for a broad class of DAG problems that admit a certain form of dynamic program over a topological ordering. This class includes weighted single-source shortest paths, longest paths, max-outdegree+1 coloring, and constructing a lexicographically-first DFS (depth-first search) forest. Our algorithm for the last problem can be seen as a generalization of our results on topological sorting and acyclicity testing: recall that standard textbook algorithms for these problems use DFS as a subroutine. Our algorithms are optimal up to an $n^{o(1)}$ factor in passes under the reasonable conjecture that $s,t$-reachability requires $Ω(\sqrt{n})$ semi-streaming passes. However, using the fact that our algorithms can be parameterized by the number of passes taken by topological sorting or single-source reachability algorithms, we prove stronger lower bounds for some of the problems even under weaker conjectures.

0.28

Exact Algorithms and Complexity of the Smallest Grammar Problem

cs.DS ·2026-10-23 ·Xiangle Chen
theory similarity 0.68
Abstract · Revised version with a uniform alphabet-sensitive subexponential algorithm and quantitative transfers to SAT. Source package includes verifi…

The Smallest Grammar Problem (SGP) asks for a smallest straight-line grammar generating a given string, with size measured by the total right-hand-side length. For an input of length $n\ge2$ over at most $σ$ symbols, where $2\leσ\le n$, let $R=\log_σn$. We give a deterministic exact algorithm running in $n^{O(1)}2^{O(n\log\log n/(R\sqrt{\log n}))}$ time and polynomial space, with constants independent of $σ$. This gives time $2^{O(n\log\log n/(\log n)^{3/2})}$ for fixed alphabets and $2^{O(n\log\log n/\sqrt{\log n})}$ for arbitrary alphabets, up to polynomial factors. The algorithm combines pairwise disjoint representative occurrences of dictionary strings, a sparse interval certificate, and the Boolean tensor contraction theorem of OpenAI. It explicitly enforces dictionary membership, rule boundaries, and the grammar-size budget. Independently of that contraction theorem, disjoint representatives yield exact algorithms in $O^*(1.872258^n)$ time and $2^{O((n/R)\log(R+1))}$ time using $O(n)$ words of space. Anchor-based grammar projections establish binary NP-completeness and reductions with tunable alphabet size. We state their consequences as unconditional quantitative transfers from SGP algorithms to sparse SAT algorithms, and quantify the additional loss from sparsifying general formulas.

0.45