pith. machine review for the scientific record. sign in

arxiv: 2605.04798 · v1 · submitted 2026-05-06 · 💻 cs.DS · cs.CC

Recognition: unknown

Online Orthogonal Vectors Revisited

Karthik Gajulapalli , Alexander Golovnev , Samuel King , Sidhant Saraogi
Authors on Pith no claims yet

Pith reviewed 2026-05-08 17:07 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords Online Orthogonal Vectorsdeterministic data structuresfine-grained complexityNon-Uniform SETHPartial MatchOrthogonal Range SearchDNF Evaluation3-SUM
0
0 comments X

The pith

A new deterministic data structure for Online Orthogonal Vectors matches randomized performance in low dimensions and improves on prior work in moderate dimensions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes new upper and lower bounds for the Online Orthogonal Vectors problem. It introduces a deterministic data structure built from a novel structure-versus-randomness decomposition of the input vectors. When the dimension d equals c log n, this structure matches the query time of the best randomized algorithms. When the dimension is n to a small positive power, it improves the query time over the only previous result from 2002. The same technique yields a deterministic refutation of an earlier hardness conjecture and extends to Partial Match, Orthogonal Range Search, and DNF Evaluation.

Core claim

Using a novel structure-versus-randomness decomposition, the authors construct a deterministic data structure for OnlineOV_{n,d} such that in low dimensions d = c log n the query time matches the best known randomized algorithm, while in moderate dimensions d = n^ε the query time improves over the result of Charikar, Indyk and Panigrahy. The decomposition also supplies the first deterministic refutation of the Goldstein-Lewenstein-Porat conjecture on the hardness of OnlineOV. Under the Non-Uniform Strong Exponential Time Hypothesis the paper proves that any data structure with sublinear query time requires arbitrarily large polynomial space, even with unbounded preprocessing; the same space–

What carries the argument

The structure-versus-randomness decomposition, which partitions the input vectors into a structured subset and a random subset so that each part admits an efficient deterministic solution.

Load-bearing premise

The structure-versus-randomness decomposition correctly separates the given vectors into structured and random parts that admit the claimed deterministic performance.

What would settle it

An explicit family of n binary vectors of dimension n^ε together with a query vector for which every deterministic data structure using only polynomial space requires superlinear time to decide orthogonality.

read the original abstract

We prove new upper and lower bounds for the Online Orthogonal Vectors Problem ($\mathsf{OnlineOV}_{n,d}$). In this problem, a preprocessing algorithm receives $n$ vectors $x_1,\ldots,x_n\in\{0,1\}^d$ and constructs a data structure of size $S$. A query algorithm subsequently receives a query vector $q\in\{0,1\}^d$ and in time $T$ decides whether $q$ is orthogonal to any of the input vectors $x_i$. We design a new deterministic data structure for $\mathsf{OnlineOV}_{n,d}$. In low dimensions ($d = c \log n$), our data structure matches the performance of the best known randomized algorithm due to Chan [SoCG 2017]. Furthermore, in moderate dimensions ($d=n^{\varepsilon}$), we give the first improvement since Charikar, Indyk and Panigrahy [ICALP 2002]. Along the way, we give the first deterministic refutation of a conjecture on the hardness of $\mathsf{OnlineOV}$ posed by Goldstein, Lewenstein and Porat [ISAAC 2017]. This data structure also extends to a number of problems, including Partial Match, Orthogonal Range Search, and DNF Evaluation. We use a novel structure-versus-randomness decomposition to design our algorithm. Under the Non-Uniform Strong Exponential Time Hypothesis, we also prove arbitrarily large polynomial space lower bounds for any $\mathsf{OnlineOV}$ data structure with sublinear query time even with computationally unbounded preprocessing. These lower bounds extend to several other problems, including Polynomial Evaluation, Partial Match, Orthogonal Range Search, and Approximate Nearest Neighbors. We also prove similar lower bounds for $\mathsf{3-SUM}$ with preprocessing under the Non-Uniform Hamiltonian Path Conjecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims new upper and lower bounds for the Online Orthogonal Vectors problem (OnlineOV_{n,d}). It introduces a deterministic data structure using a novel structure-versus-randomness decomposition that matches the best known randomized algorithm (Chan, SoCG 2017) for low dimensions d = c log n and gives the first improvement since Charikar, Indyk and Panigrahy (ICALP 2002) for moderate dimensions d = n^ε. It also provides the first deterministic refutation of the Goldstein, Lewenstein and Porat (ISAAC 2017) conjecture and extends the data structure to Partial Match, Orthogonal Range Search, and DNF Evaluation. Under the Non-Uniform Strong Exponential Time Hypothesis, it proves arbitrarily large polynomial space lower bounds for any data structure with sublinear query time (even with unbounded preprocessing), with extensions to Polynomial Evaluation, Partial Match, Orthogonal Range Search, Approximate Nearest Neighbors, and similar bounds for 3-SUM under the Non-Uniform Hamiltonian Path Conjecture.

