Cover Image

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Luo, Yuetian, Gao, Chao
Format:	Preprint
Published:	2023
Subjects:	Statistics Theory Computational Complexity Data Structures and Algorithms Machine Learning
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)

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

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

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

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

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

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

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

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
by: Chen, Sitan, et al.
Published: (2026)

Low-degree phase transitions for detecting a planted clique in sublinear time
by: Mardia, Jay, et al.
Published: (2024)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
by: Chakrabarty, Deeparnab, et al.
Published: (2025)

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

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Statistical Query Lower Bounds for Learning Truncated Gaussians
by: Diakonikolas, Ilias, et al.
Published: (2024)

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

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

SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
by: Diakonikolas, Ilias, et al.
Published: (2024)

Computing High-dimensional Confidence Sets for Arbitrary Distributions
by: Gao, Chao, et al.
Published: (2025)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

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

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

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

Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
by: Diakonikolas, Ilias, et al.
Published: (2025)

Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers
by: Diakonikolas, Ilias, et al.
Published: (2026)

PTF Testing Lower Bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2025)

Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
by: Lee, Jane H., et al.
Published: (2024)

Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination
by: Diakonikolas, Ilias, et al.
Published: (2026)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Better and Simpler Lower Bounds for Differentially Private Statistical Estimation
by: Narayanan, Shyam
Published: (2023)

Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
by: Chen, Sitan, et al.
Published: (2025)

Query Lower Bounds for Diffusion Sampling
by: Xun, Zhiyang, et al.
Published: (2026)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

The Computational Complexity of Almost Stable Clustering with Penalties
by: Khodamoradi, Kamyar, et al.
Published: (2025)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

Low-Degree Method Fails to Predict Robust Subspace Recovery
by: Jia, He, et al.
Published: (2026)

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

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
by: Ko, Young Kun
Published: (2026)

ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
by: Hertrich, Christoph, et al.
Published: (2021)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)