Image de couverture de livre

Stable Algorithms Lower Bounds for Estimation

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Yu, Xifan, Zadik, Ilias
Format:	Preprint
Publié:	2026
Sujets:	Statistics Theory Computational Complexity Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
par: Yu, Xifan, et autres
Publié: (2024)

Inference of rankings planted in random tournaments
par: Kunisky, Dmitriy, et autres
Publié: (2024)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
par: Luo, Yuetian, et autres
Publié: (2023)

Statistical inference of a ranked community in a directed graph
par: Kunisky, Dmitriy, et autres
Publié: (2024)

Transfer Learning Beyond Bounded Density Ratios
par: Kalavasis, Alkis, et autres
Publié: (2024)

On The MCMC Performance In Bernoulli Group Testing And The Random Max Set-Cover Problem
par: Lovig, Maxwell, et autres
Publié: (2024)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
par: R., Abhishek Hegade K., et autres
Publié: (2025)

On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule
par: Chen, Zongchen, et autres
Publié: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
par: Fleming, Noah, et autres
Publié: (2024)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
par: Sohn, Youngtak, et autres
Publié: (2025)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
par: Kunisky, Dmitriy, et autres
Publié: (2022)

Model-agnostic super-resolution in high dimensions
par: Chen, Xi, et autres
Publié: (2025)

A Quadratic Lower Bound for Stable Roommates Solvability
par: Rosenbaum, Will
Publié: (2025)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
par: Kelner, Jonathan, et autres
Publié: (2024)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
par: Kunisky, Dmitriy, et autres
Publié: (2024)

Lower Bounds for Convexity Testing
par: Chen, Xi, et autres
Publié: (2024)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
par: Fu, Daniel, et autres
Publié: (2026)

Testing Convex Truncation
par: De, Anindya, et autres
Publié: (2023)

Strong Low Degree Hardness for the Number Partitioning Problem
par: Mallarapu, Rushil, et autres
Publié: (2025)

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
par: Harvey, Nicholas, et autres
Publié: (2024)

Almost-Optimal Local-Search Methods for Sparse Tensor PCA
par: Lovig, Max, et autres
Publié: (2025)

Low-degree Security of the Planted Random Subgraph Problem
par: Bogdanov, Andrej, et autres
Publié: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
par: Bonnet, Édouard, et autres
Publié: (2025)

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

Near-Optimal Space Lower Bounds for Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2026)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
par: Wang, Yichuan
Publié: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
par: Chou, Chi-Ning, et autres
Publié: (2021)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
par: Li, Qian, et autres
Publié: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
par: Singer, Noah G., et autres
Publié: (2026)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
par: Grossman, Ofer, et autres
Publié: (2023)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
par: Assadi, Sepehr, et autres
Publié: (2024)

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
par: Ko, Young Kun
Publié: (2025)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
par: Khanna, Sanjeev, et autres
Publié: (2025)

The stochastic block model has the overlap graph property for modularity
par: Bhamidi, Shankar, et autres
Publié: (2026)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
par: Chen, Zherui, et autres
Publié: (2024)

Derandomizing Multi-Distribution Learning
par: Larsen, Kasper Green, et autres
Publié: (2024)

On Computationally Efficient Multi-Class Calibration
par: Gopalan, Parikshit, et autres
Publié: (2024)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
par: Banik, Aritra, et autres
Publié: (2025)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
par: Wang, Chengu
Publié: (2026)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
par: Jansen, Klaus, et autres
Publié: (2025)