pith. sign in

arxiv: 2507.14462 · v5 · submitted 2025-07-19 · 💻 cs.DS · cs.CC

Near-Optimality for Single-Source Personalized PageRank

Xinpeng Jiang , Haoyu Liu , Siqiang Luo , Xiaokui Xiao This is my paper

Pith reviewed 2026-05-19 04:38 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords single-source personalized pagerankgraph algorithmsapproximation algorithmslower boundscomputational complexityrandom walksquery processing
0
0 comments X

The pith

Single-source personalized PageRank queries achieve matching upper and lower bounds for most graphs.

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

The paper tightens the time complexity for single-source personalized PageRank, which computes the probability that a decaying random walk starting at one node ends at each other node. It gives faster upper bounds for both the absolute-error and relative-error versions while proving stronger lower bounds that nearly close the previous gap. The bounds now match exactly for the relative-error case on graphs with enough edges, establishing that the algorithms run as fast as any possible in the worst case. This clarifies the fundamental limits of an operation used widely in ranking, recommendations, and graph analysis.

Core claim

We improve the upper bound for absolute-error SSPPR to O(1/ε²) and for relative-error SSPPR-R to O(min(log(1/δ)/δ, m + n log n log(log n/(m δ)))). We prove matching lower bounds Ω(min(m, 1/ε²)) for SSPPR-A and Ω(min(m, log(1/δ)/δ)) for SSPPR-R. These coincide for SSPPR-R on graphs with m ∈ Ω(n log² n) and any δ with 1/δ ∈ O(poly(n)), giving the first optimal results for SSPPR queries. The same techniques raise the lower bound for single-target personalized PageRank to Ω(min(m, n log n / δ)), which now matches its upper bound.

What carries the argument

The new algorithms achieving the stated upper bounds together with the worst-case graph constructions that force the matching lower bounds on query time.

If this is right

  • Relative-error SSPPR-R reaches theoretical optimality on all graphs with m in Omega(n log squared n) edges.
  • Absolute-error SSPPR-A matches the lower bound when the allowed error is sufficiently large.
  • Single-target personalized PageRank now has matching upper and lower bounds.
  • The techniques provide a template for proving optimality on other random-walk queries.

Where Pith is reading between the lines

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

  • In graphs that are sparser than the Omega(n log squared n) threshold, there may still be room for faster algorithms.
  • If real graphs contain extra structure such as communities or low diameter, practical running times could beat the worst-case bounds shown here.
  • Implementations in graph databases can now target these bounds as a performance target without expecting asymptotic gains in the worst case.

Load-bearing premise

The matching optimality claims depend on the existence of graphs with at least Omega(n log squared n) edges and on error thresholds whose reciprocal is polynomial in the number of nodes.

What would settle it

An algorithm that answers relative-error SSPPR-R in asymptotically less than m + n log n log(log n / (m δ)) time on some graph with m = Omega(n log squared n) edges, or a stronger lower bound that exceeds the new upper bound in the same regime.

Figures

Figures reproduced from arXiv: 2507.14462 by Haoyu Liu, Siqiang Luo, Xiaokui Xiao, Xinpeng Jiang.

