Pith. sign in

REVIEW 4 minor 300 references

Active Learning on Adversarially Corrupted Graphs

T0 review · 0 major / 4 minor · reviewed 2026-07-11 · grok-4.5

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

Pith's one-line read Active learning recovers adversarially hidden vertices when query cost scales with adversary budget and the graph's vertex expansion.

desk verdict Clean theoretical result: neighborhood-budget adversary + cardinality-constrained SoS expansion finder yields the first explicit poly dependence of active-learning queries on vertex expansion. read the letter →

arxiv 2607.04869 v1 pith:24WNCNZ2 submitted 2026-07-06 cs.LG stat.ML

Marco Bressan , Nicolò Cesa-Bianchi , Tommaso d`Orsi , Emmanuel Esposito , Silvio Lattanzi This is my paper
classification cs.LGstat.ML
keywords activelearningadversarialrobustnessvertexexpansionsum-of-squaresweakrecoverycorruptedgraphslabelqueries
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Malicious actors can inject fake vertices into a network and wire them arbitrarily, but they can touch only a limited number of honest vertices. This paper shows that an active learner can still recover most of the fake set by querying only a number of labels that is polynomial in the adversary's contact budget and in the vertex expansion of the original graph. Vertex expansion measures how well-connected large pieces of the graph are; when it is large relative to the adversary's budget, every low-expansion set of the right size must heavily overlap the corrupted set. The algorithm repeatedly finds such a set with a sum-of-squares relaxation that also respects cardinality constraints, labels a few random vertices to decide which side is corrupted, removes the set, and recurses. The result is the first explicit link between vertex expansion and the label complexity of structural-adversary-robust active learning.

What carries the argument

A degree-4 sum-of-squares relaxation of cardinality-constrained vertex expansion (Theorem 4), together with a rounding procedure that returns a set S of size Θ(m) whose expansion is within an O(sqrt(log n)+n/m) factor of the optimum; when the corrupted set is poorly expanding, every such S is heavily correlated with it.

What would settle it

Construct a clean graph whose ηn-large vertex expansion is large, inject a corrupted set of size Θ(n) whose neighborhood is smaller than the budget bound of Theorem 3, run the algorithm, and check whether the returned set differs from the true corrupted set by more than γn vertices on a constant fraction of random seeds.

Watch

Extended reading notes

Core claim

There is a randomized polynomial-time algorithm that, given only the corrupted graph and a label oracle, returns a set whose symmetric difference with the true corrupted set is at most γn, using a number of queries that is roughly (1/γ) times (log(1/δ) plus b times square-root of log n), provided the adversary's neighborhood budget b is smaller than a poly(γ)/sqrt(log n) fraction of the ηn-large frontier of the clean graph.

Load-bearing premise

The corrupted set itself must expand far less than every large piece of the remaining clean graph; if that gap fails, low-expansion sets recovered by the algorithm need not overlap the corrupted set.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. The paper introduces an adversarial model in which a budget-b adversary hides a set I of corrupted vertices inside an arbitrary host graph G* by adding an arbitrary graph on I, arbitrary edges from I to at most b vertices of G*, and arbitrary edges inside G*. Given only the resulting graph G and a label oracle, the goal is (γ,δ,q,b)-weak recovery of I (symmetric-difference error at most γn). The main result (Theorem 3) is a randomized polynomial-time algorithm whose query complexity is polynomial in b, 1/γ and log(1/δ) whenever b is smaller than a suitable multiple of the large-set vertex expansion of G*. The algorithmic engine is a degree-4 sum-of-squares procedure (Theorem 4) that returns a set of size Θ(m) whose vertex expansion is within an O(√log n + n/m) factor of the optimum among all sets of size in [m,n-m]; this set is then used iteratively, with graceful degradation of expansion parameters, to peel off successive pieces of I.

Significance. If the claims hold, the work supplies the first explicit quantitative link between vertex expansion and the query complexity of active learning under structural (rather than label) adversarial attacks. The neighborhood-budget model is strictly harder and more realistic than classical Sybil models that charge the adversary per edge and assume expansion of the clean graph. The cardinality-constrained SoS rounding (Algorithm 1 + Lemmas 16–22) is of independent interest and improves upon prior small-set expansion approximations in the unbalanced regime. The reduction chain (Lemmas 10–14) is complete, self-contained, and free of circularity; all free parameters are universal constants or standard approximation factors arising from ARV-style structure theorems.

minor comments (4)
  1. The simplified statements of Lemmas 6/7/10 and Theorem 8 hide several logarithmic factors that reappear in the full versions (Appendix A); a short remark early in Section 3 clarifying that all poly-log factors are tracked in the appendices would improve readability.
  2. Notation for frontiers is slightly inconsistent: ∂_m(G) (Eq. 1.1) versus ϕ_m(G) and the later use of ∂_t(G*_k). A single sentence in the notation paragraph would eliminate ambiguity.
  3. Algorithm 1 (Appendix B) is described in prose that mixes the randomized analysis (random threshold t) with the deterministic implementation; a short pseudocode block distinguishing the two would help.
  4. A few typographical slips remain (e.g., “eG” for the corrupted graph, occasional missing spaces around math operators). They do not affect correctness.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: guarantees follow from explicit expansion hypothesis plus independent SoS/rounding analysis

full rationale

The derivation chain is self-contained and non-circular. Theorem 3 is obtained by showing that the modeling premise (I is (ε,ηm,m)-expanding, Definition 5) implies the hypotheses of the single-iteration finder (Lemma 10), which itself rests on a degree-4 SoS relaxation of cardinality-constrained vertex expansion (Theorem 4 / Algorithm 1, adapting Feige et al. 2005 and Arora et al. 2009 structure theorem) together with a correlation lemma (Lemma 22). Iterative removal is justified by explicit monotonicity and degradation bounds (Lemmas 11–14) that track how ϕ and ∂ change after each successful removal; the final query and error accounting is ordinary Chernoff + union bound. No quantity is defined in terms of a later “prediction,” no parameter is fitted to data and re-used as a forecast, and load-bearing citations (Feige, Arora–Rao–Vazirani, Menger, standard SoS duality) are external classical results, not self-citations of unverified uniqueness claims. The expansion hypothesis is stated as an assumption, not derived from the conclusion. Hence the result does not reduce to its inputs by construction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 3 invented entities

The paper is pure theory; free parameters are only the universal constants that must be chosen small enough for the inequalities to close. Axioms are standard combinatorial and SoS facts plus the paper’s own adversarial model and expansion definitions. Invented entities are the model itself and the auxiliary notions needed to state the guarantees.

free parameters (2)
  • universal constants c1..c5, c2
    Chosen sufficiently small so that the expansion gap, size lower bounds, and error accumulation across O(log 1/γ) iterations remain non-vacuous; they appear in Lemmas 10–11 and Theorem 9.
  • approximation factor α = O(√log n + n/m)
    Inherited from the SoS rounding analysis (Theorem 4) and then plugged into the expansion gap required of I; not fitted to data but fixed by the analysis.
assumptions (5)
  • standard math Degree-4 sum-of-squares pseudo-distributions satisfy the ℓ2^{2} triangle inequality and induce negative-type metrics (Corollary 27, Fact 25).
    Used to justify the pseudo-metric dμ and the subsequent rounding in Appendix B.
  • standard math Menger’s theorem: vertex connectivity equals the size of a minimum vertex separator (Theorem 20).
    Invoked in the analysis of Algorithm 1 to bound the size of the separator Ui.
  • standard math Arora-Rao-Vazirani structure theorem for negative-type metrics (Lemma 21).
    Supplies the well-separated sets X,Y when the pseudo-distribution is well-spread.
  • domain assumption The adversarial construction of Definition 1 (arbitrary I-graph, at most b attachments into G*, arbitrary edges inside G*).
    Defines the input distribution over which weak recovery is claimed; without it the expansion hypothesis is meaningless.
  • ad hoc to paper I is (ε,ηm,m)-expanding in G with the concrete polynomial gap of Theorem 9.
    The central modeling hypothesis that makes every low-expansion set recovered by SoS heavily correlated with I (Lemma 22).
invented entities (3)
  • Adversarial model of Definition 1 (neighborhood-budget corruption)
    purpose: Captures realistic Sybil/link-farm attacks while remaining strictly harder than edge-budget models.
    New relative to the cited Sybil literature; independent evidence is only the informal real-world motivation paragraphs.
  • (ε,t,m)-expanding set (Definition 5)
    purpose: Formalizes the “poorly expanding” property that the algorithm exploits.
    Introduced to state the sufficient condition for the SoS rounding to succeed; no external falsifiable prediction.
  • (γ,δ,q,b)-weak recovery (Definition 2)
    purpose: Precise success criterion for the active-learning algorithm.
    Standard-style definition tailored to the model; no independent evidence required.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Active Learning on Adversarially Corrupted Graphs." pith.science (2026). https://pith.science/paper/24WNCNZ2

@misc{pith2026260704869,
  author       = {Pith},
  title        = {Pith review of: Active Learning on Adversarially Corrupted Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/24WNCNZ2}},
  note         = {Machine review of arXiv:2607.04869}
}
abstract

Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of \emph{corrupted vertices} inside a graph $G^*$. To this end, the adversary can add edges between the corrupted vertices, as well as edges between the corrupted vertices and $G^*$, and its power is then measured by the size of the \emph{neighborhood} of the corrupted vertices in $G^*$. Our goal is to design an active learning algorithm that efficiently finds the subset of corrupted vertices using a small number of label queries. We devise an efficient algorithm that approximately recovers the corrupted vertices with a query complexity that depends polynomially on both the power of the adversary and the \emph{vertex expansion} of $G^*$, a fundamental measure of graph connectivity. At the heart of this result is a polynomial-time algorithm, obtained by carefully adapting sum-of-squares algorithms for approximating minimum expansion, that finds a set with small vertex expansion subject to cardinality constraints. To the best of our knowledge, this is the first time that the vertex expansion is shown to play a key role in determining the query complexity of active learning algorithms robust to structural adversarial attacks.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

300 extracted references · 1 canonical work pages

  1. [1]

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

    Approximations for the isoperimetric and spectral profile of graphs and related parameters , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=

  2. [2]

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

    Algorithms approaching the threshold for semi-random planted clique , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  3. [3]

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

    Robust recovery for stochastic block models, simplified and generalized , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

  4. [4]

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

    New Approximation Bounds for Small-Set Vertex Expansion , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  5. [5]

    2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Cheeger inequalities for vertex expansion and reweighted eigenvalues , author=. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2022 , organization=

    2022

  6. [6]

    Theory of Computing , volume=

    Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion , author=. Theory of Computing , volume=. 2016 , publisher=

    2016

  7. [7]

    arXiv preprint arXiv:2412.17115 , year=

    Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs , author=. arXiv preprint arXiv:2412.17115 , year=

    arXiv

  8. [8]

    Ergun and Zhili Feng and Sandeep Silwal and David P

    Jon C. Ergun and Zhili Feng and Sandeep Silwal and David P. Woodruff and Samson Zhou , title =. The Tenth International Conference on Learning Representations,. 2022 , url =

    2022

Show all 300 references
  1. [9]

    Conference on Learning Theory , pages=

    Approximate cluster recovery from noisy labels , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  2. [10]

    Journal of the ACM (JACM) , volume=

    Competitive caching with machine learned advice , author=. Journal of the ACM (JACM) , volume=. 2021 , publisher=

    2021

  3. [11]

    Conference on Learning Theory , pages=

    Clustering with queries under semi-random noise , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  4. [12]

    Proceedings of The Web Conference 2020 , pages=

    Clustering with a faulty oracle , author=. Proceedings of The Web Conference 2020 , pages=

    2020

  5. [13]

    Advances in Neural Information Processing Systems , volume=

    Clustering with noisy queries , author=. Advances in Neural Information Processing Systems , volume=

  6. [14]

    9th Innovations in Theoretical Computer Science Conference (ITCS 2018) , year=

    Approximate Clustering with Same-Cluster Queries , author=. 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) , year=

    2018

  7. [15]

    Advances in neural information processing systems , volume=

    Clustering with same-cluster queries , author=. Advances in neural information processing systems , volume=

  8. [16]

    Communications of the ACM , volume=

    Algorithms with predictions , author=. Communications of the ACM , volume=. 2022 , publisher=

    2022

  9. [17]

    Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Partitioning into expanders , author=. Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2014 , organization=

    2014

  10. [18]

    2012 , publisher=

    Geometric algorithms and combinatorial optimization , author=. 2012 , publisher=

    2012

  11. [19]

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

    Higher degree sum-of-squares relaxations robust against oblivious outliers , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  12. [20]

    arXiv preprint arXiv:1711.11581 , year=

    Outlier-robust moment-estimation via sum-of-squares , author=. arXiv preprint arXiv:1711.11581 , year=

    arXiv

  13. [21]

    SIAM Journal on Computing , volume=

    Limitations on explicit constructions of expanding graphs , author=. SIAM Journal on Computing , volume=. 1984 , publisher=

    1984

  14. [22]

    22nd Annual Symposium on Foundations of Computer Science (sfcs 1981) , pages=

    Non-existence of one-dimensional expanding graphs , author=. 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981) , pages=. 1981 , organization=

    1981

  15. [23]

    Annals of mathematics , volume=

    Harmonic functions on manifolds , author=. Annals of mathematics , volume=. 1997 , publisher=

    1997

  16. [24]

    Mathematische Zeitschrift , volume=

    Eigenvalue comparison theorems and its geometric applications , author=. Mathematische Zeitschrift , volume=. 1975 , publisher=

    1975

  17. [25]

    The Thirty-eighth Annual Conference on Neural Information Processing Systems , year=

    Learning-augmented approximation algorithms for maximum cut and related problems , author=. The Thirty-eighth Annual Conference on Neural Information Processing Systems , year=

  18. [26]

    Forty-first International Conference on Machine Learning,

    Evripidis Bampis and Bruno Escoffier and Michalis Xefteris , title =. Forty-first International Conference on Machine Learning,

  19. [27]

    Internet Mathematics , volume=

    Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters , author=. Internet Mathematics , volume=. 2009 , publisher=

    2009

  20. [28]

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

    Many sparse cuts via higher eigenvalues , author=. Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages=

  21. [29]

    arXiv preprint arXiv:2304.07284 , year=

    Solving unique games over globally hypercontractive graphs , author=. arXiv preprint arXiv:2304.07284 , year=

    arXiv

  22. [30]

    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Playing unique games on certified small-set expanders , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

  23. [31]

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

    High dimensional expanders: Eigenstripping, pseudorandomness, and unique games , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

    2022

  24. [32]

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

    On independent sets, 2-to-2 games, and Grassmann graphs , author=. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  25. [33]

    2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Pseudorandom sets in grassmann graph have near-perfect expansion , author=. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2018 , organization=

    2018

  26. [34]

    Proceedings of 37th conference on foundations of computer science , pages=

    The regularity lemma and approximation schemes for dense problems , author=. Proceedings of 37th conference on foundations of computer science , pages=. 1996 , organization=

    1996

  27. [35]

    2009 , institution=

    A spectral algorithm for improving graph partitions , author=. 2009 , institution=

    2009

  28. [36]

    , author=

    An algorithm for improving graph partitions. , author=. SODA , volume=

  29. [37]

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

    Unique games on expanding constraint graphs are easy , author=. Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

  30. [38]

    arXiv preprint arXiv:0806.1745 , year=

    Eigenvalue multiplicity and volume growth , author=. arXiv preprint arXiv:0806.1745 , year=

    arXiv

  31. [39]

    Czechoslovak mathematical journal , volume=

    Algebraic connectivity of graphs , author=. Czechoslovak mathematical journal , volume=. 1973 , publisher=

    1973

  32. [40]

    Journal of the American Mathematical Society , volume=

    A new proof of Gromov’s theorem on groups of polynomial growth , author=. Journal of the American Mathematical Society , volume=

  33. [41]

    Geometric & Functional Analysis GAFA , volume=

    Moderate growth and random walk on finite groups , author=. Geometric & Functional Analysis GAFA , volume=. 1994 , publisher=

    1994

  34. [42]

    Geometry and Combinatorics , pages=

    Equilateral point sets in elliptic geometry , author=. Geometry and Combinatorics , pages=. 1991 , publisher=

    1991

  35. [43]

    Combinatorica , volume=

    Spherical two-distance sets and eigenvalues of signed graphs , author=. Combinatorica , volume=. 2023 , publisher=

    2023

  36. [44]

    Journal of Functional Analysis , volume=

    Ricci curvature of Markov chains on metric spaces , author=. Journal of Functional Analysis , volume=. 2009 , publisher=

    2009

  37. [45]

    Geometric and Functional Analysis , volume=

    Sparse expanders have negative curvature , author=. Geometric and Functional Analysis , volume=. 2022 , publisher=

    2022

  38. [46]

    Annales scientifiques de l'

    A note on the isoperimetric constant , author=. Annales scientifiques de l'

  39. [47]

    Near-Optimal Cayley Expanders for Abelian Groups , booktitle =

    Akhil Jalan and Dana Moshkovitz , editor =. Near-Optimal Cayley Expanders for Abelian Groups , booktitle =. 2021 , url =. doi:10.4230/LIPICS.FSTTCS.2021.24 , timestamp =

    2021 doi

  40. [48]

    Journal of Combinatorial Theory, Series B , volume=

    Spectra of Cayley graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 1979 , publisher=

    1979

  41. [49]

    Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 8th International Conference, AAECC-8 Tokyo, Japan, August 20--24, 1990 Proceedings 8 , pages=

    Applications of cayley graphs , author=. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 8th International Conference, AAECC-8 Tokyo, Japan, August 20--24, 1990 Proceedings 8 , pages=. 1991 , organization=

    1990

  42. [50]

    arXiv preprint arXiv:1809.09829 , year=

    Eigenvalues of Cayley graphs , author=. arXiv preprint arXiv:1809.09829 , year=

    arXiv

  43. [51]

    Eurocomb 2003 , volume=

    Discrepancy and eigenvalues of cayley graphs , author=. Eurocomb 2003 , volume=

    2003

  44. [52]

    Journal of Combinatorial Theory, Series B , volume=

    Spectral estimates for abelian Cayley graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 2006 , publisher=

    2006

  45. [53]

    Proceedings of the London Mathematical Society , volume=

    Hypergraph expanders of all uniformities from Cayley graphs , author=. Proceedings of the London Mathematical Society , volume=. 2020 , publisher=

    2020

  46. [54]

    Combinatorica , volume=

    Ramanujan graphs , author=. Combinatorica , volume=

  47. [55]

    International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=

    A new regularity lemma and faster approximation algorithms for low threshold rank graphs , author=. International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=. 2013 , organization=

    2013

  48. [56]

    Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Approximating non-uniform sparsest cut via generalized spectra , author=. Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2013 , organization=

    2013

  49. [57]

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

    Faster SDP hierarchy solvers for local rounding algorithms , author=. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=. 2012 , organization=

    2012

  50. [58]

    2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages=

    Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives , author=. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages=. 2011 , organization=

    2011

  51. [59]

    computational complexity , volume=

    Spectral algorithms for unique games , author=. computational complexity , volume=. 2011 , publisher=

    2011

  52. [60]

    arXiv preprint arXiv:1807.09898 , year=

    Mildly exponential time approximation algorithms for vertex cover, uniform sparsest cut and related problems , author=. arXiv preprint arXiv:1807.09898 , year=

    arXiv

  53. [61]

    computational complexity , volume=

    On the hardness of approximating multicut and sparsest-cut , author=. computational complexity , volume=. 2006 , publisher=

    2006

  54. [62]

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

    Graph expansion and the unique games conjecture , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=

  55. [63]

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

    On the power of unique 2-prover 1-round games , author=. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages=

  56. [64]

    Journal of the ACM (JACM) , volume=

    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms , author=. Journal of the ACM (JACM) , volume=. 1999 , publisher=

    1999

  57. [65]

    Problems in analysis , volume=

    A lower bound for the smallest eigenvalue of the Laplacian , author=. Problems in analysis , volume=. 1970 , publisher=

    1970

  58. [66]

    Stirling's approximation , author=

  59. [67]

    Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages=

    Integrality gaps for sparsest cut and minimum linear arrangement problems , author=. Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages=

  60. [68]

    2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages=

    Towards a better approximation for sPARsEst CUt? , author=. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages=. 2013 , organization=

    2013

  61. [69]

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

    Approximating Small Sparse Cuts , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

  62. [70]

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

    Expander decomposition and pruning: Faster, stronger, and simpler , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    2019

  63. [71]

    Trevisan, Luca , journal=

  64. [72]

    In Theory blog , year=

  65. [73]

    Random Structures & Algorithms , volume=

    Random Cayley graphs and expanders , author=. Random Structures & Algorithms , volume=. 1994 , publisher=

    1994

  66. [74]

    Journal of the ACM (JACM) , volume=

    Multiway spectral partitioning and higher-order cheeger inequalities , author=. Journal of the ACM (JACM) , volume=. 2014 , publisher=

    2014

  67. [75]

    Non-negative Ollivier curvature on graphs, reverse Poincar

    M. Non-negative Ollivier curvature on graphs, reverse Poincar. Journal de Math. 2023 , publisher=

    2023

  68. [76]

    URl: https://people

    Lecture notes on expansion, sparsest cut, and spectral graph theory , author=. URl: https://people. eecs. berkeley. edu/\

  69. [77]

    University of California, Berkeley, https://lucatrevisan.github.io/books/expanders-2016.pdf , year=

    Lecture notes on graph partitioning, expanders and spectral methods , author=. University of California, Berkeley, https://lucatrevisan.github.io/books/expanders-2016.pdf , year=

    2016

  70. [78]

    Diffusions hypercontractives , author=. S. 2006 , publisher=

    2006

  71. [79]

    Canadian Journal of Mathematics , volume=

    Discrete curvature and abelian groups , author=. Canadian Journal of Mathematics , volume=. 2016 , publisher=

    2016

  72. [80]

    Combinatorica , volume=

    Edge-isoperimetric inequalities in the grid , author=. Combinatorica , volume=. 1991 , publisher=

    1991

  73. [81]

    arXiv preprint arXiv:1512.03037 , year=

    The independence number of a subset of an abelian group , author=. arXiv preprint arXiv:1512.03037 , year=

    arXiv

  74. [82]

    International Conference on Machine Learning , pages=

    Differentially private hierarchical clustering with provable approximation guarantees , author=. International Conference on Machine Learning , pages=. 2023 , organization=

    2023

  75. [83]

    Advances in Neural Information Processing Systems , volume=

    Privacy induces robustness: Information-computation gaps and sparse mean estimation , author=. Advances in Neural Information Processing Systems , volume=

  76. [84]

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

    Robustness implies privacy in statistical estimation , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  77. [85]

    On Rings of Operators

    John Von Neumann , journal =. On Rings of Operators. Reduction Theory , volume =

  78. [86]

    2019 IEEE Symposium on Security and Privacy (SP) , pages=

    Towards practical differentially private convex optimization , author=. 2019 IEEE Symposium on Security and Privacy (SP) , pages=. 2019 , organization=

    2019

  79. [87]

    Conference on Learning Theory , pages=

    Private convex empirical risk minimization and high-dimensional regression , author=. Conference on Learning Theory , pages=. 2012 , organization=

    2012

  80. [88]

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

    The geometry of differential privacy: the sparse and approximate cases , author=. Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

  81. [89]

    Advances in Neural Information Processing Systems , volume=

    Differential privacy dynamics of langevin diffusion and noisy gradient descent , author=. Advances in Neural Information Processing Systems , volume=

  82. [90]

    Innovations in Computer Science (poster) , year=

    An analysis of the Chaudhuri and Monteleoni algorithm , author=. Innovations in Computer Science (poster) , year=

  83. [91]

    Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages=

    Private multiplicative weights beyond linear queries , author=. Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages=

  84. [92]

    rem , volume=

    Private empirical risk minimization, revisited , author=. rem , volume=. 2014 , publisher=

    2014

  85. [93]

    International Conference on Machine Learning , pages=

    (Near) dimension independent risk bounds for differentially private learning , author=. International Conference on Machine Learning , pages=. 2014 , organization=

    2014

  86. [94]

    2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages=

    Local privacy and statistical minimax rates , author=. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages=. 2013 , organization=

    2013

  87. [95]

    Conference on Learning Theory , pages=

    Differentially private feature selection via stability arguments, and the robustness of the lasso , author=. Conference on Learning Theory , pages=. 2013 , organization=

    2013

  88. [96]

    Conference on Learning Theory , pages=

    Differentially private online learning , author=. Conference on Learning Theory , pages=. 2012 , organization=

    2012

  89. [97]

    , author=

    Differentially private empirical risk minimization. , author=. Journal of Machine Learning Research , volume=

  90. [98]

    Advances in neural information processing systems , volume=

    Privacy-preserving logistic regression , author=. Advances in neural information processing systems , volume=

  91. [99]

    Israel Journal of Mathematics , volume=

    On Lipschitz embedding of finite metric spaces in Hilbert space , author=. Israel Journal of Mathematics , volume=. 1985 , publisher=

    1985

  92. [100]

    Conference on Learning Theory , pages=

    Reducibility and statistical-computational gaps from secret leakage , author=. Conference on Learning Theory , pages=. 2020 , organization=

    2020

  93. [101]

    arXiv preprint arXiv:1605.00903 , year=

    Sum-of-squares certificates for maxima of random tensors on the sphere , author=. arXiv preprint arXiv:1605.00903 , year=

    arXiv

  94. [102]

    2010 IEEE 51st annual symposium on foundations of computer science , pages=

    A multiplicative weights mechanism for privacy-preserving data analysis , author=. 2010 IEEE 51st annual symposium on foundations of computer science , pages=. 2010 , organization=

    2010

  95. [103]

    Advances in neural information processing systems , volume=

    A simple and practical algorithm for differentially private data release , author=. Advances in neural information processing systems , volume=

  96. [104]

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

    Privately releasing conjunctions and the statistical query barrier , author=. Proceedings of the forty-third annual ACM symposium on Theory of computing , pages=

  97. [105]

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

    The price of privately releasing contingency tables and the spectra of random matrices with correlated rows , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=

  98. [106]

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

    Optimal differentially private learning of thresholds and quasi-concave optimization , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  99. [107]

    Set-Valued Analysis , volume=

    On the convergence of von Neumann's alternating projection algorithm for two sets , author=. Set-Valued Analysis , volume=. 1993 , publisher=

    1993

  100. [108]

    Applicable Analysis , volume=

    Strong convergence of infinite products of orthogonal projections in Hilbert space , author=. Applicable Analysis , volume=. 1995 , publisher=

    1995

  101. [109]

    arXiv preprint arXiv:1411.5417 , year=

    Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry , author=. arXiv preprint arXiv:1411.5417 , year=

    arXiv

  102. [110]

    Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , pages=

    Privacy, accuracy, and consistency too: a holistic solution to contingency table release , author=. Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , pages=

  103. [111]

    Discrete & Computational Geometry , volume=

    Efficient algorithms for privately releasing marginals via convex relaxations , author=. Discrete & Computational Geometry , volume=. 2015 , publisher=

    2015

  104. [112]

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

    Complexity theoretic limitations on learning halfspaces , author=. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages=

  105. [113]

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

    From average case complexity to improper learning complexity , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

  106. [114]

    , author=

    Random Satisfiability. , author=. Handbook of Satisfiability , volume=

  107. [115]

    Combinatorics, Probability and Computing , volume=

    Strong refutation heuristics for random k-SAT , author=. Combinatorics, Probability and Computing , volume=. 2007 , publisher=

    2007

  108. [116]

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

    Proof of the satisfiability conjecture for large k , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=

  109. [117]

    probabilistic polynomial time , author=

    In search of an easy witness: Exponential time vs. probabilistic polynomial time , author=. Journal of Computer and System Sciences , volume=. 2002 , publisher=

    2002

  110. [118]

    2009 , publisher=

    Approximating np-hard problems efficient algorithms and their limits , author=. 2009 , publisher=

    2009

  111. [119]

    SIAM journal on computing , volume=

    Classifying the complexity of constraints using finite algebras , author=. SIAM journal on computing , volume=. 2005 , publisher=

    2005

  112. [120]

    Journal of Physics A: Mathematical and General , volume=

    The 3-SAT problem with large number of clauses in the infinity-replica symmetry breaking scheme , author=. Journal of Physics A: Mathematical and General , volume=. 2002 , publisher=

    2002

  113. [121]

    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=

  114. [122]

    Electronic Colloquium on Computational Complexity (ECCC) , volume=

    A gap in average proof complexity , author=. Electronic Colloquium on Computational Complexity (ECCC) , volume=. 2002 , organization=

    2002

  115. [123]

    Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol

    Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry , author=. Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II--IV: Invited Lectures , pages=. 2010 , orga...

    2010

  116. [124]

    Algorithms , volume=

    A survey on approximation in parameterized complexity: Hardness and algorithms , author=. Algorithms , volume=. 2020 , publisher=

    2020

  117. [125]

    2009 , publisher=

    Computational complexity: a modern approach , author=. 2009 , publisher=

    2009

  118. [126]

    Foundations and Trends

    The algorithmic foundations of differential privacy , author=. Foundations and Trends. 2014 , publisher=

    2014

  119. [127]

    arXiv preprint arXiv:1911.05911 , year=

    Recent advances in algorithmic high-dimensional robust statistics , author=. arXiv preprint arXiv:1911.05911 , year=

    1911 arXiv

  120. [128]

    8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , year=

    SOS is not obviously automatizable, even approximately , author=. 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , year=

    2017

  121. [129]

    arXiv preprint arXiv:1607.02986 , year=

    A birthday repetition theorem and complexity of approximating dense CSPs , author=. arXiv preprint arXiv:1607.02986 , year=

    arXiv

  122. [130]

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

    Approximating CSPs with global cardinality constraints using SDP hierarchies , author=. Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=. 2012 , organization=

    2012

  123. [131]

    Advances in Neural Information Processing Systems , volume=

    Private estimation algorithms for stochastic block models and mixture models , author=. Advances in Neural Information Processing Systems , volume=

  124. [132]

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

    Private graphon estimation via sum-of-squares , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

  125. [133]

    Conference on Learning Theory , pages=

    Fast algorithm for overcomplete order-3 tensor decomposition , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  126. [134]

    Computational Complexity Conference , year=

    A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs , author=. Computational Complexity Conference , year=

  127. [135]

    Conference on Learning Theory , pages=

    Exact tensor completion with sum-of-squares , author=. Conference on Learning Theory , pages=. 2017 , organization=

    2017

  128. [136]

    , author=

    Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. , author=. Electron. Colloquium Comput. Complex. , volume=

  129. [137]

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

    Dictionary learning and tensor decomposition via the sum-of-squares method , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=

  130. [138]

    Multi-View Stochastic Block Models , booktitle =

    Vincent Cohen. Multi-View Stochastic Block Models , booktitle =. 2024 , url =

    2024

  131. [139]

    2010 , publisher=

    On the complexity of unique games and graph expansion , author=. 2010 , publisher=

    2010

  132. [140]

    Perturb-and-Project: Differentially Private Similarities and Marginals , booktitle =

    Vincent Cohen. Perturb-and-Project: Differentially Private Similarities and Marginals , booktitle =. 2024 , url =

    2024

  133. [141]

    International Conference on Machine Learning , pages=

    A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering , author=. International Conference on Machine Learning , pages=. 2024 , organization=

    2024

  134. [142]

    The Thirty Sixth Annual Conference on Learning Theory , pages=

    Reaching kesten-stigum threshold in the stochastic block model under node corruptions , author=. The Thirty Sixth Annual Conference on Learning Theory , pages=. 2023 , organization=

    2023

  135. [143]

    Journal of the ACM (JACM) , volume=

    Subexponential algorithms for unique games and related problems , author=. Journal of the ACM (JACM) , volume=. 2015 , publisher=

    2015

  136. [144]

    2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes , author=. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2020 , organization=

    2020

  137. [145]

    Conference on Learning Theory , pages=

    Lattice-based methods surpass sum-of-squares in clustering , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  138. [146]

    Advances in Neural Information Processing Systems , year=

    Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis , author=. Advances in Neural Information Processing Systems , year=

  139. [147]

    The Journal of Machine Learning Research , volume=

    Community detection and stochastic block models: recent developments , author=. The Journal of Machine Learning Research , volume=. 2017 , publisher=

    2017

  140. [148]

    Probability Theory and Related Fields , volume=

    Reconstruction and estimation in the planted partition model , author=. Probability Theory and Related Fields , volume=. 2015 , publisher=

    2015

  141. [149]

    Combinatorica , volume=

    A proof of the block model threshold conjecture , author=. Combinatorica , volume=. 2018 , publisher=

    2018

  142. [150]

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

    Community detection thresholds and the weak Ramanujan property , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

  143. [151]

    Physical Review E , volume=

    Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications , author=. Physical Review E , volume=. 2011 , publisher=

    2011

  144. [152]

    Journal of Computer and System Sciences , volume=

    Heuristics for semirandom graph problems , author=. Journal of Computer and System Sciences , volume=. 2001 , publisher=

    2001

  145. [153]

    Probability Theory and Related Fields , volume=

    Community detection in sparse networks via Grothendieck’s inequality , author=. Probability Theory and Related Fields , volume=. 2016 , publisher=

    2016

  146. [154]

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

    Semidefinite programs on sparse random graphs and their application to community detection , author=. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages=

  147. [155]

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

    How robust are reconstruction thresholds for community detection? , author=. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages=

  148. [156]

    Proceedings of the National Academy of Sciences , volume=

    Phase transitions in semidefinite relaxations , author=. Proceedings of the National Academy of Sciences , volume=. 2016 , publisher=

    2016

  149. [157]

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

    Local statistics, semidefinite programming, and community detection , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

    2021

  150. [158]

    Extremal cuts of sparse random graphs , author=

  151. [159]

    Journal of the ACM (JACM) , volume=

    Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , author=. Journal of the ACM (JACM) , volume=. 1995 , publisher=

    1995

  152. [160]

    arXiv preprint arXiv:1108.2464 , year=

    Grothendieck-type inequalities in combinatorial optimization , author=. arXiv preprint arXiv:1108.2464 , year=

    arXiv

  153. [161]

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

    Approximating the cut-norm via Grothendieck's inequality , author=. Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , pages=

  154. [162]

    2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=

    Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs , author=. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=. 2015 , organization=

    2015

  155. [163]

    Advances in Neural Information Processing Systems , volume=

    Achieving the KS threshold in the general stochastic block model with linearized acyclic belief propagation , author=. Advances in Neural Information Processing Systems , volume=

  156. [164]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Efficient bayesian estimation from few samples: community detection and related problems , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

    2017

  157. [165]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    The power of sum-of-squares for detecting hidden structures , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

    2017

  158. [166]

    Conference on Learning Theory , pages=

    Fast and robust tensor decomposition with applications to dictionary learning , author=. Conference on Learning Theory , pages=. 2017 , organization=

    2017

  159. [167]

    Conference on Learning Theory , pages=

    A robust spectral algorithm for overcomplete tensor decomposition , author=. Conference on Learning Theory , pages=. 2019 , organization=

    2019

  160. [168]

    Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018 , pages=

    High dimensional estimation via sum-of-squares proofs , author=. Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018 , pages=. 2018 , organization=

    2018

  161. [169]

    arXiv preprint arXiv:1609.02487 , year=

    Non-backtracking spectrum of degree-corrected stochastic block models , author=. arXiv preprint arXiv:1609.02487 , year=

    arXiv

  162. [170]

    Zeitschrift f

    Bounds on conditional probabilities with applications in multi-user communication , author=. Zeitschrift f

  163. [171]

    IEEE Transactions on Information Theory , volume=

    A simple proof of the blowing-up lemma (corresp.) , author=. IEEE Transactions on Information Theory , volume=. 1986 , publisher=

    1986

  164. [172]

    The Annals of Probability , volume=

    Bounding d-distance by informational divergence: a method to prove measure concentration , author=. The Annals of Probability , volume=. 1996 , publisher=

    1996

  165. [173]

    Foundations and Trends

    Concentration of measure inequalities in information theory, communications, and coding , author=. Foundations and Trends. 2013 , publisher=

    2013

  166. [174]

    2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Robust recovery for stochastic block models , author=. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2022 , organization=

    2021

  167. [175]

    2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Minimax rates for robust community detection , author=. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2022 , organization=

    2022

  168. [176]

    The Annals of Statistics , volume=

    Optimality and sub-optimality of PCA I: Spiked random matrix models , author=. The Annals of Statistics , volume=. 2018 , publisher=

    2018

  169. [177]

    Conference on Learning Theory , pages=

    Robustness of spectral methods for community detection , author=. Conference on Learning Theory , pages=. 2019 , organization=

    2019

  170. [178]

    SIAM Journal on Mathematics of Data Science , volume=

    Graph powering and spectral robustness , author=. SIAM Journal on Mathematics of Data Science , volume=. 2020 , publisher=

    2020

  171. [179]

    Random Structures & Algorithms , volume=

    Spectral techniques applied to sparse random graphs , author=. Random Structures & Algorithms , volume=. 2005 , publisher=

    2005

  172. [180]

    Conference on Learning Theory , pages=

    Belief propagation, robust reconstruction and optimal recovery of block models , author=. Conference on Learning Theory , pages=. 2014 , organization=

    2014

  173. [181]

    2008 IEEE international symposium on information theory , pages=

    High-dimensional analysis of semidefinite relaxations for sparse principal components , author=. 2008 IEEE international symposium on information theory , pages=. 2008 , organization=

    2008

  174. [182]

    arXiv preprint arXiv:1304.0828 , year=

    Computational lower bounds for sparse PCA , author=. arXiv preprint arXiv:1304.0828 , year=

    arXiv

  175. [183]

    The Annals of Statistics , volume=

    Optimal detection of sparse principal components in high dimension , author=. The Annals of Statistics , volume=

  176. [184]

    Annals of Probability , pages=

    Phase Transition of the Largest Eigenvalue for Nonnull Complex Sample Covariance Matrices , author=. Annals of Probability , pages=. 2005 , publisher=

    2005

  177. [185]

    Annals of Statistics , volume=

    Do semidefinite relaxations solve sparse PCA up to the information limit? , author=. Annals of Statistics , volume=. 2013 , publisher=

    2013

  178. [186]

    Journal of the American Statistical Association , volume=

    On consistency and sparsity for principal components analysis in high dimensions , author=. Journal of the American Statistical Association , volume=. 2009 , publisher=

    2009

  179. [187]

    Foundations of Computational Mathematics , pages=

    Subexponential-time algorithms for sparse PCA , author=. Foundations of Computational Mathematics , pages=. 2023 , publisher=

    2023

  180. [188]

    Advances in neural information processing systems , volume=

    A direct formulation for sparse PCA using semidefinite programming , author=. Advances in neural information processing systems , volume=

  181. [189]

    The Annals of Statistics , volume=

    Sparse PCA: Optimal Rates and Adaptive Estimation , author=. The Annals of Statistics , volume=

  182. [190]

    Advances in Neural Information Processing Systems , volume=

    Sum-of-squares lower bounds for sparse PCA , author=. Advances in Neural Information Processing Systems , volume=

  183. [191]

    Advances in Neural Information Processing Systems , volume=

    Sparse PCA via covariance thresholding , author=. Advances in Neural Information Processing Systems , volume=

  184. [192]

    International encyclopedia of statistical science , pages=

    Robust statistics , author=. International encyclopedia of statistical science , pages=. 2011 , publisher=

    2011

  185. [193]

    Statistical Methods and Applications , volume=

    A survey of robust statistics , author=. Statistical Methods and Applications , volume=. 2007 , publisher=

    2007

  186. [194]

    Advances in neural information processing systems , volume=

    Robustness of classifiers: from adversarial to random noise , author=. Advances in neural information processing systems , volume=

  187. [195]

    Conference on learning theory , pages=

    Learning communities in the presence of errors , author=. Conference on learning theory , pages=. 2016 , organization=

    2016

  188. [196]

    Physical review letters , volume=

    Solvable model of a spin-glass , author=. Physical review letters , volume=. 1975 , publisher=

    1975

  189. [197]

    SIAM Journal on Computing , number=

    Optimization of the Sherrington--Kirkpatrick Hamiltonian , author=. SIAM Journal on Computing , number=. 2021 , publisher=

    2021

  190. [198]

    11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , volume=

    Computational Hardness of Certifying Bounds on Constrained PCA Problems , author=. 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , volume=

    2020

  191. [199]

    SIAM Journal on Computing , volume=

    A nearly tight sum-of-squares lower bound for the planted clique problem , author=. SIAM Journal on Computing , volume=. 2019 , publisher=

    2019

  192. [200]

    Statistical Inference and the Sum of Squares Method , author=

  193. [201]

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

    Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors , author=. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages=

  194. [202]

    Advances in Neural Information Processing Systems , volume=

    Estimating rank-one spikes from heavy-tailed noise via self-avoiding walks , author=. Advances in Neural Information Processing Systems , volume=

  195. [203]

    Course notes: http://www

    Proofs, beliefs, and algorithms through the lens of sum-of-squares , author=. Course notes: http://www. sumofsquares. org/public/index. html , volume=

  196. [204]

    2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Polynomial-time tensor decompositions with sum-of-squares , author=. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2016 , organization=

    2016

  197. [205]

    Soviet Journal of Computer and Systems Sciences , volume=

    Quadratic optimization problems , author=. Soviet Journal of Computer and Systems Sciences , volume=

  198. [206]

    2000 , publisher=

    Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , author=. 2000 , publisher=

    2000

  199. [207]

    High performance optimization , pages=

    Squared functional systems and optimization problems , author=. High performance optimization , pages=. 2000 , publisher=

    2000

  200. [208]

    Advances in Convex Analysis and Global Optimization: Honoring the Memory of C

    New positive semidefinite relaxations for nonconvex quadratic programs , author=. Advances in Convex Analysis and Global Optimization: Honoring the Memory of C. Caratheodory (1873--1950) , pages=. 2001 , publisher=

    1950

  201. [209]

    Combinatorica , volume=

    The ellipsoid method and its consequences in combinatorial optimization , author=. Combinatorica , volume=. 1981 , publisher=

    1981

  202. [210]

    On the problem of the most efficient tests of statistical hypotheses , author=

    IX. On the problem of the most efficient tests of statistical hypotheses , author=. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character , volume=. 1933 , publisher=

    1933

  203. [211]

    Asymptotics in Statistics: Some Basic Concepts , pages=

    Locally asymptotically normal families , author=. Asymptotics in Statistics: Some Basic Concepts , pages=. 1990 , publisher=

    1990

  204. [212]

    Mathematical Methods for Physicists , pages=

    Chapter 15-legendre functions , author=. Mathematical Methods for Physicists , pages=. 2013 , publisher=

    2013

  205. [213]

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

    Rounding sum-of-squares relaxations , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

  206. [214]

    40th Annual Symposium on Foundations of Computer Science (Cat

    Learning mixtures of Gaussians , author=. 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039) , pages=. 1999 , organization=

    1999

  207. [215]

    SIAM Journal on Computing , volume=

    Robust estimators in high-dimensions without the computational intractability , author=. SIAM Journal on Computing , volume=. 2019 , publisher=

    2019

  208. [216]

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

    Mixture models, robustness, and sum of squares proofs , author=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  209. [217]

    Conference On Learning Theory , pages=

    Efficient algorithms for outlier-robust regression , author=. Conference On Learning Theory , pages=. 2018 , organization=

    2018

  210. [218]

    arXiv preprint arXiv:1711.07465 , year=

    Better agnostic clustering via relaxed tensor norms , author=. arXiv preprint arXiv:1711.07465 , year=

    arXiv

  211. [219]

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

    Robust moment estimation and improved clustering via sum of squares , author=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  212. [220]

    Annals of Statistics , pages=

    Adaptive estimation of a quadratic functional by model selection , author=. Annals of Statistics , pages=. 2000 , publisher=

    2000

  213. [221]

    2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages=

    Settling the polynomial learnability of mixtures of gaussians , author=. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages=. 2010 , organization=

    2010

  214. [222]

    Proceedings of the 23rd international conference on Machine learning , pages=

    Generalized spectral bounds for sparse LDA , author=. Proceedings of the 23rd international conference on Machine learning , pages=

  215. [223]

    SIAM journal on computing , volume=

    Sparse approximate solutions to linear systems , author=. SIAM journal on computing , volume=. 1995 , publisher=

    1995

  216. [224]

    Journal of Functional Analysis , volume=

    Random vectors in the isotropic position , author=. Journal of Functional Analysis , volume=. 1999 , publisher=

    1999

  217. [225]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    On learning mixtures of well-separated gaussians , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

    2017

  218. [226]

    2017 , publisher=

    The moment problem , author=. 2017 , publisher=

    2017

  219. [227]

    Foundations of computational mathematics , volume=

    User-friendly tail bounds for sums of random matrices , author=. Foundations of computational mathematics , volume=. 2012 , publisher=

    2012

  220. [228]

    The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002

    A spectral algorithm for learning mixtures of distributions , author=. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. , pages=. 2002 , organization=

    2002

  221. [229]

    2019 , publisher=

    High-dimensional statistics: A non-asymptotic viewpoint , author=. 2019 , publisher=

    2019

  222. [230]

    IEEE Transactions on Information Theory , volume=

    On estimating rank-one spiked tensors in the presence of heavy tailed errors , author=. IEEE Transactions on Information Theory , volume=. 2022 , publisher=

    2022

  223. [231]

    Conference on Learning Theory , pages=

    Optimal average-case reductions to sparse pca: From weak assumptions to strong hardness , author=. Conference on Learning Theory , pages=. 2019 , organization=

    2019

  224. [232]

    Conference On Learning Theory , pages=

    Reducibility and computational lower bounds for problems with planted sparse structure , author=. Conference On Learning Theory , pages=. 2018 , organization=

    2018

  225. [233]

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

    Robustly learning mixtures of k arbitrary gaussians , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  226. [234]

    Advances in Neural Information Processing Systems , volume=

    Consistent robust regression , author=. Advances in Neural Information Processing Systems , volume=

  227. [235]

    Conference on learning theory , pages=

    Complexity theoretic lower bounds for sparse principal component detection , author=. Conference on learning theory , pages=. 2013 , organization=

    2013

  228. [236]

    Conference on Learning Theory , pages=

    On the well-spread property and its relation to linear regression , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  229. [237]

    Advances in Neural Information Processing Systems , volume=

    The complexity of sparse tensor PCA , author=. Advances in Neural Information Processing Systems , volume=

  230. [238]

    Journal of the ACM (JACM) , volume=

    Robust principal component analysis? , author=. Journal of the ACM (JACM) , volume=. 2011 , publisher=

    2011

  231. [239]

    2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Sparse PCA: algorithms, adversarial perturbations and certificates , author=. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2020 , organization=

    2020

  232. [240]

    Advances in Neural Information Processing Systems , volume=

    Consistent estimation for PCA and sparse regression with oblivious outliers , author=. Advances in Neural Information Processing Systems , volume=

  233. [241]

    International Conference on Machine Learning , pages=

    Consistent regression when oblivious outliers overwhelm , author=. International Conference on Machine Learning , pages=. 2021 , organization=

    2021

  234. [242]

    Communications in mathematical physics , volume=

    The largest eigenvalue of rank one deformation of large Wigner matrices , author=. Communications in mathematical physics , volume=. 2007 , publisher=

    2007

  235. [243]

    The Annals of Statistics , pages=

    Sparse CCA: Adaptive Estimation and Computational Barriers , author=. The Annals of Statistics , pages=

  236. [244]

    Mean estimation with sub-Gaussian rates in polynomial time , author=

  237. [245]

    Conference on Learning Theory , pages=

    Tensor principal component analysis via sum-of-square proofs , author=. Conference on Learning Theory , pages=. 2015 , organization=

    2015

  238. [246]

    Mathematical Analysis, its Applications and Computation: ISAAC 2019, Aveiro, Portugal, July 29--August 2 , pages=

    Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio , author=. Mathematical Analysis, its Applications and Computation: ISAAC 2019, Aveiro, Portugal, July 29--August 2 , pages=. 2022 , publisher=

    2019

  239. [247]

    Emerging applications of algebraic geometry , pages=

    Sums of squares, moment matrices and optimization over polynomials , author=. Emerging applications of algebraic geometry , pages=. 2009 , publisher=

    2009

  240. [248]

    Conference on Learning Theory , pages=

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

    2020

  241. [249]

    Advances in neural information processing systems , volume=

    A statistical model for tensor PCA , author=. Advances in neural information processing systems , volume=

  242. [250]

    arXiv preprint arXiv:2011.05555 , year=

    The strongish planted clique hypothesis and its consequences , author=. arXiv preprint arXiv:2011.05555 , year=

    2011 arXiv

  243. [251]

    2010 IEEE international symposium on information theory , pages=

    Stable principal component pursuit , author=. 2010 IEEE international symposium on information theory , pages=. 2010 , organization=

    2010

  244. [252]

    Statistical and computational trade-offs in estimation of sparse principal components , author=

  245. [253]

    IEEE Signal Processing Letters , volume=

    Convergence of the huber regression m-estimate in the presence of dense outliers , author=. IEEE Signal Processing Letters , volume=. 2014 , publisher=

    2014

  246. [254]

    Journal of the American Statistical Association , volume=

    Adaptive huber regression , author=. Journal of the American Statistical Association , volume=. 2020 , publisher=

    2020

  247. [255]

    Conference on Learning Theory , pages=

    Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery , author=. Conference on Learning Theory , pages=. 2015 , organization=

    2015

  248. [256]

    Natural Computing , volume=

    A study of drift analysis for estimating computation time of evolutionary algorithms , author=. Natural Computing , volume=. 2004 , publisher=

    2004

  249. [257]

    Conference on Learning Theory , pages=

    Adaptive hard thresholding for near-optimal consistent robust regression , author=. Conference on Learning Theory , pages=. 2019 , organization=

    2019

  250. [258]

    International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=

    New tools for graph coloring , author=. International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=. 2011 , organization=

    2011

  251. [259]

    The Thirty Sixth Annual Conference on Learning Theory , pages=

    Fast, sample-efficient, affine-invariant private mean and covariance estimation for subgaussian distributions , author=. The Thirty Sixth Annual Conference on Learning Theory , pages=. 2023 , organization=

    2023

  252. [260]

    Statistical limits of spiked tensor models , author=

  253. [261]

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

    Learning quantum Hamiltonians at any temperature in polynomial time , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

  254. [262]

    2023 , school=

    Information-computation gaps in robust statistics , author=. 2023 , school=

    2023

  255. [263]

    arXiv preprint arXiv:2009.12976 , year=

    Robust regression with covariate filtering: Heavy tails and adversarial contamination , author=. arXiv preprint arXiv:2009.12976 , year=

    2009 arXiv

  256. [264]

    Electron

    Boaz Barak and David Steurer , title =. Electron. Colloquium Comput. Complex. , volume =. 2014 , url =. TR14-059 , timestamp =

    2014

  257. [265]

    Personal communication , year=

    , author=. Personal communication , year=

  258. [266]

    Advances in Neural Information Processing Systems , volume=

    Graph zeta function in the Bethe free energy and loopy belief propagation , author=. Advances in Neural Information Processing Systems , volume=

  259. [267]

    arXiv preprint arXiv:1507.04391 , year=

    Sub-exponential approximation schemes for csps: From dense to almost sparse , author=. arXiv preprint arXiv:1507.04391 , year=

    arXiv

  260. [268]

    Journal of the ACM (JACM) , volume=

    Two-query PCP with subconstant error , author=. Journal of the ACM (JACM) , volume=. 2008 , publisher=

    2008

  261. [269]

    Journal of the ACM (JACM) , volume=

    Approximation resistance from pairwise-independent subgroups , author=. Journal of the ACM (JACM) , volume=. 2016 , publisher=

    2016

  262. [270]

    48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) , pages=

    Refuting smoothed 3CNF formulas , author=. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) , pages=. 2007 , organization=

    2007

  263. [271]

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

    Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  264. [272]

    2011 ieee 52nd annual symposium on foundations of computer science , pages=

    Rounding semidefinite programming hierarchies via global correlation , author=. 2011 ieee 52nd annual symposium on foundations of computer science , pages=. 2011 , organization=

    2011

  265. [273]

    2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Approximating constraint satisfaction problems on high-dimensional expanders , author=. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2019 , organization=

    2019

  266. [274]

    Lecture notes , year =

    Tselil Schramm , title =. Lecture notes , year =

  267. [275]

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

    Hypercontractivity, sum-of-squares proofs, and their applications , author=. Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages=

  268. [276]

    2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    The Kikuchi hierarchy and tensor PCA , author=. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2019 , organization=

    2019

  269. [277]

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

    Strongly refuting random csps below the spectral threshold , author=. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  270. [278]

    SIAM Journal on Computing , volume=

    Recognizing more unsatisfiable random k-SAT instances efficiently , author=. SIAM Journal on Computing , volume=. 2005 , publisher=

    2005

  271. [279]

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

    How well do local algorithms solve semidefinite programs? , author=. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  272. [280]

    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=

  273. [281]

    2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=

    How to refute a random CSP , author=. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=. 2015 , organization=

    2015

  274. [282]

    International Journal of Mathematics , volume=

    The Ihara-Selberg zeta function of a tree lattice , author=. International Journal of Mathematics , volume=. 1992 , publisher=

    1992

  275. [283]

    Contemporary Mathematics , volume=

    What are zeta functions of graphs and what are they good for? , author=. Contemporary Mathematics , volume=. 2006 , publisher=

    2006

  276. [284]

    Google Europe Blog, November , volume=

    Tackling urban mobility with technology , author=. Google Europe Blog, November , volume=

  277. [285]

    2017 , note =

    Learning with Privacy at Scale , howpublished =. 2017 , note =

    2017

  278. [286]

    Disclosure Avoidance for the 2020 Census: An Introduction , howpublished =

    2020

  279. [287]

    IEEE Transactions on information theory , volume=

    Exact recovery in the stochastic block model , author=. IEEE Transactions on information theory , volume=. 2015 , publisher=

    2015

  280. [288]

    Conference on Learning Theory , pages=

    Private and polynomial time algorithms for learning gaussians and beyond , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  281. [289]

    2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Outlier-robust clustering of gaussians and other non-spherical mixtures , author=. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2020 , organization=

    2020

  282. [290]

    The Annals of Statistics , volume=

    Minimax rates of community detection in stochastic block models , author=. The Annals of Statistics , volume=. 2016 , publisher=

    2016

  283. [291]

    Advances in Neural Information Processing Systems , volume=

    Differentially private empirical risk minimization revisited: Faster and more general , author=. Advances in Neural Information Processing Systems , volume=

  284. [292]

    International Conference on Machine Learning , pages=

    Friendlycore: Practical differentially private aggregation , author=. International Conference on Machine Learning , pages=. 2022 , organization=

    2022

  285. [293]

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

    SoS degree reduction with applications to clustering and robust moment estimation , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

    2021

  286. [294]

    2013 IEEE global conference on signal and information processing , pages=

    Stochastic gradient descent with differentially private updates , author=. 2013 IEEE global conference on signal and information processing , pages=. 2013 , organization=

    2013

  287. [295]

    International Conference on Machine Learning , pages=

    Differentially private community detection for stochastic block models , author=. International Conference on Machine Learning , pages=. 2022 , organization=

    2022

  288. [296]

    Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages=

    Smooth sensitivity and sampling in private data analysis , author=. Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages=

  289. [297]

    International Conference on Artificial Intelligence and Statistics , pages=

    Private optimization without constraint violations , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2021 , organization=

    2021

  290. [298]

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

    Consistency thresholds for the planted bisection model , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=

  291. [299]

    48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) , pages=

    Mechanism design via differential privacy , author=. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) , pages=. 2007 , organization=

    2007

  292. [300]

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

    Clustering mixtures with almost optimal separation in polynomial time , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.