Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Statistical inference of a ranked community in a directed graph

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper maps exactly when a hidden ranked community in a directed graph can be detected and recovered, statistically and in polynomial time.

desk verdict A solid first paper on a new planted model; the statistical thresholds are rigorous, the computational ones are honest about relying on the low-degree conjecture. read the letter →

arxiv 2411.19885 v1 pith:4FU7G2BP submitted 2024-11-18 math.ST cs.CCcs.DSmath.COmath.PRstat.TH

Dmitriy Kunisky , Daniel A. Spielman , Alexander S. Wein , Xifan Yu This is my paper · ORCID
classification math.STcs.CCcs.DSmath.COmath.PRstat.TH
keywords plantedrankedsubgraphdetection-recoverygapstatistical-computationallow-degreepolynomialmethoddirectedgraphcommunitydetectionnoisyrankingrandomtournamentsorderedclique
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

The paper studies a directed analogue of the planted dense subgraph problem: a hidden subset of $k$ vertices carries a latent ranking, and edges between those vertices favor the higher-ranked endpoint with probability $1/2 + q$, while all other pairwise directions are unbiased coin flips. Because the underlying undirected edge set is just a random graph with independent edges, the planted structure is visible only in the consistency of directions, not in edge density. In the log-density scaling $q = n^{-\alpha}$, $k = n^{\beta}$, $p = n^{-\gamma}$, the paper claims exact exponent thresholds for statistical and computational detection and recovery, yielding a three-parameter phase diagram with both statistical-computational gaps and detection-recovery gaps. A sympathetic reader would take the central contribution to be a clean new model where the boundary between feasible and infeasible inference is known precisely, up to an explicit unproved conjecture about computational hardness.

What carries the argument

Three mechanisms carry the argument. First, the degree-$2$ polynomial $f(Y) = \sum_{i}\sum_{j<k} Y_{ij}Y_{ik}$, essentially the sample variance of win counts, separates the planted from the null distribution when $k^3 p^2 q^2$ dominates the noise scale; thresholding it gives the computational detection upper bound. Second, the Hermitian matrix $iY$ has expectation whose top eigenvector encodes the planted set and ranking through a matrix $A_{\ell}$ with eigenvalues $1/\tan((2i-1)\pi/(2\ell))$, and a Davis-Kahan perturbation bound converts closeness of eigenvectors into approximate recovery of both the subset and the permutation. Third, the low-degree method computes the low-degree advantage and low-degree correlation as sums over edge subsets, bounded by counting even graphs, yielding the computational lower bounds that the paper labels as conditional on the low-degree conjecture. For tournaments, Ranking By Wins combined with read-$k$ tail bounds and Berry-Esseen estimates gives recovery and alignment guarantees.

What would settle it

A concrete falsifier would be any polynomial-time algorithm that achieves weak detection or weak recovery for some exponents with $\beta < \frac{2}{3}\alpha + \frac{1}{3}\gamma + \frac{1}{2}$; alternatively, one could numerically compute the low-degree advantage at degree $D = (\log n)^{1+\varepsilon}$ inside the claimed hard region and find it diverging, which would break the low-degree lower bound itself.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the planted ranked subgraph model has explicit, exact thresholds in the log-density regime. Strong detection is statistically possible if and only if $\beta > \min\{2\alpha + \gamma,\ \frac{2}{3}\alpha + \frac{1}{3}\gamma + \frac{1}{2}\}$, while strong detection by polynomial-time algorithms is possible if and only if $\beta > \frac{2}{3}\alpha + \frac{1}{3}\gamma + \frac{1}{2}$, with the lower bound informal and conditional on the low-degree conjecture. Strong recovery is statistically possible if and only if $\beta > 2\alpha + \gamma$, and computationally possible if and only if $\beta > \alpha + \frac{1}{2}\gamma + \frac{1}{2}$, again with the hardness part resting on the same conjecture. At the two extreme scalings the picture sharpens: a full tournament weakly correlated with a global ranking is strongly detectable when $q = \omega(n^{-3/4})$ and weakly recoverable when $q = \omega(n^{-1/2})$, and a planted ordered clique of size $k = \Omega(\sqrt{n})$ is exactly recoverable in polynomial time, with the constant in front of $\sqrt{n}$ reducible to any positive constant.

