Pith. sign in

REVIEW 1 major objections 4 minor 157 references

Directed single-source shortest paths now have the same parallel work–span tradeoff as undirected graphs.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

For any t, directed shortest paths can be computed with near-linear work plus n^{1+o(1)}t^2 work and roughly n/t parallel depth, matching the undirected tradeoff.

T0 review reviewed 2026-08-01 challenge →

load-bearing objection Real algorithmic contribution, but Theorem 6.1's span derivation has a repairable parameter bug that should be fixed before the result is cited as stated. the 1 major comments →

arxiv 2607.19342 v1 pith:X3A3B432 submitted 2026-07-21 cs.DS

Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths

Isaac M. Hair , George Z. Li , Jason Li , Junkai Zhang This is my paper
classification cs.DS
keywords single-source shortest pathsparallel algorithmswork-span tradeoffdirected graphsnonnegative real weightslayered near-listheavy verticeshop-bounded search
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

This paper claims a deterministic parallel algorithm that, for any user-chosen t in [1,n], computes single-source shortest paths on nonnegative real-weighted directed graphs with O(n^{1+o(1)}t^2 + m^{1+o(1)}) work and O~(n/t) span. The significance is that this tradeoff curve was previously known only for undirected graphs; the directed case resisted all attempts to match it. The algorithm simulates t steps of the standard greedy shortest-path search per parallel round, using a two-level hierarchy of 'heavy' vertices and hop-bounded near-lists so that each round costs only subpolynomial span. If correct, the result interpolates between the near-linear-work linear-span extreme and the near-cubic-work polylog-span extreme of the problem, while remaining deterministic and free of integral-weight assumptions.

Core claim

The central claim is Theorem 6.1: for every t in [1,n], there is a deterministic parallel algorithm that solves single-source shortest paths on any nonnegative real-weighted directed graph with n vertices and m edges using O(n^{1+o(1)}t^2 + m^{1+o(1)}) work and O~(n/t) span. This is the first directed-graph algorithm to realize the tradeoff previously established for undirected graphs, and it simultaneously covers (up to subpolynomial factors) the two classical extremes: t=1 gives the near-linear-work, linear-span regime, and t=n gives near-cubic work with polylogarithmic span. The proof introduces a hierarchy of layered near-list data structures that maintain, for each vertex, the t closest

What carries the argument

The central object is the (h,k)-Layered Near-List (LNL) data structure. It stores a hierarchy of vertex subsets H_i ('heavy' sets) and, for each heavy vertex, a near-list of at most 2k unsettled vertices reachable within h hops in the graph with the next heavy set removed. The data structure supports batched deletions, plus place-marker and return-to-marker operations for rollback. A search lemma built on it finds, for any source, the k closest vertices reachable within qh hops using O~(k^2 q) work and O~(q) span. The main technical contribution is a recursive construction: an (h,2k)-LNL structure initializes a (ρh,k)-LNL structure whose hop bound is larger by a factor ρ, and updates are mad

Load-bearing premise

The load-bearing premise is that the effective tradeoff parameter T can be padded above the user-supplied t by a subpolynomial factor so the hierarchy's n^{o(1)} span overhead is absorbed; the proof fixes T ≤ t and then concludes the span bound from the reverse inequality, so the padding is the fragile step. If this padding cannot be made rigorous, the theorem's span guarantee degrades by an n^{o(1)} factor.

What would settle it

