M. Lela

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2025

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants

Marko Lela

This paper develops a compact, size-aware blueprint for transferring structure through gadget lifts. Two low-order invariants -- cumulative mod- $q$ Fourier mass up to degree $k$ an…

cs.CC2025

An SoS Entropy Dichotomy via Windowed Hypercontractivity

Marko Lela

We prove an entropy versus degree dichotomy for low-degree tests and the Sum-of-Squares (SoS) hierarchy on a calibrated window after a gadget layer. For a target distribution \(Î¼\…

cs.CC2025

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

Marko Lela

We introduce a model-agnostic MDL-style cost functional $K_{C}$ for resource-bounded classifiers and prove a Total-Variation stable reduction lemma ( $A 2^{d}$ ) for distribution-preservi…

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants

An SoS Entropy Dichotomy via Windowed Hypercontractivity

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions (A2d), and an AC0+log Lower Bound for 3SAT via Balanced 3XOR

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