Copertina

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Li, Tiange, Li, Yinan, Qiao, Youming, Tao, Dacheng, Wang, Yingjie
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Data Structures and Algorithms Probability
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

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

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

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

Stable algorithms cannot reliably find isolated perceptron solutions
di: Gong, Shuyang, et al.
Pubblicazione: (2026)

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

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
di: Scheder, Dominik, et al.
Pubblicazione: (2025)

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

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

A computational phase transition for learning-to-sample from Ising models
di: Risteski, Andrej, et al.
Pubblicazione: (2026)

Sparsifying Suprema of Gaussian Processes
di: De, Anindya, et al.
Pubblicazione: (2024)

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

Parameter estimation for Gibbs distributions
di: Harris, David G., et al.
Pubblicazione: (2020)

Testing Convex Truncation
di: De, Anindya, et al.
Pubblicazione: (2023)

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

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

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
di: Yang, Yang
Pubblicazione: (2024)

Constructing self-referential instances for the clique problem
di: Li, Jiaqi, et al.
Pubblicazione: (2026)

Tensor Hinted Mv Conjectures
di: Song, Zhao
Pubblicazione: (2026)

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

On the complexity of global Roman domination problem in graphs
di: Reddy, Sangam Balchandar, et al.
Pubblicazione: (2026)

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

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

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

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

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

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

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

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
di: Kothari, Pravesh K., et al.
Pubblicazione: (2025)

The communication complexity of distributed estimation
di: Gopalan, Parikshit, et al.
Pubblicazione: (2025)

Parameterized complexity of reconfiguration of atoms
di: Cooper, Alexandre, et al.
Pubblicazione: (2021)

An alignment problem
di: McDaniel, Emma L., et al.
Pubblicazione: (2024)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
di: Wang, Chengu
Pubblicazione: (2026)

Sketching approximations and LP approximations for finite CSPs are related
di: Singer, Noah G., et al.
Pubblicazione: (2025)

On the complexity and approximability of Bounded access Lempel Ziv coding
di: Cicalese, Ferdinando, et al.
Pubblicazione: (2024)

On girth and the parameterized complexity of token sliding and token jumping
di: Bartier, Valentin, et al.
Pubblicazione: (2020)