Image de couverture de livre

Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Even, Bertrand, Giraud, Christophe, Verzelen, Nicolas
Format:	Preprint
Publié:	2025
Sujets:	Statistics Theory 68Q17
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Computational lower bounds in latent models: clustering, sparse-clustering, biclustering
par: Even, Bertrand, et autres
Publié: (2025)

Computation-information gap in high-dimensional clustering
par: Even, Bertrand, et autres
Publié: (2024)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
par: Li, Zhangsong
Publié: (2026)

The Algorithmic Phase Transition in Correlated Spiked Models
par: Li, Zhangsong
Publié: (2025)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
par: Li, Zhangsong
Publié: (2025)

Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
par: Bhamidi, Shankar, et autres
Publié: (2025)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
par: Lin, Tianrong
Publié: (2023)

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
par: Li, Zhangsong
Publié: (2026)

Minimax optimal seriation in polynomial time
par: Issartel, Yann, et autres
Publié: (2024)

A computational transition for detecting correlated stochastic block models by low-degree polynomials
par: Chen, Guanyi, et autres
Publié: (2024)

Adaptivity Under Realizability Constraints: Comparing In-Context and Agentic Learning
par: Kratsios, Anastasis, et autres
Publié: (2026)

Resolution of The Linear-Bounded Automata Question
par: Lin, Tianrong
Publié: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
par: Lin, Tianrong
Publié: (2021)

Languages given by Finite Automata over the Unary Alphabet
par: Czerwiński, Wojciech, et autres
Publié: (2023)

Computational Complexity of Finding Subgroups of a Given Order
par: Lakshmanan, K.
Publié: (2025)

Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities
par: Carpentier, Alexandra, et autres
Publié: (2025)

Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II)
par: Carpentier, Alexandra, et autres
Publié: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
par: Hu, Ivan, et autres
Publié: (2022)

Minimal Unimodal Decomposition is NP-Hard on Graphs
par: K, Mishal Assif P, et autres
Publié: (2025)

The Separation of $NP$ and $PSPACE$
par: Lin, Tianrong
Publié: (2021)

Teaching and Learning under Deductive Errors
par: Telle, Jan Arne, et autres
Publié: (2026)

The complexity of intersecting subproducts with subgroups in Cartesian powers
par: Spelier, Pim
Publié: (2021)

Asymptotic Optimism of Random-Design Linear and Kernel Regression Models
par: Luo, Hengrui, et autres
Publié: (2025)

Adaptive learning of density ratios in RKHS
par: Zellinger, Werner, et autres
Publié: (2023)

P not equal to NP
par: Delgado, Daniel Cardona
Publié: (2023)

Identities of triangular Boolean matrices
par: Volkov, Mikhail V.
Publié: (2024)

Unifying lower bounds for algebraic machines, semantically
par: Seiller, Thomas, et autres
Publié: (2018)

The Computational Complexity of Variational Inequalities and Applications in Game Theory
par: Kapron, Bruce M., et autres
Publié: (2024)

Domain Generalization by Functional Regression
par: Holzleitner, Markus, et autres
Publié: (2023)

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

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

Quantum Physics using Weighted Model Counting
par: Ende, Dirck van den, et autres
Publié: (2025)

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

Universality of conformal prediction under the assumption of randomness
par: Vovk, Vladimir
Publié: (2025)

A Formalization of Co-Transcriptional Splicing as an Operation on Formal Languages
par: Cho, Da-Jung, et autres
Publié: (2025)

Context-Free Trees
par: Wächter, Jan Philipp
Publié: (2026)

Undefinability of Approximation of 2-to-2 Games
par: Dawar, Anuj, et autres
Publié: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
par: Kelley, Zander, et autres
Publié: (2023)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
par: Abdullah, Duaa, et autres
Publié: (2025)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
par: Ilmavirta, Joonas, et autres
Publié: (2023)