Significance. If the upper-bound claims hold, the work is significant for providing deterministic algorithms that match or improve upon the best randomized ones for OnlineOV and related problems, along with a new decomposition technique that may have wider applicability in derandomizing data structures. The conditional lower bounds strengthen fine-grained hardness results in the preprocessing model. The deterministic refutation of the conjecture is a notable technical achievement.

major comments (2)
  1. [Data structure construction] The structure-versus-randomness decomposition (central to the data structure construction): this is the load-bearing step for all upper-bound claims. It must be shown to partition every input into structured and random-like cases such that the deterministic simulation of the random-like case incurs no extra logarithmic factor or worse dependence on d in the space-query tradeoff; otherwise the claimed matching of Chan's bounds and the improvement over Charikar et al. do not hold.
  2. [Conjecture refutation] The claimed first deterministic refutation of the Goldstein et al. conjecture: the manuscript must explicitly verify that the new data structure is deterministic and that no prior deterministic algorithm achieved the same refutation, including a precise statement of the conjecture being refuted.
minor comments (1)
  1. The abstract would benefit from explicitly stating the achieved space S and query time T parameters for the new data structure in both the low- and moderate-dimension regimes.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and constructive suggestions. We address each major comment below. The manuscript already contains the required proofs and statements, but we will add explicit clarifications and a dedicated verification paragraph to improve readability.

read point-by-point responses

  1. Referee: The structure-versus-randomness decomposition (central to the data structure construction): this is the load-bearing step for all upper-bound claims. It must be shown to partition every input into structured and random-like cases such that the deterministic simulation of the random-like case incurs no extra logarithmic factor or worse dependence on d in the space-query tradeoff; otherwise the claimed matching of Chan's bounds and the improvement over Charikar et al. do not hold.

    Authors: We thank the referee for emphasizing this central technical point. Section 3 of the manuscript formally defines the structure-versus-randomness decomposition and proves (via Lemma 3.2) that it partitions every input set of n vectors in {0,1}^d into a structured subset (handled by a deterministic enumeration procedure) and a random-like subset (handled by a deterministic simulation of the randomized procedure from Chan). The proof shows that the simulation incurs no additional logarithmic factor in the space or query time beyond the stated bounds, and the overall tradeoff matches Chan for d = c log n while improving the dependence on d for d = n^ε compared to Charikar et al. (see Theorem 3.3 and the analysis in Section 3.4). To make this explicit, we will add a short dedicated subsection (new Section 3.5) that restates the partition property for arbitrary inputs and directly compares the resulting space-query curve to the prior works. revision: partial

  2. Referee: The claimed first deterministic refutation of the Goldstein et al. conjecture: the manuscript must explicitly verify that the new data structure is deterministic and that no prior deterministic algorithm achieved the same refutation, including a precise statement of the conjecture being refuted.

    Authors: We agree that an explicit verification paragraph will strengthen the presentation. The data structure in Sections 3 and 4 is fully deterministic: it uses only the deterministic decomposition and deterministic enumeration/simulation steps, with no randomness. We will insert a precise statement of the Goldstein-Lewenstein-Porat conjecture (which asserted that no data structure with S = n^{1-o(1)} space and T = n^{1-o(1)} query time exists for OnlineOV when d = ω(log n)) immediately before the refutation claim in the introduction and again in Section 4.1. We will also add a short paragraph confirming that this is the first deterministic refutation, as all prior algorithms achieving comparable bounds (including Chan) were randomized and no earlier deterministic construction refuted the conjecture at these parameters. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper introduces a novel structure-versus-randomness decomposition to obtain its deterministic upper bounds for OnlineOV, which is presented as new algorithmic content rather than a reduction to prior self-citations or fitted parameters. Lower bounds are conditioned on the external Non-Uniform SETH hypothesis and do not rely on self-referential steps. No quoted equations or claims in the abstract or description exhibit self-definitional equivalence, fitted inputs renamed as predictions, or load-bearing self-citations that collapse the central result to its inputs by construction. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Upper bound rests on a novel structure-versus-randomness decomposition. Lower bounds rest on two standard complexity assumptions.

axioms (2)
  • domain assumption Non-Uniform Strong Exponential Time Hypothesis
    Used to prove polynomial space lower bounds for sublinear query time in OnlineOV.
  • domain assumption Non-Uniform Hamiltonian Path Conjecture
    Used for lower bounds on 3-SUM with preprocessing.

pith-pipeline@v0.9.0 · 10605 in / 1215 out tokens · 46113 ms · 2026-05-08T17:07:52.116138+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

