IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908587463278592 |
|---|---|
| author | Lela, Marko |
| author_facet | Lela, Marko |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_09808 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants Lela, Marko Computational Complexity Information Theory 68Q17, 68Q15, 03F20 F.1.3; F.2.2; G.2.1 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. |
| title | IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants |
| topic | Computational Complexity Information Theory 68Q17, 68Q15, 03F20 F.1.3; F.2.2; G.2.1 |
| url | https://arxiv.org/abs/2510.09808 |