Load-bearing premise

The computational impossibility thresholds rest on the low-degree conjecture, an unproved claim that if low-degree polynomials cannot separate the two distributions, then no polynomial-time algorithm can. If that conjecture fails for this model, the claimed computationally hard regions could actually be easy, while the statistical thresholds would still stand.

Editorial extensions

If this is right

  • When $\beta > \frac{2}{3}\alpha + \frac{1}{3}\gamma + \frac{1}{2}$, a simple quadratic polynomial in the directed adjacency matrix detects the ranked community in polynomial time.
  • When $\beta$ lies between $\min\{2\alpha+\gamma,\ \frac{2}{3}\alpha+\frac{1}{3}\gamma+\frac{1}{2}\}$ and the computational threshold, detection is statistically possible but apparently computationally hard, exhibiting a statistical-computational gap.
  • Spectral recovery through the Hermitian matrix $iY$ succeeds down to $\beta > \alpha + \frac{1}{2}\gamma + \frac{1}{2}$, matching the low-degree lower bound under the conjecture.
  • In a full tournament, Ranking By Wins is optimal up to constants: it strongly recovers the hidden ranking when $q = \omega(n^{-1/2})$, weakly recovers when $q = \Theta(n^{-1/2})$, and no estimator succeeds when $q = o(n^{-1/2})$.
  • A planted ordered clique of size $c\sqrt{n}$ is exactly recoverable in polynomial time for every constant $c > 0$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the same proof template of bounding low-degree advantage by counting even edge subsets should transfer to bipartite or multilayer versions of the model, with the exponent formulas changing according to the dimension of the planted structure.
  • Editorial extension: the spectral detection result suggests that in sparse directed models, eigenvalue-based statistics can be polynomially weaker than quadratic combinatorial statistics, a phenomenon that could be tested in other planted ranking and planted structure settings.
  • Editorial extension: the exponent predictions are directly testable at finite $n$ by Monte Carlo estimation of the low-degree advantage and comparison with the claimed threshold curves, independently of whether the low-degree conjecture is eventually resolved.
  • Editorial extension: the model provides a minimal setting where the detection-recovery gap and the statistical-computational gap coexist, so it could serve as a benchmark for transfer principles that predict computational hardness from low-degree calculations.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper introduces the planted ranked subgraph (PRS) model for directed graphs, in which a hidden subset S of k vertices carries a latent permutation π and the observed directed edges within S are biased toward agreement with π, while all edge directions outside S are fair. The authors study both detection (testing the planted distribution against the null) and recovery (estimating S and π), in each case separating statistical from computational feasibility. In the log-density setting q=n^{-α}, k=n^β, p=n^{-γ}, they derive exact exponent thresholds: statistical detection is possible iff β>min{2α+γ, 2/3α+1/3γ+1/2}; statistical recovery iff β>2α+γ; computational detection iff β>2/3α+1/3γ+1/2; and computational recovery iff β>α+γ/2+1/2, with the computational lower bounds explicitly informal and resting on the low-degree conjecture. The paper also gives sharp results for two extreme cases: a full tournament weakly correlated with a global ranking (detection threshold q∼n^{-3/4}, recovery threshold q∼n^{-1/2}, with a spectral detection algorithm provably suboptimal), and a small planted ordered clique in a tournament (exact recovery for k≥c√n for any constant c).

