Imagen de Portada

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	R., Abhishek Hegade K., Kızıldağ, Eren C.
Formato:	Preprint
Publicado:	2025
Materias:	Statistics Theory Computational Complexity Data Structures and Algorithms Probability
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
por: Kızıldağ, Eren C.
Publicado: (2023)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
por: Dhawan, Abhishek, et al.
Publicado: (2026)

Sharp Online Hardness for Large Balanced Independent Sets
por: Dhawan, Abhishek, et al.
Publicado: (2025)

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

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

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

Testing Convex Truncation
por: De, Anindya, et al.
Publicado: (2023)

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

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

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

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

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

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

Discrepancy Algorithms for the Binary Perceptron
por: Li, Shuangping, et al.
Publicado: (2024)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
por: Gamarnik, David, et al.
Publicado: (2026)

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

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

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
por: Dhawan, Abhishek, et al.
Publicado: (2024)

Pseudodeterministic Algorithms for Minimum Cut Problems
por: Agarwala, Aryan, et al.
Publicado: (2025)

Optimal Hardness of Online Algorithms for Large Independent Sets
por: Gamarnik, David, et al.
Publicado: (2025)

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

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
por: Moka, Sarat, et al.
Publicado: (2026)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
por: Huang, Neng, et al.
Publicado: (2024)

Random tensor isomorphism under orthogonal and unitary actions
por: Chizewer, Jeremy, et al.
Publicado: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
por: Li, Tiange, et al.
Publicado: (2026)

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

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
por: Zhang, Bingwei, et al.
Publicado: (2026)

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
por: Gall, François Le
Publicado: (2024)

An Instance-Based Approach to the Trace Reconstruction Problem
por: Mazooji, Kayvon, et al.
Publicado: (2024)

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

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

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

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

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

Polynomial-time sampling despite disorder chaos
por: Ma, Eric, et al.
Publicado: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
por: Kunisky, Dmitriy, et al.
Publicado: (2024)

Some easy optimization problems have the overlap-gap property
por: Li, Shuangping, et al.
Publicado: (2024)

Efficient Catalytic Graph Algorithms
por: Cook, James, et al.
Publicado: (2025)

Improved Algorithm for Permutation Testing
por: Zhang, Xiaojin
Publicado: (2020)

Universal entrywise eigenvector fluctuations in delocalized spiked matrix models and asymptotics of rounded spectral algorithms
por: Chen, Shujing, et al.
Publicado: (2025)