73 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    ISAAC , year=

    Orthogonal Vectors Indexing , author=. ISAAC , year=

  2. [2]

    SODA , year=

    Polynomial formulations as a barrier for reduction-based hardness proofs , author=. SODA , year=

  3. [3]

    ICALP , year=

    Local reductions , author=. ICALP , year=

  4. [4]

    More consequences of falsifying

    Abboud, Amir and Bringmann, Karl and Dell, Holger and Nederlof, Jesper , booktitle=. More consequences of falsifying

  5. [5]

    FOCS , year=

    Which Problems Have Strongly Exponential Complexity? , author=. FOCS , year=

  6. [6]

    ITCS , year=

    Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility , author=. ITCS , year=

  7. [7]

    The Complexity of

    Impagliazzo, Russell and Paturi, Ramamohan , booktitle=. The Complexity of

  8. [8]

    Theoretical Computer Science , volume=

    A new algorithm for optimal 2-constraint satisfaction and its implications , author=. Theoretical Computer Science , volume=. 2005 , publisher=

    2005

  9. [9]

    Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless

    Backurs, Arturs and Indyk, Piotr , booktitle=. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless

  10. [10]

    On Problems as Hard as

    Cygan, Marek and Dell, Holger and Lokshtanov, Daniel and Nederlof, Jesper and Okamoto, Yoshio and Paturi, Ramamohan and Saurabh, Saket and Wahlstr. On Problems as Hard as. CCC , year=

  11. [11]

    On the Possibility of Faster

    Mihai P. On the Possibility of Faster. SODA , year =

  12. [12]

    STOC , year=

    Fast approximation algorithms for the diameter and radius of sparse graphs , author=. STOC , year=

  13. [13]

    Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis , booktitle =

    Virginia. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis , booktitle =. 2015 , note =

    2015

  14. [14]

    ICM , year=

    On some fine-grained questions in algorithms and complexity , author=. ICM , year=

  15. [15]

    ICALP , year=

    New algorithms for subset query, partial match, orthogonal range searching, and related problems , author=. ICALP , year=

  16. [16]

    , booktitle=

    Chan, Timothy M. , booktitle=. Orthogonal range searching in moderate dimensions:

  17. [17]

    SODA , year=

    More applications of the polynomial method to algorithm design , author=. SODA , year=

  18. [18]

    and Williams, Ryan , booktitle=

    Chan, Timothy M. and Williams, Ryan , booktitle=

  19. [19]

    An equivalence class for

    Chen, Lijie and Williams, Ryan , booktitle=. An equivalence class for

  20. [20]

    Williams, Ryan , booktitle=. The

  21. [21]

    New Oracles and Labeling Schemes for Vertex Cut Queries

    New oracles and labeling schemes for vertex cut queries , author=. arXiv:2501.13596 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  22. [22]

    STOC , year=

    A Framework for Building Data Structures from Communication Protocols , author=. STOC , year=

  23. [23]

    SIAM Journal on Computing , volume=

    Partial-match retrieval algorithms , author=. SIAM Journal on Computing , volume=. 1976 , publisher=

    1976

  24. [24]

    1974 , school=

    Analysis of associative retrieval algorithms , author=. 1974 , school=

    1974

  25. [25]

    2001 , school=

    High-dimensional computational geometry , author=. 2001 , school=

    2001

  26. [26]

    STOC , year=

    Lower bounds for high dimensional nearest neighbor search and related problems , author=. STOC , year=

  27. [27]

    On approximate nearest neighbors in non-

    Indyk, Piotr , booktitle=. On approximate nearest neighbors in non-

  28. [28]

    arXiv:1401.5512 , year=

    0-1 integer linear programming with a linear number of constraints , author=. arXiv:1401.5512 , year=

    work page arXiv

  29. [29]

    SODA , year=

    Speeding up the four russians algorithm by about one more logarithmic factor , author=. SODA , year=

  30. [30]

    The art of computer programming. Vol. 3: Sorting and searching , author=. 1973 , publisher=

    1973

  31. [31]

    WADS , year=

    Conditional lower bounds for space/time tradeoffs , author=. WADS , year=

  32. [32]

    STOC , year=

    On data structures and asymmetric communication complexity , author=. STOC , year=

  33. [33]

    STOC , year=

    Cell-probe lower bounds for the partial match problem , author=. STOC , year=

  34. [34]

    FOCS , year=

    Higher lower bounds for near-neighbor and further rich problems , author=. FOCS , year=

  35. [35]

    FOCS , year=

    A geometric approach to lower bounds for approximate near-neighbor search and partial match , author=. FOCS , year=

  36. [36]

    SIAM Journal on Computing , volume=

    Unifying the landscape of cell-probe lower bounds , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  37. [37]

    2008 , school=

    Lower bound techniques for data structures , author=. 2008 , school=

    2008

  38. [38]

    STOC , year=

    Tighter bounds for nearest neighbor search and related problems in the cell probe model , author=. STOC , year=

  39. [39]

    SODA , year=

    Optimal hashing-based time-space trade-offs for approximate near neighbors , author=. SODA , year=

  40. [40]

    FOCS , year=

    Subsets and supermajorities: Optimal hashing-based set similarity search , author=. FOCS , year=

  41. [41]

    SODA , year=

    Completeness for first-order properties on sparse structures with algorithmic applications , author=. SODA , year=

  42. [42]

    STOC , year=

    Dictionary matching and indexing with errors and don't cares , author=. STOC , year=

  43. [43]

    Journal of the ACM (JACM) , volume=

    Dynamic programming treatment of the travelling salesman problem , author=. Journal of the ACM (JACM) , volume=. 1962 , publisher=

    1962

  44. [44]

    Journal of the Society for Industrial and Applied mathematics , volume=

    A dynamic programming approach to sequencing problems , author=. Journal of the Society for Industrial and Applied mathematics , volume=. 1962 , publisher=

    1962

  45. [45]

    Williams, Ryan , booktitle=. Strong

  46. [46]

    FOCS , year=

    Regularity lemmas and combinatorial algorithms , author=. FOCS , year=

  47. [47]

    and Lewenstein, Moshe , booktitle=

    Chan, Timothy M. and Lewenstein, Moshe , booktitle=. Clustered integer

  48. [48]

    Chan, Timothy M. and. Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted. STOC , year=

  49. [49]

    Kasliwal, Shashwat and Polak, Adam and Sharma, Pratyush , booktitle=

  50. [50]

    IPEC , year=

    The exponential time hypothesis and the parameterized clique problem , author=. IPEC , year=

  51. [51]

    SODA , year=

    Aggarwal, Divesh and Bennett, Huck and Golovnev, Alexander and. SODA , year=

  52. [52]

    Lower Bounds on the Complexity of

    Ganian, Robert and Hlineny, Petr and Langer, Alexander and Obdr. Lower Bounds on the Complexity of. STACS , year=

  53. [53]

    FOCS , year=

    Determinant Sums for Undirected Hamiltonicity , author=. FOCS , year=

  54. [54]

    FOCS , year=

    Near-optimal deterministic vertex-failure connectivity oracles , author=. FOCS , year=

  55. [55]

    Jiawei Han and Micheline Kamber and Jian Pei , title =

  56. [56]

    SOSA , year=

    Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems , author=. SOSA , year=

  57. [57]

    SODA , year=

    Faster online matrix-vector multiplication , author=. SODA , year=

  58. [58]

    STOC , year=

    Tight cell probe bounds for succinct boolean matrix-vector multiplication , author=. STOC , year=

  59. [59]

    PODS , year=

    On the complexity of inner product similarity join , author=. PODS , year=

  60. [60]

    STOC , year=

    Hardness of approximate nearest neighbor search , author=. STOC , year=

  61. [61]

    STOC , year=

    Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture , author=. STOC , year=

  62. [62]

    FOCS , year=

    Popular conjectures imply strong lower bounds for dynamic problems , author=. FOCS , year=

  63. [63]

    SIAM Journal on Computing , volume=

    On universal classes of extremely random constant-time hash functions , author=. SIAM Journal on Computing , volume=. 2004 , publisher=

    2004

  64. [64]

    FOCS , year=

    Higher cell probe lower bounds for evaluating polynomials , author=. FOCS , year=

  65. [65]

    STOC , year=

    Static data structure lower bounds imply rigidity , author=. STOC , year=

  66. [66]

    ITCS , year=

    Equivalence of systematic linear data structures and matrix rigidity , author=. ITCS , year=

  67. [67]

    Theory of Computing , volume=

    Lower bounds for data structures with space close to maximum imply circuit lower bounds , author=. Theory of Computing , volume=. 2019 , publisher=

    2019

  68. [68]

    SIAM Journal on Computing , volume=

    Distance oracles beyond the Thorup--Zwick bound , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

    2014

  69. [69]

    2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=

    A new infinity of distance oracles for sparse graphs , author=. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=. 2012 , organization=

    2012

  70. [70]

    MFCS , year=

    Graph-theoretic arguments in low-level complexity , author=. MFCS , year=

  71. [71]

    ITCS , year=

    The Orthogonal Vectors Conjecture for Branching Programs and Formulas , author=. ITCS , year=

  72. [72]

    ICALP , year=

    Abboud, Amir and. ICALP , year=

  73. [73]

    Alman, Josh and Li, Baitian , journal=