:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Even, Bertrand, Giraud, Christophe, Verzelen, Nicolas
Format:	Preprint
Published:	2025
Subjects:	Statistics Theory 68Q17
Online Access:	https://arxiv.org/abs/2507.07946
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computational lower bounds in latent models: clustering, sparse-clustering, biclustering
by: Even, Bertrand, et al.
Published: (2025)

Computation-information gap in high-dimensional clustering
by: Even, Bertrand, et al.
Published: (2024)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
by: Li, Zhangsong
Published: (2026)

The Algorithmic Phase Transition in Correlated Spiked Models
by: Li, Zhangsong
Published: (2025)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
by: Li, Zhangsong
Published: (2025)

Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
by: Bhamidi, Shankar, et al.
Published: (2025)

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
by: Li, Zhangsong
Published: (2026)

A computational transition for detecting correlated stochastic block models by low-degree polynomials
by: Chen, Guanyi, et al.
Published: (2024)

Adaptivity Under Realizability Constraints: Comparing In-Context and Agentic Learning
by: Kratsios, Anastasis, et al.
Published: (2026)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Minimax optimal seriation in polynomial time
by: Issartel, Yann, et al.
Published: (2024)

Minimal Unimodal Decomposition is NP-Hard on Graphs
by: K, Mishal Assif P, et al.
Published: (2025)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities
by: Carpentier, Alexandra, et al.
Published: (2025)

Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II)
by: Carpentier, Alexandra, et al.
Published: (2025)

Languages given by Finite Automata over the Unary Alphabet
by: Czerwiński, Wojciech, et al.
Published: (2023)

Computational Complexity of Finding Subgroups of a Given Order
by: Lakshmanan, K.
Published: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Identities of triangular Boolean matrices
by: Volkov, Mikhail V.
Published: (2024)

Asymptotic Optimism of Random-Design Linear and Kernel Regression Models
by: Luo, Hengrui, et al.
Published: (2025)

Adaptive learning of density ratios in RKHS
by: Zellinger, Werner, et al.
Published: (2023)

Teaching and Learning under Deductive Errors
by: Telle, Jan Arne, et al.
Published: (2026)

Quantum Physics using Weighted Model Counting
by: Ende, Dirck van den, et al.
Published: (2025)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

The complexity of intersecting subproducts with subgroups in Cartesian powers
by: Spelier, Pim
Published: (2021)

Universality of conformal prediction under the assumption of randomness
by: Vovk, Vladimir
Published: (2025)

The Computational Complexity of Variational Inequalities and Applications in Game Theory
by: Kapron, Bruce M., et al.
Published: (2024)

Context-Free Trees
by: Wächter, Jan Philipp
Published: (2026)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

A Formalization of Co-Transcriptional Splicing as an Operation on Formal Languages
by: Cho, Da-Jung, et al.
Published: (2025)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Domain Generalization by Functional Regression
by: Holzleitner, Markus, et al.
Published: (2023)

The Feldman-Hájek Dichotomy for Countable Gaussian Mixtures and their Asymptotic Separability in High Dimensions
by: Michelucci, Umberto
Published: (2026)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

E-variables and tests of randomness for distribution classes
by: Potapov, Georgii, et al.
Published: (2026)

Sample completion, structured correlation, and Netflix problems
by: Coregliano, Leonardo N., et al.
Published: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)