Cover Image

Inference of rankings planted in random tournaments

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kunisky, Dmitriy, Spielman, Daniel A., Yu, Xifan
Format:	Preprint
Published:	2024
Subjects:	Statistics Theory Computational Complexity Data Structures and Algorithms Combinatorics Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Statistical inference of a ranked community in a directed graph
by: Kunisky, Dmitriy, et al.
Published: (2024)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
by: Kunisky, Dmitriy
Published: (2024)

Tensor cumulants for statistical inference on invariant distributions
by: Kunisky, Dmitriy, et al.
Published: (2024)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
by: Kunisky, Dmitriy, et al.
Published: (2022)

The stochastic block model has the overlap graph property for modularity
by: Bhamidi, Shankar, et al.
Published: (2026)

Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise
by: De, Debsurya, et al.
Published: (2025)

Universal entrywise eigenvector fluctuations in delocalized spiked matrix models and asymptotics of rounded spectral algorithms
by: Chen, Shujing, et al.
Published: (2025)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
by: Fu, Daniel, et al.
Published: (2026)

Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
by: Kunisky, Dmitriy
Published: (2024)

Stable Algorithms Lower Bounds for Estimation
by: Yu, Xifan, et al.
Published: (2026)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
by: Yu, Xifan, et al.
Published: (2024)

Nonlinear Laplacians: Tunable principal component analysis under directional prior information
by: Ma, Yuxin, et al.
Published: (2025)

Fitting an ellipsoid to random points: predictions using the replica method
by: Maillard, Antoine, et al.
Published: (2023)

Universality of first-order methods on random and deterministic matrices
by: Gorini, Nicola, et al.
Published: (2026)

Testing Convex Truncation
by: De, Anindya, et al.
Published: (2023)

Detection of local geometry in random graphs: information-theoretic and computational limits
by: Bok, Jinho, et al.
Published: (2026)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
by: R., Abhishek Hegade K., et al.
Published: (2025)

Strong Low Degree Hardness for the Number Partitioning Problem
by: Mallarapu, Rushil, et al.
Published: (2025)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
by: Sohn, Youngtak, et al.
Published: (2025)

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
by: Harvey, Nicholas, et al.
Published: (2024)

Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms
by: Kunisky, Dmitriy, et al.
Published: (2023)

Some easy optimization problems have the overlap-gap property
by: Li, Shuangping, et al.
Published: (2024)

Polynomial-time sampling despite disorder chaos
by: Ma, Eric, et al.
Published: (2025)

Composition of random functions and word reconstruction
by: Chapuy, Guillaume, et al.
Published: (2026)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2026)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2024)

Sharp Online Hardness for Large Balanced Independent Sets
by: Dhawan, Abhishek, et al.
Published: (2025)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
by: Gamarnik, David, et al.
Published: (2026)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

Model-agnostic super-resolution in high dimensions
by: Chen, Xi, et al.
Published: (2025)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
by: Collins, Nathaniel A., et al.
Published: (2024)

Explicit Good Codes Approaching Distance 1 in Ulam Metric
by: Goldenberg, Elazar, et al.
Published: (2024)

Computational lower bounds for multi-frequency group synchronization
by: Kireeva, Anastasia, et al.
Published: (2024)

Finding planted cliques using gradient descent
by: Gheissari, Reza, et al.
Published: (2023)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

On Detecting $H$-Induced Minors for Small $H$
by: Eagling-Vose, Tala, et al.
Published: (2026)

Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
by: Fan, Zhou, et al.
Published: (2026)

Hypergraph Samplers: Typical and Worst Case Behavior
by: Alev, Vedat Levi, et al.
Published: (2026)

Testing Sumsets is Hard
by: Chen, Xi, et al.
Published: (2024)