Figure 1
Figure 1. Figure 1: Graph instance family U(n, D, d) = U(3, 2, 1). (a) denotes our base graph instance family U(n, D, d) and (b) represents the r-padded instance U(r) based on U. 12 [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An example for generating graph distribution Σ( [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Instance U −1 (r) Lemma 26 (STPPR-R). Let U−1 denote the inverse graph of a graph U obtained by reversing the direction of each edge. Choose any decay factor α ∈ (0, 1), error parameter c ≤ 1 2 , and functions δ0(n0) ∈ [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An example for generating graph distribution [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of a 2-Lift. Our proof begins by considering how an algorithm A can operate on a multi-graph U(r) whose edge multiplicity is bounded by L. Intuitively, we construct an L-simple lift of U(r) by creating L parallel copies of every node and edge, thereby transforming U(r) into a simple graph. This lifted graph allows A to run as if it were operating on a simple graph, while its queries can be sim… view at source ↗
read the original abstract

The \emph{Single-Source Personalized PageRank} (SSPPR) query is central to graph OLAP, measuring the probability $\pi(s,t)$ that an $\alpha$-decay random walk from node $s$ terminates at $t$. Despite decades of research, a significant gap remains between upper and lower bounds for its computational complexity. Existing upper bounds are $O\left(\min\left(\frac{\log(1/\epsilon)}{\epsilon^2}, \frac{\sqrt{m \log n}}{\epsilon}, m \log \frac{1}{\epsilon}\right)\right)$ for SSPPR-A and $O\left(\min\left(\frac{\log(1/n)}{\delta}, \sqrt{m \log(n/\delta)}, m \log \left(\frac{\log(n)}{m\delta}\right)\right)\right)$ for SSPPR-R, with trivial lower bounds of $\Omega(\min(n,1/\epsilon))$ and $\Omega(\min(n,1/\delta))$. This work narrows or closes this gap. We improve the upper bounds for SSPPR-A and SSPPR-R to $O\left(\frac{1}{\epsilon^2}\right)$ and $O\left(\min\left(\frac{\log(1/\delta)}{\delta}, m + n \log(n) \log \left(\frac{\log(n)}{m\delta}\right)\right)\right)$, respectively, offering improvements by factors of $\log(1/\epsilon)$ and $\log\left(\frac{\log(n)}{m\delta}\right)$. On the lower bound side, we establish stronger results: $\Omega(\min(m, 1/\epsilon^2))$ for SSPPR-A and $\Omega(\min(m, \frac{\log(1/\delta)}{\delta}))$ for SSPPR-R, strengthening theoretical foundations. Our upper and lower bounds for SSPPR-R coincide for graphs with $m \in \Omega(n \log^2 n)$ and any threshold $\delta, 1/\delta \in O(\text{poly}(n))$, achieving theoretical optimality in most graph regimes. The SSPPR-A query attains partial optimality for large error thresholds, matching our new lower bound. This is the first optimal result for SSPPR queries. Our techniques generalize to the Single-Target Personalized PageRank (STPPR) query, improving its lower bound from $\Omega(\min(n, 1/\delta))$ to $\Omega(\min(m, \frac{n}{\delta} \log n))$, matching the upper bound and revealing its optimality.

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

1 major / 2 minor

Summary. The manuscript presents improved upper bounds for Single-Source Personalized PageRank queries under absolute approximation (SSPPR-A) and relative error (SSPPR-R) models, together with matching or near-matching lower bounds. For SSPPR-R the new upper bound is O(min(log(1/δ)/δ, m + n log n ⋅ log(log n/(m δ)))), paired with a lower bound Ω(min(m, log(1/δ)/δ)); the two coincide for m = Ω(n log² n) and 1/δ polynomial in n. Parallel improvements are claimed for SSPPR-A (upper bound O(1/ε²) matching a new Ω(min(m, 1/ε²)) lower bound for large ε) and for the single-target variant STPPR, where the lower bound is strengthened to Ω(min(m, n log n / δ)) and matches the known upper bound.

Significance. If the stated bounds and their proofs hold, the paper supplies the first tight (or near-tight) complexity characterization for SSPPR queries over a broad range of graph densities and error parameters. The explicit matching of upper and lower bounds for SSPPR-R in the regime m ∈ Ω(n log² n) constitutes a concrete theoretical advance; the generalization to STPPR that closes its gap is likewise a clear contribution. The work rests on standard random-walk analysis and combinatorial constructions rather than ad-hoc constants, which strengthens its foundational value for graph-algorithmic complexity.

major comments (1)
  1. [Abstract] Abstract and §1: the optimality claim for SSPPR-R is conditioned on m ∈ Ω(n log² n) and 1/δ ∈ poly(n). The manuscript should explicitly verify that, under these constraints, the second term in the new upper bound is asymptotically dominated by log(1/δ)/δ (or state the precise case distinction used).
minor comments (2)
  1. Clarify the precise definition of the relative-error threshold δ versus the absolute-error threshold ε in the problem statements and throughout the technical sections.
  2. [Abstract] The abstract lists an upper bound containing the term n log n ⋅ log(log n/(m δ)); a brief pointer to the section deriving this additive term would aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment and the recommendation of minor revision. The single major comment is addressed below with a clarification that will be incorporated into the revised manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract and §1: the optimality claim for SSPPR-R is conditioned on m ∈ Ω(n log² n) and 1/δ ∈ poly(n). The manuscript should explicitly verify that, under these constraints, the second term in the new upper bound is asymptotically dominated by log(1/δ)/δ (or state the precise case distinction used).

    Authors: We thank the referee for highlighting the need for explicit verification. Let A ≔ log(1/δ)/δ and let B ≔ m + n log n ⋅ log(log n/(m δ)). Under the stated regime m ∈ Ω(n log² n) and 1/δ ∈ poly(n), the argument of the inner logarithm satisfies log n/(m δ) = O(n^{O(1)-1}/log n), so log(log n/(m δ)) = O(log n). Consequently B = O(m + n (log n)²) = O(m). The new upper bound therefore simplifies to min(A, O(m)). Combined with the lower bound Ω(min(m, A)), the two sides are asymptotically equivalent (both Θ(min(m, A))). This establishes the claimed coincidence without requiring B = O(A) in every subcase. We will revise the abstract and the relevant paragraph in §1 to state this case analysis and the resulting simplification explicitly. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in bound derivations

full rationale

The paper presents improved upper bounds derived from new algorithmic constructions for SSPPR-A and SSPPR-R queries, alongside stronger lower bounds obtained through independent combinatorial hardness arguments and graph constructions. The claimed coincidence of upper and lower bounds for SSPPR-R on graphs with m ∈ Ω(n log² n) and polynomial 1/δ follows directly from comparing these separately proven quantities, without any reduction of a result to its own fitted parameters, self-definitional equations, or load-bearing self-citations. The STPPR generalization similarly matches an existing upper bound via a new lower-bound proof. All steps rely on standard random-walk analysis and explicit worst-case constructions rather than renaming or smuggling prior ansatzes, rendering the derivation chain self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard definitions of alpha-decay random walks and worst-case graph families; no free parameters are fitted and no new entities are postulated.

axioms (2)
  • domain assumption Alpha-decay random walk terminates with probability alpha at each step and follows graph edges uniformly otherwise
    Defines the SSPPR probability pi(s,t) used throughout the complexity statements.
  • standard math Standard RAM model with unit-cost word operations for graph algorithms
    Underpins all time-bound statements in the abstract.

pith-pipeline@v0.9.0 · 6016 in / 1295 out tokens · 45213 ms · 2026-05-19T04:38:34.784619+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

138 extracted references · 138 canonical work pages · 4 internal anchors

  1. [1]

    An elementary introduction to modern convex geometry

    Keith Ball et al. An elementary introduction to modern convex geometry. Flavors of geometry , 31(1--58):26, 1997

    work page 1997

  2. [2]

    K. Ball. The Reverse Isoperimetric Problem for Gaussian Measure . Discrete and Computational Geometry , 10:411--420, 1993

    work page 1993

  3. [3]

    Constructive algorithms for discrepancy minimization

    Nikhil Bansal. Constructive algorithms for discrepancy minimization. In IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS) , pages 3--10, 2010

    work page 2010

  4. [4]

    Belovs and E

    A. Belovs and E. Blais. A polynomial lower bound for testing monotonicity. In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC) , pages 1021--1032, 2016

    work page 2016

  5. [5]

    On testing and robust characterizations of convexity

    Eric Blais and Abhinav Bommireddi. On testing and robust characterizations of convexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages 18:1--18:15, 2020

    work page 2020

  6. [6]

    Testing convexity of functions over finite domains

    Aleksandrs Belovs, Eric Blais, and Abhinav Bommireddi. Testing convexity of functions over finite domains. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 2030--2045, 2020

    work page 2020

  7. [7]

    Testing and learning convex sets in the ternary hypercube

    Hadley Black, Eric Blais, and Nathaniel Harms. Testing and learning convex sets in the ternary hypercube. In 15th Innovations in Theoretical Computer Science Conference, ITCS , pages 15:1--15:21, 2024

    work page 2024

  8. [8]

    Earthmover resilience and testing in ordered structures

    Omri Ben - Eliezer and Eldar Fischer. Earthmover resilience and testing in ordered structures. In 33rd Computational Complexity Conference, CCC , pages 18:1--18:35, 2018

    work page 2018

  9. [9]

    M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences , 47:549--595, 1993

    work page 1993

  10. [10]

    The Power and Limitations of Uniform Samples in Testing Properties of Figures

    Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. The Power and Limitations of Uniform Samples in Testing Properties of Figures . In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) , pages 45:1--45:14, 2016

    work page 2016

  11. [11]

    Testing convexity of figures under the uniform distribution

    Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Testing convexity of figures under the uniform distribution. Random Struct. Algorithms , 54(3):413--443, 2019

    work page 2019

  12. [12]

    Tolerant testers of image properties

    Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Tolerant testers of image properties. ACM Trans. Algorithms , 18(4):37:1--37:39, 2022

    work page 2022

  13. [13]

    C. Borell. The Brunn-Minkowski inequality in Gauss space . Invent. Math. , 30:207--216, 1975

    work page 1975

  14. [14]

    The Ehrhard inequality

    Christer Borell. The Ehrhard inequality . Comptes Rendus. Math\' e matique , 337(10):663--666, 2003

    work page 2003

  15. [15]

    C. Borell. Inequalities of the Brunn--Minkowski type for Gaussian measures . Probability Theory and Related Fields , 140:195--205, 2008

    work page 2008

  16. [16]

    L_p -testing

    Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p -testing. In Symposium on Theory of Computing, STOC 2014 , pages 164--173, 2014

    work page 2014

  17. [17]

    Lower bounds for testing properties of functions over hypergrid domains

    Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In IEEE 29th Conference on Computational Complexity, CCC 2014 , pages 309--320, 2014

    work page 2014

  18. [18]

    Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas

    Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A Servedio. Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4321--4337. SIAM, 2024

    work page 2024

  19. [19]

    Servedio

    Eshan Chattopadhyay, Anindya De, and Rocco A. Servedio. Simple and efficient pseudorandom generators from gaussian processes. In Amir Shpilka, editor, 34th Computational Complexity Conference (CCC) , volume 137 of LIPIcs , pages 4:1--4:33. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2019

    work page 2019

  20. [20]

    X. Chen, A. De, R. Servedio, and L. - Y. Tan. Boolean Function Monotonicity Testing Requires (Almost) n^ 1/2 Non-adaptive Queries . In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015 , pages 519--528, 2015

    work page 2015

  21. [21]

    The (b) conjecture for the gaussian measure of dilates of symmetric convex sets and related problems

    Dario Cordero-Erausquin, Matthieu Fradelizi, and Bernard Maurey. The (b) conjecture for the gaussian measure of dilates of symmetric convex sets and related problems. Journal of Functional Analysis , 214(2):410--427, 2004

    work page 2004

  22. [22]

    X. Chen, A. Freilich, R. Servedio, and T. Sun. Sample-based high-dimensional convexity testing. In Proceedings of the 17th Int. Workshop on Randomization and Computation (RANDOM) , pages 37:1--37:20, 2017

    work page 2017

  23. [23]

    Seshadhri

    Deeparnab Chakrabarty and C. Seshadhri. A o(n) monotonicity tester for boolean functions over the hypercube. In Proceedings of the 45th ACM Symposium on Theory of Computing , pages 411--418, 2013

    work page 2013

  24. [24]

    Servedio, and Li-Yang Tan

    Xi Chen, Rocco A. Servedio, and Li-Yang Tan. New algorithms and lower bounds for testing monotonicity. In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science , pages 286--295, 2014

    work page 2014

  25. [25]

    Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

    Xi Chen, Erik Waingarten, and Jinyu Xie. Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages 523--536, 2017

    work page 2017

  26. [26]

    Anindya De, Elchanan Mossel, and Joe Neeman. Is your function low dimensional? In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA , volume 99 of Proceedings of Machine Learning Research , pages 979--993. PMLR , 2019

    work page 2019

  27. [27]

    Robust testing of low dimensional functions

    Anindya De, Elchanan Mossel, and Joe Neeman. Robust testing of low dimensional functions. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 584--597. ACM , 2021

    work page 2021

  28. [28]

    Servedio

    Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Quantitative correlation inequalities via semigroup interpolation. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021 , volume 185 of LIPIcs , pages 69:1--69:20, 2021

    work page 2021

  29. [29]

    Servedio

    Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Convex influences. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS , volume 215 of LIPIcs , pages 53:1--53:21, 2022

    work page 2022

  30. [30]

    Servedio

    Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Testing C onvex T runcation. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4050--4082. 2023

    work page 2023

  31. [31]

    Servedio

    Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Gaussian A pproximation of C onvex S ets by I ntersections of H alfspaces. In Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS) , 2024. To appear

    work page 2024

  32. [32]

    Probability: Theory and Examples

    Rick Durrett. Probability: Theory and Examples . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 5 edition, 2019

    work page 2019

  33. [33]

    Second-order bounds on correlations between increasing families

    Ronen Eldan. Second-order bounds on correlations between increasing families. Combinatorica , 42:1099--1118, 2022

    work page 2022

  34. [34]

    An introduction to probability theory and its applications , volume 1

    William Feller. An introduction to probability theory and its applications , volume 1. Wiley, 3rd edition, 1968

    work page 1968

  35. [35]

    Goldreich, S

    O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samordinsky. Testing monotonicity. Combinatorica , 20(3):301--337, 2000

    work page 2000

  36. [36]

    Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces

    Efim Davydovich Gluskin. Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces. Mathematics of the USSR-Sbornik , 64(1):85, 1989

    work page 1989

  37. [37]

    Gopalan, R

    P. Gopalan, R. O'Donnell, Y. Wu, and D. Zuckerman. Fooling functions of halfspaces under product distributions. In IEEE Conf. on Computational Complexity (CCC) , pages 223--234, 2010

    work page 2010

  38. [38]

    On proximity-oblivious testing

    Oded Goldreich and Dana Ron. On proximity-oblivious testing. SIAM Journal on Computing , 40(2):534--566, 2011

    work page 2011

  39. [39]

    On sample-based testers

    Oded Goldreich and Dana Ron. On sample-based testers. ACM Trans. Comput. Theory , 8(2):7:1--7:54, 2016

    work page 2016

  40. [40]

    P. M. Gruber and J. M. Wills, editors. Handbook of Convex Geometry . Elsevier, 1993

    work page 1993

  41. [41]

    Hsu, Clayton Hendrick Sanford, Rocco A

    Daniel J. Hsu, Clayton Hendrick Sanford, Rocco A. Servedio, and Emmanouil - Vasileios Vlatakis - Gkaragkounis. Near-optimal statistical query lower bounds for agnostically learning intersections of halfspaces with gaussian marginals. In Po - Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK , volume 178 of Proc...

    work page 2022

  42. [42]

    Lectures on Convex Geometry

    Daniel Hug and Wolfgang Weil. Lectures on Convex Geometry . Springer Graduate Texts in Mathematics, 2020

    work page 2020

  43. [43]

    Downsampling for testing and learning in product distributions

    Nathaniel Harms and Yuichi Yoshida. Downsampling for testing and learning in product distributions. In 49th International Colloquium on Automata, Languages, and Programming, ( ICALP ) , pages 71:1--71:19, 2022

    work page 2022

  44. [44]

    Johnstone

    Iain M. Johnstone. Chi-square oracle inequalities. In State of the art in probability and statistics , pages 399--418. Institute of Mathematical Statistics, 2001

    work page 2001

  45. [45]

    D. M. Kane. The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions . Computational Complexity , 20(2):389--412, 2011

    work page 2011

  46. [46]

    D. Kane. A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions . In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012 , pages 91--100, 2012

    work page 2012

  47. [47]

    D. Kane. A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length . In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014 , pages 217--228, 2014

    work page 2014

  48. [48]

    D. M. Kane. A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting . In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA , pages 567--581, 2015

    work page 2015

  49. [49]

    A. R. Klivans and P. Kothari. Embedding Hard Learning Problems Into Gaussian Space . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014 , pages 793--809, 2014

    work page 2014

  50. [50]

    On monotonicity testing and boolean isoperimetric-type theorems

    Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean isoperimetric-type theorems. SIAM J. Comput. , 47(6):2238--2276, 2018

    work page 2018

  51. [51]

    Testing surface area

    Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, and Chenggang Wu. Testing surface area. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 . SIAM , 2014

    work page 2014

  52. [52]

    Klivans, R

    A. Klivans, R. O'Donnell, and R. Servedio. Learning geometric concepts via G aussian surface area. In Proc.\ 49th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 541--550, 2008

    work page 2008

  53. [53]

    On some inequalities for gaussian measures

    Rafa Lata a. On some inequalities for gaussian measures. In Proceedings of the ICM , volume 2, pages 813--822, 2002

    work page 2002

  54. [54]

    I. E. Leonard and J. E. Lewis. Geometry of Convex Sets . Wiley, 2015

    work page 2015

  55. [55]

    Laurent and P

    B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics , 28(5):1302--1338, 2000

    work page 2000

  56. [56]

    Constructive discrepancy minimization by walking on the edges

    Shachar Lovett and Raghu Meka. Constructive discrepancy minimization by walking on the edges. SIAM Journal on Computing , 44(5):1573--1582, 2015

    work page 2015

  57. [57]

    Gaussian measures of dilatations of convex symmetric sets

    Rafa Lata a and Krzysztof Oleszkiewicz. Gaussian measures of dilatations of convex symmetric sets. The Annals of Probability , 27(4):1922--1938, 10 1999

    work page 1922

  58. [58]

    Small ball probability estimates in terms of width

    Rafa Lata a and Krzysztof Oleszkiewicz. Small ball probability estimates in terms of width. Studia Mathematica , 169(3):305--314, 2005

    work page 2005

  59. [59]

    Deterministic discrepancy minimization via the multiplicative weight update method

    Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss. Deterministic discrepancy minimization via the multiplicative weight update method. In International Conference on Integer Programming and Combinatorial Optimization (IPCO) , pages 380--391, 2017

    work page 2017

  60. [60]

    McDiarmid

    C. McDiarmid. On the method of bounded differences. In Surveys in Combinatorics 1989 , pages 148--188. London Mathematical Society Lecture Notes, 1989

    work page 1989

  61. [61]

    On the noise sensitivity of monotone functions

    Elchanan Mossel and Ryan O'Donnell. On the noise sensitivity of monotone functions. Random Structures & Algorithms , 23(3):333--350, 2003

    work page 2003

  62. [62]

    Matulef, R

    K. Matulef, R. O'Donnell, R. Rubinfeld, and R. Servedio. Testing halfspaces. SIAM J. on Comput. , 39(5):2004--2047, 2010

    work page 2004

  63. [63]

    Gaussian bounds for noise correlation of functions and tight analysis of long codes

    Elchanan Mossel. Gaussian bounds for noise correlation of functions and tight analysis of long codes. FOCS , pages 156--165, 2008

    work page 2008

  64. [64]

    F. Nazarov. On the maximal perimeter of a convex set in ^n with respect to a Gaussian measure . In Geometric aspects of functional analysis (2001-2002) , pages 169--187. Lecture Notes in Math., Vol. 1807, Springer, 2003

    work page 2001

  65. [65]

    Servedio, Li - Yang Tan, and Daniel Kane

    Ryan O'Donnell, Rocco A. Servedio, Li - Yang Tan, and Daniel Kane. Fooling Gaussian PTFs via local hyperconcentration . Preliminary version in STOC 2020. Revised version includes an appendix by Daniel Kane, 2021

    work page 2020

  66. [66]

    Approximation by DNF: examples and counterexamples

    Ryan O'Donnell and Karl Wimmer. Approximation by DNF: examples and counterexamples . In International Colloquium on Automata, Languages, and Programming , pages 195--206. Springer, 2007

    work page 2007

  67. [67]

    On testing convexity and submodularity

    Michal Parnas, Dana Ron, and Ronitt Rubinfeld. On testing convexity and submodularity. SIAM J. Comput. , 32(5):1158--1184, 2003

    work page 2003

  68. [68]

    Tolerant property testing and distance approximation

    Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. J. Comput. Syst. Sci. , 72(6):1012--1042, 2006

    work page 2006

  69. [69]

    Pallavoor, Sofya Raskhodnikova, and Nithin Varma

    Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Parameterized property testing of functions. ACM Trans. Comput. Theory , 9(4):17:1--17:19, 2018

    work page 2018

  70. [70]

    Pallavoor, S

    R. Pallavoor, S. Raskhodnikova, and E. Waingarten. Approximating the distance to monotonicity of Boolean functions . Random Struct. Algorithms , 60(2):233--260, 2022

    work page 2022

  71. [71]

    Approximate testing of visual properties

    Sofya Raskhodnikova. Approximate testing of visual properties. In 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003 , pages 370--381, 2003

    work page 2003

  72. [72]

    Constructive discrepancy minimization for convex sets

    Thomas Rothvoss. Constructive discrepancy minimization for convex sets. SIAM Journal on Computing , 46(1):224--234, 2017

    work page 2017

  73. [73]

    Lattices: CSE 599S---Winter 2023 Lecture Notes , 2023

    Thomas Rothvoss. Lattices: CSE 599S---Winter 2023 Lecture Notes , 2023. URL: https://sites.math.washington.edu/ rothvoss/599-winter-2023/lattices.pdf

    work page 2023

  74. [74]

    A simple proof of the Gaussian correlation conjecture extended to multivariate gamma distributions

    Thomas Royen. A simple proof of the G aussian correlation conjecture extended to multivariate gamma distributions. 2014. http://arxiv.org/abs/1408.1028 arXiv:1408.1028

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  75. [75]

    The subspace flatness conjecture and faster integer programming

    Victor Reis and Thomas Rothvoss. The subspace flatness conjecture and faster integer programming. In IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 974--988, 2023

    work page 2023

  76. [76]

    Vector balancing in lebesgue spaces

    Victor Reis and Thomas Rothvoss. Vector balancing in lebesgue spaces. Random Structures & Algorithms , 62(3):667--688, 2023

    work page 2023

  77. [77]

    Rubinfeld and M

    R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing , 25:252--271, 1996

    work page 1996

  78. [78]

    A reverse M inkowski theorem

    Oded Regev and Noah Stephens-Davidowitz. A reverse M inkowski theorem. Annals of Mathematics , 199(1):1--49, 2024

    work page 2024

  79. [79]

    Testing geometric convexity

    Luis Rademacher and Santosh Vempala. Testing geometric convexity. In FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science: 24th International Conference, 2004 , pages 469--480, 2005

    work page 2004

  80. [80]

    Talagrand

    M. Talagrand. How much are increasing sets positively correlated? Combinatorica , 16(2):243--258, 1996

    work page 1996

Showing first 80 references.