Significance. If the phase diagram is correct, this is a substantial contribution to the theory of planted inference in directed graphs. The model is a natural directed analogue of planted dense subgraph, and the paper provides the first exact exponent-level characterization of statistical and computational thresholds for it, including explicit detection-recovery and statistical-computational gaps. The statistical upper and lower bounds are supported by matching χ²/KL and union-bound calculations, and the computational upper bounds are constructive polynomial-time algorithms (degree-2 polynomial, spectral method, ranking-by-wins). The computational lower bounds are conditional on the low-degree conjecture, but they are carefully and honestly labeled as informal, and the low-degree calculations themselves are internally consistent. The extreme-case results, particularly the spectral-vs-combinatorial gap for detection in tournaments, are interesting in their own right.

major comments (2)
  1. [Section 4.3.2, Proposition 4.13 and following inequality] The proposition as stated is false and does not match its use. It claims the number of connected A⊆[n] choose 2 with 1∈V(A), |A|=d, and |V(A)|=d+1−h is at most (dn)^d(d/n)^d. But the proof immediately uses the bound (dn)^d(d/n)^h; for d=1 and h=0, the stated bound gives 1 while the actual number of such edge sets is n−1. Since this counting bound is a load-bearing step in the derivation of Corr≤D(P)²≤k²/n²·(...) that establishes Theorem 1.7's lower bound, the proof as written is not valid. Please correct the proposition statement (the intended bound appears to be (dn)^d(d/n)^h, as used) or revise the application accordingly, and make the dependence on the cited [SW22, Lemma 3.5] explicit.
  2. [Section 5.1.4, Proposition 5.1 proof] The proof of the upper bound on OPT contains an incorrect stochastic domination statement. It says that for each fixed Bℓ, the distribution of Σ_{(x,y)∈Bℓ} Y_{x,y} is stochastically dominated by a sum of n/2^ℓ independent Rademacher variables. However |Bℓ| = n²/2^{ℓ+1}, so the number of summands is off by a factor of order n, which changes the tail scale and the resulting O(n^{3/2}) claim. This proof supports the upper bound in Proposition 5.1, which is used in Theorem 1.16. Please correct the number of summands (presumably |Bℓ| or an equivalent bound) and supply the omitted union-bound calculation, or state a precise adaptation of [dlV83].
minor comments (5)
  1. [Section 5.1.1] There is a duplicated phrase: 'See, e.g., See, e.g., [KWB19, Lemma 1.13]'. Please fix.
  2. [Remark 1.17] The remark says 'In the case of γ ≥ 1/4'; this should be 'q ≥ 1/4', since the surrounding discussion is about the tournament setting with the signal strength q, not the log-density exponent γ.
  3. [General notation] The tilde-o notation eO, eΘ, eΩ is used in Section 4.4.1 and elsewhere without being formally defined. Please add a sentence defining these as hiding poly-logarithmic factors.
  4. [Theorem 1.7] The phrase 'under the less stringent assumptions that q=ω(√n/(k√p)), p=Ω(log n/n), and k=ω(1)' is misleading: in the log-density setting these assumptions are equivalent to β>α+γ/2+1/2, not weaker. The intended meaning is that the statement is more general because p, k, q need not be exact powers of n. Please rephrase.
  5. [Abstract and Section 1.2] The abstract states that the paper establishes 'exact thresholds' for computational feasibility, but the computational lower bounds are conditional on the low-degree conjecture. Section 1.2 does qualify this, so please add a similar qualifier in the abstract to avoid overstating the status of the computational thresholds.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the phase thresholds follow from explicit moment, chi-square, KL, spectral, and low-degree computations, with only the honestly labeled low-degree conjecture as a conditional external input.

full rationale

