Image de couverture de livre

The Quasi-Polynomial Low-Degree Conjecture is False

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Buhai, Rares-Darius, Hsieh, Jun-Ting, Jain, Aayush, Kothari, Pravesh K.
Format:	Preprint
Publié:	2025
Sujets:	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

Rounding Large Independent Sets on Expanders
par: Bafna, Mitali, et autres
Publié: (2024)

Semirandom Planted Clique and the Restricted Isometry Property
par: Błasiok, Jarosław, et autres
Publié: (2024)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
par: Kothari, Pravesh K., et autres
Publié: (2025)

Lasso and Partially-Rotated Designs
par: Buhai, Rares-Darius
Publié: (2025)

Detecting Low-Degree Truncation
par: De, Anindya, et autres
Publié: (2024)

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

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
par: Mao, Songtao
Publié: (2026)

Tensor Hinted Mv Conjectures
par: Song, Zhao
Publié: (2026)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
par: Guruswami, Venkatesan, et autres
Publié: (2024)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Finding Colorings in One-Sided Expanders
par: Buhai, Rares-Darius, et autres
Publié: (2025)

Structural Parameterizations for Two Bounded Degree Problems Revisited
par: Lampis, Michael, et autres
Publié: (2023)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
par: Shao, Shuai, et autres
Publié: (2023)

Solving Polynomial Equations Over Finite Fields
par: Dell, Holger, et autres
Publié: (2024)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
par: Sajith, Thejas Radhika
Publié: (2025)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
par: Asadi, Vahid R., et autres
Publié: (2026)

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

Low-Degree Method Fails to Predict Robust Subspace Recovery
par: Jia, He, et autres
Publié: (2026)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
par: Dumas, Maël, et autres
Publié: (2022)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
par: Jiang, Cheng, et autres
Publié: (2026)

Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
par: Hsieh, Jun-Ting, et autres
Publié: (2026)

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

Uniformity testing when you have the source code
par: Canonne, Clément L., et autres
Publié: (2024)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
par: Sharma, Amatya, et autres
Publié: (2026)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
par: Yoshida, Yuichi, et autres
Publié: (2025)

Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
par: Hsieh, Jun-Ting, et autres
Publié: (2024)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
par: Vroon, Mats, et autres
Publié: (2025)

Second Price Matching with Complete Allocation and Degree Constraints
par: Pinchasi, Rom, et autres
Publié: (2025)

Quantum Property Testing for Bounded-Degree Directed Graphs
par: Peng, Pan, et autres
Publié: (2026)

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
par: Leake, Jonathan, et autres
Publié: (2025)

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

Polynomial-Time Pseudodeterministic Construction of Primes
par: Chen, Lijie, et autres
Publié: (2023)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
par: Leake, Jonathan, et autres
Publié: (2025)

Polynomial-time sampling despite disorder chaos
par: Ma, Eric, et autres
Publié: (2025)

Polynomial-time tolerant testing stabilizer states
par: Arunachalam, Srinivasan, et autres
Publié: (2024)

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

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
par: Rai, Shanthanu S
Publié: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
par: Assadi, Sepehr, et autres
Publié: (2024)

Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
par: Chen, Sitan, et autres
Publié: (2025)

A General Framework for Low Soundness Homomorphism Testing
par: Mittal, Tushant, et autres
Publié: (2025)