Theoretical Computer Science
Unconditional Lower-Bound Barrier for AC0-Natural Proofs Against Constant-Depth Circuits
This paper establishes an unconditional lower-bound barrier for AC0-natural proofs against constant-depth circuits. While natural proofs were previously shown to have limitations under cryptographic assumptions, this work provides an unconditional result by adapting the Trevisan-Xue pseudorandom gen…
Sharper Amenability Bounds for Local Coordination Games via Shapley-Weighted Mutual Information
Peretz and Kraizberg improve quantitative bounds connecting low-disagreement local coordination games on finite social networks to graph amenability. Prior work by Hutchcroft, Rospuskova, and Tamuz established that low inefficiency implies amenability but with a square-root loss in the amenability p…
Optimal Reed-Muller Code Testing Achieved Under Adversarial Online Erasures
Kelman, Meir, and Zheng introduce *semi-sample-based testers* — a hybrid between fully adaptive and purely random-query testers — to address Reed-Muller code property testing under the online-erasure adversary model, where an adversary can erase up to *t* input points after each query. They prove th…
SMB Algebras Yield Tractable CSP Templates: Bridging Bulatov and Zhuk's Dichotomy Proofs
This paper formally introduces semilattices of Mal'cev blocks (SMB algebras) — algebraic structures where each element of a semilattice is "blown up" into a Mal'cev algebra — and proves that all such algebras induce tractable templates of the Constraint Satisfaction Problem (CSP). Beyond tractabilit…