Cover Image

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Yu, Xifan, Zadik, Ilias, Zhang, Peiyuan
Format:	Preprint
Published:	2024
Subjects:	Statistics Theory Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Low-degree Security of the Planted Random Subgraph Problem
by: Bogdanov, Andrej, et al.
Published: (2024)

Inference of rankings planted in random tournaments
by: Kunisky, Dmitriy, et al.
Published: (2024)

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

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)

On The MCMC Performance In Bernoulli Group Testing And The Random Max Set-Cover Problem
by: Lovig, Maxwell, et al.
Published: (2024)

On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule
by: Chen, Zongchen, et al.
Published: (2024)

Almost-Optimal Local-Search Methods for Sparse Tensor PCA
by: Lovig, Max, et al.
Published: (2025)

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

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
by: Curticapean, Radu, et al.
Published: (2025)

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

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
by: Curticapean, Radu, et al.
Published: (2024)

Transfer Learning Beyond Bounded Density Ratios
by: Kalavasis, Alkis, et al.
Published: (2024)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, 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)

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

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

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

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)

Detecting Low-Degree Truncation
by: De, Anindya, et al.
Published: (2024)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
by: Chen, Zherui, et al.
Published: (2024)

Derandomizing Multi-Distribution Learning
by: Larsen, Kasper Green, et al.
Published: (2024)

On Computationally Efficient Multi-Class Calibration
by: Gopalan, Parikshit, et al.
Published: (2024)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
by: Kelner, Jonathan, et al.
Published: (2024)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
by: Luo, Yuetian, et al.
Published: (2023)

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

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

A Note on Approximability of Densest At-Least-k-Subgraph
by: Laekhanukit, Bundit, et al.
Published: (2026)

Gray Codes With Constant Delay and Constant Auxiliary Space
by: Amarilli, Antoine, et al.
Published: (2026)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
by: Kumar, Mrinal, et al.
Published: (2024)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
by: Abboud, Amir, et al.
Published: (2026)

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

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
by: Dey, Palash, et al.
Published: (2026)

Optimality of Frequency Moment Estimation
by: Braverman, Mark, et al.
Published: (2024)

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

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
by: Garg, Sumegha, et al.
Published: (2026)

The Quasi-Polynomial Low-Degree Conjecture is False
by: Buhai, Rares-Darius, et al.
Published: (2025)