Image de couverture de livre

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

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Lela, Marko
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity Information Theory Logic in Computer Science 68Q15, 68Q17 F.1.3; F.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
par: Lela, Marko
Publié: (2025)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
par: Dorochko, Leonid, et autres
Publié: (2026)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
par: Lela, Marko
Publié: (2025)

Completeness classes in algebraic complexity theory
par: Bürgisser, Peter
Publié: (2024)

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

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
par: Böhnlein, Toni, et autres
Publié: (2024)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
par: Ye, Lixi
Publié: (2026)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
par: Hakoniemi, Tuomas, et autres
Publié: (2024)

Counting Martingales for Measure and Dimension in Complexity Classes
par: Hitchcock, John M., et autres
Publié: (2025)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
par: Filmus, Yuval, et autres
Publié: (2020)

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

The Word Problem for Products of Symmetric Groups
par: Simon, Hans U.
Publié: (2025)

On Small-depth Frege Proofs for PHP
par: Håstad, Johan
Publié: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
par: Levin, Leonid A.
Publié: (2022)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
par: Xia, Mingji
Publié: (2026)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
par: Eua-anant, Pakapim, et autres
Publié: (2025)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
par: Phillips, Reed
Publié: (2026)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
par: Bodirsky, Manuel, et autres
Publié: (2024)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
par: Levet, Michael, et autres
Publié: (2023)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
par: Kumar, Mrinal, et autres
Publié: (2018)

Finitely (In)tractable Promise Constraint Satisfaction Problems
par: Asimi, Kristina, et autres
Publié: (2020)

Some derivations among Logarithmic Space Bounded Counting Classes
par: Janaki, V., et autres
Publié: (2023)

On weighted graph separation problems and flow-augmentation
par: Kim, Eun Jung, et autres
Publié: (2022)

Upper and Lower Bounds for the Linear Ordering Principle
par: Hirsch, Edward A., et autres
Publié: (2025)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
par: Grochow, Joshua A., et autres
Publié: (2021)

Count-Free Weisfeiler--Leman and Group Isomorphism
par: Collins, Nathaniel A., et autres
Publié: (2022)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
par: Grochow, Joshua A., et autres
Publié: (2025)

From Gödel incompleteness to the consistency of circuit lower bounds
par: Atserias, Albert, et autres
Publié: (2026)

Logarithmic Weisfeiler--Leman and Treewidth
par: Levet, Michael, et autres
Publié: (2023)

Computational Complexity of Determining the Assembly Index
par: Masierak, Piotr
Publié: (2026)

Shifted Partial Derivative Polynomial Rank and Codimension
par: Edwards, Darren J.
Publié: (2025)

Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
par: Kornerup, Niels, et autres
Publié: (2021)

DAG Scheduling in the BSP Model
par: Papp, Pál András, et autres
Publié: (2023)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
par: Saffidine, Abdallah, et autres
Publié: (2025)

The Optimizer Quotient and the Certification Trilemma
par: Simas, Tristan
Publié: (2026)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
par: Huseynzade, Rafig
Publié: (2025)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
par: Bodirsky, Manuel, et autres
Publié: (2023)

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

Termination of Innermost-Terminating Right-Linear Overlay Term Rewrite Systems (Full Version)
par: Nishida, Naoki
Publié: (2026)

Rewriting Induction for Existentially Quantified Equations in Logically Constrained Rewriting (Full Version)
par: Nishida, Naoki, et autres
Publié: (2026)