The paper's central thresholds are derived by direct calculation rather than by assuming the target result. The statistical detection bound (Theorem 1.6) comes from a chi-square expansion that reduces to expectation over the overlap of two random planted sets and is bounded via Propositions 4.2 and 4.3; the condition beta < min{2alpha+gamma, (2/3)alpha+(1/3)gamma+1/2} emerges from p^2 q^4 max{k'^2/n, k'^6/n^3} = o(1), and it exactly matches the union-of-algorithms upper bound. The statistical recovery bound (Theorem 1.8) uses a Neyman-Pearson reduction between two planted hypotheses and tensorization of KL divergence, giving an Omega(k) Hamming lower bound when q << 1/sqrt(kp), again with no fitted parameter renamed as a prediction. The computational detection lower bound (Theorem 1.5) computes the low-degree advantage Adv_{<=D}(Q,P)^2 directly from the orthonormal basis h_{A,B}, summing over even graphs A; the exponent condition arises from the algebra of (k/n)^{|V(A)|}(2q sqrt(p))^{|A|}, not from the conclusion. The computational recovery lower bound (Theorem 1.7) follows the Schramm-Wein low-degree MMSE framework but performs the model-specific recursion and graph-counting estimates in Propositions 4.9-4.13. The only conditional step is the low-degree conjecture (Conjecture 3.8), which the paper explicitly labels informal and attributes to [Hop18]; the jump from 'no low-degree polynomial separates' to 'no polynomial-time algorithm' is an external unproved conjecture, honestly flagged, not a self-citation chain and not a construction that encodes the answer. Self-citations such as [SW22] and [KWB19] supply standard machinery (low-degree correlation formula, orthogonal polynomial expansion) but not the model-specific thresholds, which are computed in this paper. Upper bounds are explicit algorithms: a degree-2 polynomial, a spectral method, ranking-by-wins, and an MLE-type search, all analyzed with standard concentration and perturbation tools. No fitted input is called a prediction, no known result is merely renamed, and no uniqueness theorem is imported from the authors' prior work to force a choice. The informal labels on the computational lower bounds are a limitation of the hardness framework, not circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters were fitted to data; n, k, p, q are problem inputs and the thresholds are exact functions of the log-density exponents. The planted ranked subgraph is a statistical model rather than an invented physical entity. The only load-bearing assumption beyond standard mathematics is the low-degree conjecture, which is explicitly stated and used for computational hardness.

assumptions (3)
  • domain assumption Low-degree conjecture: for sufficiently nice Q and P, if Adv<=D(Q,P) remains bounded for D >= (log n)^{1+epsilon}, then no polynomial-time algorithm achieves strong detection (Conjecture 3.8).
    The computational lower bounds in Theorems 1.5 and 1.7 are conditional on this conjecture; the paper states it explicitly in Section 3.2 and marks the theorem parts as informal.
  • standard math Standard concentration and random matrix results: Davis-Kahan eigenvector perturbation, Berry-Esseen theorem, read-k tail bounds, spectral norm of sparse random matrices [BGBK20], Wigner semicircle law, finite-rank perturbation theorem [CDMF09].
    These are cited and used without proof in Sections 3.4, 4.3, and 5.1; they are established results, not specific to this paper.
  • standard math Information-theoretic inequalities: Neyman-Pearson lemma, Pinsker's and Bretagnolle-Huber inequalities, tensorization of KL divergence.
    Used in lower bound proofs for statistical detection and recovery in Sections 4.2.2, 4.4.2, and 5.1.3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Statistical inference of a ranked community in a directed graph." pith.science (2026). https://pith.science/paper/4FU7G2BP

@misc{pith2026241119885,
  author       = {Pith},
  title        = {Pith review of: Statistical inference of a ranked community in a directed graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4FU7G2BP}},
  note         = {Machine review of arXiv:2411.19885}
}
abstract

We study the problem of detecting or recovering a planted ranked subgraph from a directed graph, an analog for directed graphs of the well-studied planted dense subgraph model. We suppose that, among a set of $n$ items, there is a subset $S$ of $k$ items having a latent ranking in the form of a permutation $\pi$ of $S$, and that we observe a fraction $p$ of pairwise orderings between elements of $\{1, \dots, n\}$ which agree with $\pi$ with probability $\frac{1}{2} + q$ between elements of $S$ and otherwise are uniformly random. Unlike in the planted dense subgraph and planted clique problems where the community $S$ is distinguished by its unusual density of edges, here the community is only distinguished by the unusual consistency of its pairwise orderings. We establish computational and statistical thresholds for both detecting and recovering such a ranked community. In the log-density setting where $k$, $p$, and $q$ all scale as powers of $n$, we establish the exact thresholds in the associated exponents at which detection and recovery become statistically and computationally feasible. These regimes include a rich variety of behaviors, exhibiting both statistical-computational and detection-recovery gaps. We also give finer-grained results for two extreme cases: (1) $p = 1$, $k = n$, and $q$ small, where a full tournament is observed that is weakly correlated with a global ranking, and (2) $p = 1$, $q = \frac{1}{2}$, and $k$ small, where a small "ordered clique" (totally ordered directed subgraph) is planted in a random tournament.