Pick a value of t that is exactly a power of the base ρ used in the construction, so the algorithm's effective parameter T equals t, and trace the final span accounting in Theorem 6.1. The proof derives O~(n/t) from T ≥ t/n^{o(1)}; when T = t this inequality is trivially true and provides no bound. If instead the correct derivation requires T ≥ t·n^{o(1)}, which the construction does not guarantee, then the actual span is O~(n^{1+o(1)}/t) and the claimed tradeoff fails by a subpolynomial factor—observable by checking whether the span analysis absorbs the n^{o(1)} overhead on the right side of

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Setting t=1 recovers the classical greedy-search extreme: near-linear work and O~(n) span, up to subpolynomial factors.
  • Setting t=n recovers the repeated matrix-product extreme: polylogarithmic span with near-cubic work.
  • Every intermediate t gives a smooth deterministic tradeoff, so the work–span frontier for directed graphs now matches the undirected frontier.
  • The algorithm applies to arbitrary nonnegative real weights without scaling or bit-length assumptions, making the guarantee strongly polynomial.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The written proof of Theorem 6.1 has a parameter-direction slip: it picks T as the largest power of ρ that is at most t, yet derives the O~(n/t) span from the inequality T ≥ t/n^{o(1)}, which has the wrong direction. A rigorous version would have to inflate t by a subpolynomial factor before defining T; as written, the span bound appears to be O~(n^{1+o(1)}/t) rather than O~(n/t) when T = t.
  • The two-hierarchy design—heavy vertices layered with hop-bounded near-lists—looks transferable to other parallel graph problems that have a batched greedy step and a hop-limited distance oracle, such as reachability or strongly connected components.
  • A concrete stress test is to run the algorithm on a directed path with t near n^{1/2}; the hop-bounded completeness invariant (a short near-list must contain every reachable vertex) is the part most likely to break under the adversarial deletion sequence used in the update analysis.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper presents a deterministic work-span algorithm for SSSP on nonnegative real-weighted directed graphs. For every parameter t in [1,n], it claims O(n^{1+o(1)}t^2 + m^{1+o(1)}) work and O~(n/t) span. The construction is a two-level hierarchy: a heavy-vertex hierarchy in the style of Karczmarz-Nadara-Sokolowski, and a hop-bounded near-list hierarchy in the style of Spencer. Layered Near-List (LNL) structures support batched deletions, markers, and rollback, and the top structure simulates Dijkstra in batches of T vertices. If correct, the tradeoff matches Shi-Spencer for undirected graphs and interpolates between parallel Dijkstra (t=1) and repeated min-plus squaring (t=n).

Significance. This is a substantial result. The proof is detailed and largely self-contained: LNL invariants are explicit, the search lemmas are proved by induction, update and rebuild schedules are analyzed with a transcript-width argument, and the batched Dijkstra correctness is argued through a boundary-key invariant. The algorithm is deterministic and builds on standard deterministic primitives such as sorting networks, parallel priority queues, and parallel BSTs. There is no circular dependence on the target result: the correctness of the Dijkstra layer rests on the search lemma, which is proved from the LNL invariants. The only substantive flaw is the parameterization in the proof of Theorem 6.1. That flaw is local and appears repairable; if the parameter choice is fixed, the paper would be a strong contribution to parallel graph algorithms.

major comments (1)
  1. [Theorem 6.1, proof (parameterization)] The final span bound in Theorem 6.1 does not follow from the written choice of T. T is defined as the largest power of rho at most min{t,n/rho}, so T <= t. The proof says it is enough to obtain O~(n^{1+o(1)}/T) and then uses T >= t/n^{o(1)} to conclude the theorem's O~(n/t). This is the wrong direction: T <= t gives n^{1+o(1)}/T >= n^{1+o(1)}/t, and T >= t/n^{o(1)} only yields n^{1+o(1)}/T <= n^{1+o(1)} * n^{o(1)}/t. Since O~ suppresses only polylogarithmic factors, the extra n^{o(1)} cannot be absorbed. The opening paragraph of the proof announces that t will be inflated by a subpolynomial factor before invoking the algorithm, but the subsequent definition of T is never changed; the proof needs T >= t*n^{o(1)} (e.g., T a power of rho at least t*rho), not T <= t. This is a load-bearing gap in the central theorem's derivation. It appears repairable by carrying the announced inflation thro
minor comments (4)
  1. [Theorem 6.1, proof] The case split between t < n^{1-o(1)} and t >= n^{1-o(1)} is not a well-defined property of a concrete instance, because n^{1-o(1)} is an asymptotic class. Specify a concrete subpolynomial threshold, for example n/rho^2, and state which case applies for a given t.
  2. [Theorem 6.1, proof] The sentence 'It is enough to obtain O(n^{1+o(1)}/t)' should be rephrased: as written, O(n^{1+o(1)}/t) is not O~(n/t). The intended meaning is that after inflating t by a subpolynomial factor, the span becomes O~(n/t). This is the same issue as the major comment but should be clarified for the reader.
  3. [Section 2, transcript width] It would help to state explicitly that marker/return operations may increase the vertex count and that transcript width counts only downward crossings. The proof of Lemma 5.5 relies on this convention.
  4. [Table 1] The row 'repeated min-plus product [Wil14]' lists work n^{3-o(1)}. The standard parallel repeated-squaring algorithm used in Theorem 6.1 has work O(n^3 log n) and polylog span; the citation to [Wil14] seems to concern a different APSP algorithm. Please either cite the standard algorithm or explain the connection.

Circularity Check

0 steps flagged

