Cover Image

An SoS Entropy Dichotomy via Windowed Hypercontractivity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Lela, Marko
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Primary 68Q17, Secondary 03F20, 06E30, 68Q25 F.1.3; F.1.2; F.2.2; G.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)

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

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Hive is PSPACE-Hard
by: Andel, Daniël, et al.
Published: (2025)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

Quantum algorithms through graph composition
by: Cornelissen, Arjan
Published: (2025)

Quantum walks through generalized graph composition
by: Cornelissen, Arjan
Published: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
by: Bodnar, Levente
Published: (2024)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

Quoridor is PSPACE-Complete
by: Drop, Marius, et al.
Published: (2026)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
by: Rossman, Benjamin
Published: (2024)

Quantum Advantage in Computational Chemistry?
by: Gundlach, Hans, et al.
Published: (2025)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

Computational Complexity of Determining the Assembly Index
by: Masierak, Piotr
Published: (2026)

Quantum Search without Global Diffusion
by: Burke, John, et al.
Published: (2026)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

On the computational complexity of Data Flow Analysis
by: Sood, Gaurav, et al.
Published: (2013)

Separation of PSPACE and EXP
by: Czerwinski, Reiner
Published: (2021)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
by: Philip, Geevarghese, et al.
Published: (2026)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
by: von Liechtenstein, Maximilian R. P.
Published: (2025)

Computability of Initial Value Problems
by: Brattka, Vasco, et al.
Published: (2024)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Algorithmic Barriers to Detecting and Repairing Structural Overspecification in Adaptive Data-Structure Selection
by: Alpay, Faruk, et al.
Published: (2026)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Topological Logics with Connectedness over Euclidean Spaces
by: Kontchakov, Roman, et al.
Published: (2011)

Languages of Words of Low Automatic Complexity Are Hard to Compute
by: Chen, Joey, et al.
Published: (2025)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
by: Wulf, Lasse
Published: (2025)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2024)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)