Figures

Figures reproduced from arXiv: 2411.19885 by the authors.

Figure 1
Figure 1. Computational and statistical thresholds for detection and recovery in the planted ranked [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. All possible patterns in which two paths of length 2 can intersect non-trivially. [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
Figure 3
Figure 3. A description of the spectral algorithm analyzed in Theorem 1.7. [PITH_FULL_IMAGE:figures/full_fig_p034_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: A description of the spectral algorithm analyzed in Theorem 1.18. [PITH_FULL_IMAGE:figures/full_fig_p062_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

    math.ST 2025-06 accept novelty 2.0 of 10

    A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.

Reference graph

Works this paper leans on

62 extracted references · 54 canonical work pages · cited by 1 Pith paper

  1. [1]

    Community detection and stochastic block models: recent developments

    Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research , 18(1):6446--6531, 2017

    work page 2017

  2. [2]

    An introduction to random matrices

    Greg W Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction to random matrices . Cambridge University Press, 2010

    work page 2010

  3. [3]

    Finding a large hidden clique in a random graph

    Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. Random Structures & Algorithms , 13(3-4):457--466, 1998

    1998

  4. [4]

    Ranking tournaments

    Noga Alon. Ranking tournaments. SIAM Journal on Discrete Mathematics , 20(1):137--142, 2006

    work page 2006

  5. [5]

    Reducibility and statistical-computational gaps from secret leakage

    Matthew Brennan and Guy Bresler. Reducibility and statistical-computational gaps from secret leakage. In 33rd Annual Conference on Learning Theory (COLT 2020) , pages 648--847. PMLR, 2020

    work page 2020

  6. [6]

    Detecting high log-densities: an o (n 1/4 ) approximation for densest k-subgraph

    Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. Detecting high log-densities: an o (n 1/4 ) approximation for densest k-subgraph. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 201--210, 2010

    work page 2010

  7. [7]

    The Franz-Parisi criterion and computational trade-offs in high dimensional statistics

    Afonso S Bandeira, Ahmed El Alaoui, Samuel Hopkins, Tselil Schramm, Alexander S Wein, and Ilias Zadik. The Franz-Parisi criterion and computational trade-offs in high dimensional statistics. Advances in Neural Information Processing Systems , 35:33831--33844, 2022

    work page 2022

  8. [8]

    The accuracy of the Gaussian approximation to the sum of independent variates

    Andrew C Berry. The accuracy of the Gaussian approximation to the sum of independent variates. Transactions of the american mathematical society , 49(1):122--136, 1941

    work page 1941

Show all 62 references
  1. [9]

    Spectral radii of sparse random matrices

    Florent Benaych-Georges, Charles Bordenave, and Antti Knowles. Spectral radii of sparse random matrices . Annales de l'Institut Henri Poincaré, Probabilités et Statistiques , 56(3):2141 -- 2161, 2020

    2020

  2. [10]

    A nearly tight sum-of-squares lower bound for the planted clique problem

    Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing , 48(2):687--735, 2019

    2019

  3. [11]

    Detection-recovery and detection-refutation gaps via reductions from planted clique

    Guy Bresler and Tianze Jiang. Detection-recovery and detection-refutation gaps via reductions from planted clique. In The Thirty Sixth Annual Conference on Learning Theory , pages 5850--5889. PMLR, 2023

    2023

  4. [12]

    Noisy sorting without resampling

    Mark Braverman and Elchanan Mossel. Noisy sorting without resampling. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008) , page 268–276, USA, 2008. Society for Industrial and Applied Mathematics

    2008

  5. [13]

    Notes on computational-to-statistical gaps: predictions using statistical physics

    Afonso S Bandeira, Amelia Perry, and Alexander S Wein. Notes on computational-to-statistical gaps: predictions using statistical physics. Portugaliae Mathematica , 75(2):159--186, 2018

    2018

  6. [14]

    Rank analysis of incomplete block designs: I

    Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika , 39(3/4):324--345, 1952

    1952

  7. [15]

    A short note on an inequality between KL and TV

    Cl \'e ment L Canonne. A short note on an inequality between KL and TV . arXiv preprint arXiv:2202.07198 , 2022

    2022 arXiv

  8. [16]

    The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations

    Mireille Capitaine, Catherine Donati-Martin, and Delphine F \'e ral. The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations. The Annals of Probability , 37(1):1--47, 2009

    2009

  9. [17]

    Matrix estimation by universal singular value thresholding

    Sourav Chatterjee. Matrix estimation by universal singular value thresholding. 2015

    2015

  10. [18]

    Estimation in tournaments and graphs under monotonicity constraints

    Sabyasachi Chatterjee and Sumit Mukherjee. Estimation in tournaments and graphs under monotonicity constraints. IEEE Transactions on Information Theory , 65(6):3525--3539, 2019

    2019

  11. [19]

    Statistical and computational phase transitions in group testing

    Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S Wein, and Ilias Zadik. Statistical and computational phase transitions in group testing. In Conference on Learning Theory , pages 4764--4781. PMLR, 2022

    2022

  12. [20]

    Spectral MLE : Top- k rank aggregation from pairwise comparisons

    Yuxin Chen and Changho Suh. Spectral MLE : Top- k rank aggregation from pairwise comparisons. In International Conference on Machine Learning , pages 371--380. PMLR, 2015

    2015

  13. [21]

    Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices

    Yudong Chen and Jiaming Xu. Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. The Journal of Machine Learning Research , 17(1):882--938, 2016

    2016

  14. [22]

    A physical model for efficient ranking in networks

    Caterina De Bacco, Daniel B Larremore, and Cristopher Moore. A physical model for efficient ranking in networks. Science advances , 4(7):eaar8260, 2018

    2018

  15. [23]

    Low-degree hardness of detection for correlated Erd o s-R\' e nyi graphs

    Jian Ding, Hang Du, and Zhangsong Li. Low-degree hardness of detection for correlated Erd o s-R\' e nyi graphs. arXiv preprint arXiv:2311.15931 , 2023

    2023

  16. [24]

    The rotation of eigenvectors by a perturbation

    Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. iii. SIAM Journal on Numerical Analysis , 7(1):1--46, 1970

    1970

  17. [25]

    On the maximum cardinality of a consistent set of arcs in a random tournament

    W Fernandez de la Vega. On the maximum cardinality of a consistent set of arcs in a random tournament. Journal of Combinatorial Theory, Series B , 35(3):328--332, 1983

    1983

  18. [26]

    Detection of dense subhypergraphs by low-degree polynomials

    Abhishek Dhawan, Cheng Mao, and Alexander S Wein. Detection of dense subhypergraphs by low-degree polynomials. arXiv preprint arXiv:2304.08135 , 2023

    2023 arXiv

  19. [27]

    Condorcet social choice functions

    Peter C Fishburn. Condorcet social choice functions. SIAM Journal on applied Mathematics , 33(3):469--489, 1977

    1977

  20. [28]

    Finding and certifying a large hidden clique in a semirandom graph

    Uriel Feige and Robert Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph. Random Structures & Algorithms , 16(2):195--208, 2000

    2000

  21. [29]

    Sorting with recurrent comparison errors

    Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Sorting with recurrent comparison errors. arXiv preprint arXiv:1709.07249 , 2017

    2017 arXiv

  22. [30]

    Optimal sorting with persistent comparison errors

    Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal sorting with persistent comparison errors. arXiv preprint arXiv:1804.07575 , 2018

    2018 arXiv

  23. [31]

    A tail bound for read- k families of functions

    Dmitry Gavinsky, Shachar Lovett, Michael Saks, and Srikanth Srinivasan. A tail bound for read- k families of functions. Random Structures & Algorithms , 47(1):99--108, 2015

    2015

  24. [32]

    Values of Mills' ratio of area to bounding ordinate and of the normal probability integral for large values of the argument

    Robert D Gordon. Values of Mills' ratio of area to bounding ordinate and of the normal probability integral for large values of the argument. The Annals of Mathematical Statistics , 12(3):364--366, 1941

    1941

  25. [33]

    Finding hierarchy in directed online social networks

    Mangesh Gupte, Pravin Shankar, Jing Li, Shanmugauelayut Muthukrishnan, and Liviu Iftode. Finding hierarchy in directed online social networks. In Proceedings of the 20th international conference on World wide web , pages 557--566, 2011

    2011

  26. [34]

    Optimal bounds for noisy sorting

    Yuzhou Gu and Yinzhan Xu. Optimal bounds for noisy sorting. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1502--1515, 2023

    2023

  27. [35]

    The power of sum-of-squares for detecting hidden structures

    Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures. In 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 720--731. IEEE, 2017

    2017

  28. [36]

    Statistical inference and the sum of squares method

    Samuel Hopkins. Statistical inference and the sum of squares method . PhD thesis, Cornell University, 2018

    2018

  29. [37]

    Efficient Bayesian estimation from few samples: community detection and related problems

    Samuel B Hopkins and David Steurer. Efficient Bayesian estimation from few samples: community detection and related problems. In 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 379--390. IEEE, 2017

    2017

  30. [38]

    Computational lower bounds for community detection on random graphs

    Bruce Hajek, Yihong Wu, and Jiaming Xu. Computational lower bounds for community detection on random graphs. In Conference on Learning Theory , pages 899--928. PMLR, 2015

    2015

  31. [39]

    Large cliques elude the Metropolis process

    Mark Jerrum. Large cliques elude the Metropolis process. Random Structures & Algorithms , 3(4):347--359, 1992

    1992

  32. [40]

    Top- k ranking from pairwise comparisons: When spectral ranking is optimal

    Minje Jang, Sunghyun Kim, Changho Suh, and Sewoong Oh. Top- k ranking from pairwise comparisons: When spectral ranking is optimal. arXiv preprint arXiv:1603.04153 , 2016

    2016 arXiv

  33. [41]

    Tolerant algorithms

    Rolf Klein, Rainer Penninger, Christian Sohler, and David P Woodruff. Tolerant algorithms. In Algorithms--ESA 2011: 19th Annual European Symposium, Saarbr \"u cken, Germany, September 5-9, 2011. Proceedings 19 , pages 736--747. Springer, 2011

    2011

  34. [42]

    Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio

    Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation) , pages 1--50. Springer, 2019

    2019

  35. [43]

    Individual choice behavior , volume 4

    R Duncan Luce. Individual choice behavior , volume 4. Wiley New York, 1959

    1959

  36. [44]

    Spectral partitioning of random graphs

    Frank McSherry. Spectral partitioning of random graphs. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science , pages 529--537. IEEE, 2001

    2001

  37. [45]

    Active learning for top- k rank aggregation from noisy comparisons

    Soheil Mohajer, Changho Suh, and Adel Elmahdy. Active learning for top- k rank aggregation from noisy comparisons. In International Conference on Machine Learning , pages 2488--2497. PMLR, 2017

    2017

  38. [46]

    Minimax rates and efficient algorithms for noisy sorting

    Cheng Mao, Jonathan Weed, and Philippe Rigollet. Minimax rates and efficient algorithms for noisy sorting. In Algorithmic Learning Theory , pages 821--847. PMLR, 2018

    2018

  39. [47]

    Detection-recovery gap for planted dense cycles

    Cheng Mao, Alexander S Wein, and Shenduo Zhang. Detection-recovery gap for planted dense cycles. In 36th Annual Conference on Learning Theory (COLT 2023) . PMLR, 2023

    2023

  40. [48]

    Iterative ranking from pair-wise comparisons

    Sahand Negahban, Sewoong Oh, and Devavrat Shah. Iterative ranking from pair-wise comparisons. Advances in neural information processing systems , 25, 2012

    2012

  41. [49]

    Tournament ranking with expected profit in polynomial time

    Svatopluk Poljak, Vojt e˘ ch R \"o dl, and Joel Spencer. Tournament ranking with expected profit in polynomial time. SIAM journal on discrete mathematics , 1(3):372--376, 1988

    1988

  42. [50]

    A statistical convergence perspective of algorithms for rank aggregation from pairwise data

    Arun Rajkumar and Shivani Agarwal. A statistical convergence perspective of algorithms for rank aggregation from pairwise data. In International conference on machine learning , pages 118--126. PMLR, 2014

    2014

  43. [51]

    Social hierarchies and social networks in humans

    Daniel Redhead and Eleanor A Power. Social hierarchies and social networks in humans. Philosophical Transactions of the Royal Society B , 377(1845), 2022

    2022

  44. [52]

    Sorting from noisier samples

    Aviad Rubinstein and Shai Vardi. Sorting from noisier samples. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 960--972. SIAM, 2017

    2017

  45. [53]

    Stochastically transitive models for pairwise comparisons: Statistical and computational issues

    Nihar Shah, Sivaraman Balakrishnan, Aditya Guntuboyina, and Martin Wainwright. Stochastically transitive models for pairwise comparisons: Statistical and computational issues. In International Conference on Machine Learning , pages 11--20. PMLR, 2016

    2016

  46. [54]

    Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons

    Nihar B Shah, Sivaraman Balakrishnan, and Martin J Wainwright. Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons. IEEE Transactions on Information Theory , 65(8):4854--4874, 2019

    2019

  47. [55]

    Optimal ranking of tournaments

    Joel Spencer. Optimal ranking of tournaments. Networks , 1(2):135--138, 1971

    1971

  48. [56]

    On the size of induced acyclic subgraphs in random digraphs

    Joel Spencer and CR Subramanian. On the size of induced acyclic subgraphs in random digraphs. Discrete Mathematics & Theoretical Computer Science , 10(Graph and Algorithms), 2008

    2008

  49. [57]

    Simple, robust and optimal ranking from pairwise comparisons

    Nihar B Shah and Martin J Wainwright. Simple, robust and optimal ranking from pairwise comparisons. Journal of machine learning research , 18(199):1--38, 2018

    2018

  50. [58]

    Computational barriers to estimation from low-degree polynomials

    Tselil Schramm and Alexander S Wein. Computational barriers to estimation from low-degree polynomials. The Annals of Statistics , 50(3):1833--1858, 2022

    2022

  51. [59]

    Tsybakov

    Alexandre B. Tsybakov. Introduction to Nonparametric Estimation . Springer New York, 2009

    2009

  52. [60]

    Noisy sorting capacity

    Ziao Wang, Nadim Ghaddar, and Lele Wang. Noisy sorting capacity. In 2022 IEEE International Symposium on Information Theory , pages 2541--2546. IEEE, 2022

    2022

  53. [61]

    Statistical problems with planted structures: Information-theoretical and computational limits

    Yihong Wu and Jiaming Xu. Statistical problems with planted structures: Information-theoretical and computational limits. Information-Theoretic Methods in Data Science , 383:13, 2021

    2021

  54. [62]

    Quantifying hierarchy and dynamics in us faculty hiring and retention

    K Hunter Wapman, Sam Zhang, Aaron Clauset, and Daniel B Larremore. Quantifying hierarchy and dynamics in us faculty hiring and retention. Nature , 610(7930):120--127, 2022

    2022

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.