No significant circularity: the derivation is self-contained and the cited prior work provides independent machinery.

full rationale

The paper's central contribution is a hierarchical adaptation of existing LNL data structures, but the key invariants and search lemmas are proved directly from definitions rather than assumed from the target theorem. The base-level search primitive (h_J = 1) is implemented directly using the stored priority queues, so the hierarchy bottoms out in an independently verifiable operation. Correctness of the batched Dijkstra phase is argued via standard distance-estimate and ordering invariants, not by assuming the final O~(n/t) bound. Citations to sorting networks, parallel priority queues, Spencer's near-lists, and KNS26 LNLs are used as building blocks with independent content; no load-bearing step reduces to a self-citation. The only substantive weakness is in the final parameter choice of Theorem 6.1, where the proof claims O~(n/t) span from T >= t/n^{o(1)} while the derived span is O~(n^{1+o(1)}/T); this is a quantification/sign issue about whether the subpolynomial inflation of t is carried through, not a circular step. The target result is not assumed anywhere, and no fitted quantity is renamed as a prediction. Hence the circularity score is 0.

Axiom & Free-Parameter Ledger

3 free parameters · 5 axioms · 0 invented entities

The paper's central result rests on standard parallel primitives and algorithmic constructions rather than new physical or mathematical entities. The only hand-chosen quantities are asymptotic constants and the hop-growth factor rho, all internal to the proof.

free parameters (3)
  • rho = 2^{ceil(sqrt(log n))}
    Hop-growth factor per LNL level; chosen by hand so hierarchy depth is O(sqrt(log n)) and overhead is n^{o(1)}.
  • c1 = unspecified sufficiently large constant
    Threshold in the heavy-source counter game (Claim 5.2); must be large enough that remaining counters fall below k.
  • c2 = unspecified sufficiently large constant, c2 >> c1
    Schedules rebuild thresholds tau_i; chosen large enough to preserve |H_j| <= n/2^j between rebuilds.
axioms (5)
  • domain assumption Batched parallel priority queues and ordered-set operations exist with O(b polylog n) work and O(polylog n) span, deterministically.
    Invoked for graph queues, boundary queue, counters, and inverse-lists in Sections 2, 3, and 5.
  • domain assumption Sorting networks sort b real values in O(b polylog b) work and O(polylog b) span.
    Used in the truncation steps of Lemmas 3.1 and 3.4; cited from Batcher [Bat68].
  • domain assumption High-degree vertices can be replaced by constant-degree trees preserving SSSP distances and increasing n and m by constant factors.
    Section 2, 'Assume without loss of generality' paragraph; needed for graph-update work charges.
  • domain assumption Repeated squaring solves SSSP in O(n^3) work and polylog span.
    Used in Theorem 6.1 for values of t close to n; cited from Williams [Wil14].
  • standard math PRAM work-span model with deterministic scheduling and unit-cost comparisons/arithmetic on nonnegative reals.
    Background model assumed throughout the paper.

reviewed 2026-08-01 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths." pith.science (2026). https://pith.science/paper/X3A3B432

