๐ฎ
๐ฎ
The Ethereal
IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
October 10, 2025 ยท The Ethereal ยท ๐ arXiv.org
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Marko Lela
arXiv ID
2510.09808
Category
cs.CC: Computational Complexity
Cross-listed
cs.IT
Citations
0
Venue
arXiv.org
Last Checked
3 months ago
Abstract
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$ and noise stability $\mathrm{Stab}_ฯ$ -- are treated as a reusable "profile" tied to the gadget's affine interface. Under coordinate permutations ($ฮ=1$) the profile is preserved exactly; under bounded fan-in the degree budget relaxes by at most $+ฮk$ (i.e., $k \mapsto k + ฮk$), with all overheads tracked explicitly. In a balanced window $m=(1+ฮณ)n$ the framework yields a distributional lower bound for a monotone cost (Erasure Complexity, EC) and an "echo" to correlation against size-aware $\mathrm{AC}^0{+}\log$ and to logarithmic degree in the polynomial-calculus setting. The accounting keeps total-variation non-expansion and a single $O(\log N)$ prefix-free header visible end to end, avoiding hidden slack.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Computational Complexity
๐ฎ
๐ฎ
The Ethereal
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
๐ฎ
๐ฎ
The Ethereal
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
๐ฎ
๐ฎ
The Ethereal
The Hardness of Approximation of Euclidean k-means
๐ฎ
๐ฎ
The Ethereal
Slightly Superexponential Parameterized Problems
๐ฎ
๐ฎ
The Ethereal