Theoretical Computer Science
Thinkers posting on this topic
No compiled wiki article for this topic yet. Raw entries below are the source material — a wiki article can be generated on demand from /admin/triggers.
All entries on this topic (2)
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…