@misc{pith2026260719342,
  author       = {Pith},
  title        = {Pith review of: Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X3A3B432}},
  note         = {Machine review of arXiv:2607.19342}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We revisit the single-source shortest paths (SSSP) problem on directed graphs with nonnegative real weights and give a deterministic parallel algorithm with $O(n^{1+o(1)}t^2 + m^{1+o(1)})$ work and $\tilde{O}(n/t)$ span, for any $t \in [1, n]$. This matches (up to subpolynomial factors) the tradeoff due to [Shi and Spencer '99] for undirected graphs with nonnegative real weights.

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

157 extracted references · 12 linked inside Pith

  1. [1]

    Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Parallel approximate undirected shortest paths via low hop emulators , author=. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

  2. [2]

    Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Faster parallel algorithm for approximate shortest path , author=. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

  3. [3]

    Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Nearly work-efficient parallel algorithm for digraph reachability , author=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  4. [4]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Undirected (1+ ) -shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  5. [5]

    53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) , pages=

    Parallel Reachability and Shortest Paths on Non-Sparse Digraphs: Near-Linear Work and Sub-Square-Root Depth , author=. 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) , pages=. 2026 , organization=

    2026

  6. [6]

    SIAM Journal on Computing , volume=

    Hopsets with constant hopbound, and applications to approximate shortest paths , author=. SIAM Journal on Computing , volume=. 2019 , publisher=

    2019

  7. [7]

    Journal of the ACM (JACM) , volume=

    Polylog-time and near-linear work approximation scheme for undirected shortest paths , author=. Journal of the ACM (JACM) , volume=. 2000 , publisher=

    2000

  8. [8]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

    Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  9. [9]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Parallel exact shortest paths in almost linear work and square root depth , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  10. [10]

    32nd Annual European Symposium on Algorithms (ESA 2024) , pages=

    Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights , author=. 32nd Annual European Symposium on Algorithms (ESA 2024) , pages=. 2024 , organization=

    2024

  11. [11]

    2025 Symposium on Simplicity in Algorithms (SOSA) , pages=

    A simple parallel algorithm with near-linear work for negative-weight single-source shortest path , author=. 2025 Symposium on Simplicity in Algorithms (SOSA) , pages=. 2025 , organization=

    2025

  12. [12]

    International Colloquium on Automata, Languages, and Programming (ICALP 2017) , pages=

    Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs , author=. International Colloquium on Automata, Languages, and Programming (ICALP 2017) , pages=

    2017

  13. [13]

    Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    Faster all-pairs shortest paths via circuit complexity , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

  14. [14]

    Journal of the ACM (JACM) , volume=

    Time-work tradeoffs for parallel algorithms , author=. Journal of the ACM (JACM) , volume=. 1997 , publisher=

    1997

  15. [15]

    Proceedings of Structure in Complexity Theory

    A personal view of average-case complexity , author=. Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference , pages=. 1995 , organization=

    1995

  16. [16]

    Proceedings of the nineteenth annual ACM symposium on Theory of computing , pages=

    Matching is as easy as matrix inversion , author=. Proceedings of the nineteenth annual ACM symposium on Theory of computing , pages=

  17. [17]

    Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

    2026

  18. [18]

    Journal of algorithms , volume=

    Time--work tradeoffs of the single-source shortest paths problem , author=. Journal of algorithms , volume=. 1999 , publisher=

    1999

  19. [19]

    Proceedings of the April 30--May 2, 1968, spring joint computer conference , pages=

    Sorting networks and their applications , author=. Proceedings of the April 30--May 2, 1968, spring joint computer conference , pages=

    1968

  20. [20]

    Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures , pages=

    A Deterministic Work-Depth Tradeoff for Strongly Connected Components , author=. Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures , pages=

  21. [21]

    Journal of Parallel and Distributed Computing , volume=

    A parallel priority queue with constant time operations , author=. Journal of Parallel and Distributed Computing , volume=. 1998 , publisher=

    1998

  22. [22]

    Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures , pages=

    Just join for parallel ordered sets , author=. Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures , pages=

  23. [23]

    Parallel algorithms for shortest path problems , author=. Proc. 1985 International Conference on Parallel Processing , pages=

    1985

  24. [24]

    Proceedings of the seventeenth annual ACM symposium on Theory of computing , pages=

    A simple parallel algorithm for the maximal independent set problem , author=. Proceedings of the seventeenth annual ACM symposium on Theory of computing , pages=

  25. [25]

    Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures , pages=

    Greedy sequential maximal independent set and matching are parallel on average , author=. Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures , pages=

  26. [26]

    Communications of the ACM , volume=

    Secure communications over insecure channels , author=. Communications of the ACM , volume=. 1978 , publisher=

    1978

  27. [27]

    Proceedings of the seventeenth annual ACM symposium on Theory of computing , pages=

    Constructing a perfect matching is in random NC , author=. Proceedings of the seventeenth annual ACM symposium on Theory of computing , pages=

  28. [28]

    arXiv preprint arXiv:2505.17360 , year=

    The quasi-polynomial low-degree conjecture is false , author=. arXiv preprint arXiv:2505.17360 , year=

    Pith/arXiv arXiv

  29. [29]

    Proceedings of the 4th conference on Innovations in Theoretical Computer Science , pages=

    On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction , author=. Proceedings of the 4th conference on Innovations in Theoretical Computer Science , pages=

  30. [30]

    IEEE Transactions on Information Theory , volume=

    Reed--Muller codes: Theory and algorithms , author=. IEEE Transactions on Information Theory , volume=. 2020 , publisher=

    2020

  31. [31]

    Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    On the performance of Reed-Muller codes with respect to random errors and erasures , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    2020

  32. [32]

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels , author=. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2023 , organization=

    2023

  33. [33]

    Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages=

    Reed-Muller codes for random erasures and errors , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages=

  34. [34]

    Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

    CSP gaps and reductions in the Lasserre hierarchy , author=. Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

  35. [35]

    Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Sum of squares lower bounds for refuting any CSP , author=. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  36. [36]

    Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=

    Polynomial integrality gaps for strong sdp relaxations of densest k-subgraph , author=. Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=. 2012 , organization=

    2012

  37. [37]

    Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Approximation algorithms for label cover and the log-density threshold , author=. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2017 , organization=

    2017

  38. [38]

    Annual International Cryptology Conference , pages=

    Merkle puzzles are optimal—an O (n 2)-query attack on any key exchange from a random oracle , author=. Annual International Cryptology Conference , pages=. 2009 , organization=

    2009

  39. [39]

    Communications of the ACM , volume=

    A method for obtaining digital signatures and public-key cryptosystems , author=. Communications of the ACM , volume=. 1978 , publisher=

    1978

  40. [40]

    Digitalized signatures and public-key functions as intractable as factorization , author=

  41. [41]

    Theory of Cryptography Conference , pages=

    Basing weak public-key cryptography on strong one-way functions , author=. Theory of Cryptography Conference , pages=. 2008 , organization=

    2008

  42. [42]

    44th Annual IEEE Symposium on Foundations of Computer Science, 2003

    More on average case vs approximation complexity , author=. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. , pages=. 2003 , organization=

    2003

  43. [43]

    Journal of the ACM (JACM) , volume=

    On lattices, learning with errors, random linear codes, and cryptography , author=. Journal of the ACM (JACM) , volume=. 2009 , publisher=

    2009

  44. [44]

    Discrete Mathematics , volume=

    Some recent problems and results in graph theory , author=. Discrete Mathematics , volume=. 1997 , publisher=

    1997

  45. [45]

    Geometric & Functional Analysis GAFA , volume=

    A sum-product estimate in finite fields, and applications , author=. Geometric & Functional Analysis GAFA , volume=. 2004 , publisher=

    2004

  46. [46]

    International Mathematics Research Notices , volume=

    An explicit sum-product estimate in Fp , author=. International Mathematics Research Notices , volume=. 2007 , publisher=

    2007

  47. [47]

    Proceedings of the American Mathematical Society , pages=

    A slight improvement to Garaev's sum product estimate , author=. Proceedings of the American Mathematical Society , pages=. 2008 , publisher=

    2008

  48. [48]

    Mathematical Proceedings of the Cambridge Philosophical Society , volume=

    On a variant of sum-product estimates and explicit exponential sum bounds in prime fields , author=. Mathematical Proceedings of the Cambridge Philosophical Society , volume=. 2009 , organization=

    2009

  49. [49]

    arXiv preprint arXiv:0907.2051 , year=

    Slightly improved sum-product estimates in fields of prime order , author=. arXiv preprint arXiv:0907.2051 , year=

    Pith/arXiv arXiv 2051

  50. [50]

    International Mathematics Research Notices , volume=

    An improved sum--product inequality in fields of prime order , author=. International Mathematics Research Notices , volume=. 2012 , publisher=

    2012

  51. [51]

    Advances in Mathematics , volume=

    New sum-product type estimates over finite fields , author=. Advances in Mathematics , volume=. 2016 , publisher=

    2016

  52. [52]

    Proceedings of the American Mathematical Society , volume=

    Stronger sum-product inequalities for small sets , author=. Proceedings of the American Mathematical Society , volume=

  53. [53]

    International Mathematics Research Notices , volume=

    Attaining the exponent 5/4 for the sum-product problem in finite fields , author=. International Mathematics Research Notices , volume=. 2023 , publisher=

    2023

  54. [54]

    Studies in pure mathematics , pages=

    On sums and products of integers , author=. Studies in pure mathematics , pages=. 1983 , publisher=

    1983

  55. [55]

    How to find groups?(and how to use them in Erd

    Elekes, Gy. How to find groups?(and how to use them in Erd. Combinatorica , volume=. 2012 , publisher=

    2012

  56. [56]

    Polynomials vanishing on Cartesian products: The Elekes--Szab

    Raz, Orit E and Sharir, Micha and De Zeeuw, Frank , year=. Polynomials vanishing on Cartesian products: The Elekes--Szab

  57. [57]

    Polynomials vanishing on grids: The Elekes-R

    Raz, Orit E and Sharir, Micha and Solymosi, J. Polynomials vanishing on grids: The Elekes-R. Proceedings of the thirtieth annual symposium on Computational geometry , pages=

  58. [58]

    The Elekes--Szab

    Raz, Orit E and Sharir, Micha and de Zeeuw, Frank , journal=. The Elekes--Szab. 2018 , publisher=

    2018

  59. [59]

    Approximation, Randomization, and Combinatorial Optimization

    Unbalanced expanders from multiplicity codes , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) , pages=. 2022 , organization=

    2022

  60. [60]

    Current Developments in Mathematics , volume=

    On the proof of the 2-to-2 games conjecture , author=. Current Developments in Mathematics , volume=. 2019 , publisher=

    2019

  61. [61]

    Combinatorics, Probability and Computing , volume=

    An almost m-wise independent random permutation of the cube , author=. Combinatorics, Probability and Computing , volume=. 1996 , publisher=

    1996

  62. [62]

    International Colloquium on Automata, Languages, and Programming , pages=

    Limitations of algebraic approaches to graph isomorphism testing , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2015 , organization=

    2015

  63. [63]

    2020 IEEE International Symposium on Information Theory (ISIT) , pages=

    Capacity-achieving polar-based ldgm codes with crowdsourcing applications , author=. 2020 IEEE International Symposium on Information Theory (ISIT) , pages=. 2020 , organization=

    2020

  64. [64]

    Conference on Learning Theory , pages=

    Open problem: Average-case hardness of hypergraphic planted clique detection , author=. Conference on Learning Theory , pages=. 2020 , organization=

    2020

  65. [65]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Average-radius list-recoverability of random linear codes , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  66. [66]

    arXiv preprint arXiv:2503.19069 , year=

    Detecting Arbitrary Planted Subgraphs in Random Graphs , author=. arXiv preprint arXiv:2503.19069 , year=

    Pith/arXiv arXiv

  67. [67]

    Improved Elekes-Szab

    Solymosi, Jozsef and Zahl, Joshua , journal=. Improved Elekes-Szab. 2024 , publisher=

    2024

  68. [68]

    The Elekes—Szab

    Makhul, Mehdi and Roche-Newton, Oliver and Stevens, Sophie and Warren, Audie , journal=. The Elekes—Szab. 2022 , publisher=

    2022

  69. [69]

    arXiv preprint arXiv:2205.14059 , year=

    Convexity, Squeezing, and the Elekes-Szab ' \ o \ Theorem , author=. arXiv preprint arXiv:2205.14059 , year=

    Pith/arXiv arXiv

  70. [70]

    Expanding polynomials: A generalization of the Elekes-R

    Raz, Orit E and Shem-Tov, Zvi , journal=. Expanding polynomials: A generalization of the Elekes-R. 2020 , publisher=

    2020

  71. [71]

    A survey of Elekes-R

    de Zeeuw, Frank , booktitle=. A survey of Elekes-R. 2018 , publisher=

    2018

  72. [72]

    Theory of Cryptography Conference , pages=

    Public-key encryption, local pseudorandom generators, and the low-degree method , author=. Theory of Cryptography Conference , pages=. 2023 , organization=

    2023

  73. [73]

    Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages=

    Pseudorandom generators with long stretch and low locality from random local one-way functions , author=. Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages=

  74. [74]

    Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages=

    Relations between average case complexity and approximation complexity , author=. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages=

  75. [75]

    Proceedings of the tenth annual ACM symposium on Theory of computing , pages=

    The complexity of satisfiability problems , author=. Proceedings of the tenth annual ACM symposium on Theory of computing , pages=

  76. [76]

    Strong Refutation of Semirandom k-LIN over Larger Fields , author=

  77. [77]

    Proceedings of the 57th Annual ACM SIGACT Symposium on Theory of Computing , year=

    Using the Planted Clique Conjecture for Cryptography: Public Key Encryption from Planted Clique and Noisy kLIN Over Expanders , author=. Proceedings of the 57th Annual ACM SIGACT Symposium on Theory of Computing , year=

  78. [78]

    Proceedings of the forty-second ACM symposium on Theory of computing , pages=

    Public-key cryptography from different assumptions , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=

  79. [79]

    arXiv preprint arXiv:1212.3365 , year=

    Expanding polynomials over the rationals , author=. arXiv preprint arXiv:1212.3365 , year=

    Pith/arXiv arXiv

  80. [80]

    Annual International Cryptology Conference , pages=

    k-SUM in the Sparse Regime: Complexity and Applications , author=. Annual International Cryptology Conference , pages=. 2024 , organization=

    2024

Showing first 80 references.

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.