Polylogarithmic Genus Does Not Increase the Power of Constant-Width Polynomial-Size Circuits: A Separator-Based Candidate Proof

Abstract

ZENODO METADATA - ALLENDER POLYLOGARITHMIC GENUS PREPRINT, VERSION 1Prepared: 7 August 2026 RESOURCE TYPEPublication -> Preprint (choose "Publication" and, if the interface asks for a subtype, choose "Preprint") TITLEPolylogarithmic Genus Does Not Increase the Power of Constant-Width Polynomial-Size Circuits: A Separator-Based Candidate Proof CREATORFamily name: PochuevGiven names: GrishaAffiliation: leave blank unless you want to state a current research affiliationORCID: leave blank unless you have an ORCID PUBLICATION DATE2026-08-07 VERSIONv1.0 LANGUAGEEnglish DESCRIPTION / ABSTRACTAllender, Datta, and Roy claimed that constant-width polynomial-size Boolean circuits of polylogarithmic orientable genus compute exactly ACC^0. The published proof was later found to contain a false topological assertion, and Eric Allender listed the upper-bound direction as an open problem with a US$1000 bounty. This preprint presents a different candidate proof that avoids the handle-placement argument entirely. The key observation is a layer-separator lemma: if a layered graph has N vertices and orientable genus g, then deleting at most g(ceil(log_2 N)+1) whole layers makes the graph planar. The circuit consequently decomposes into O(g log N) planar macroblocks and constant-size boundary transitions. Each planar macroblock is simulated in ACC^0 using Hansen's characterization of planar constant-width computation. Because the state space of a constant-width circuit has constant size, a polylogarithmic number of macroblock relations can be composed in constant depth with polynomial size. The manuscript gives a complete proof candidate for the intended nonuniform polynomial-size statement, while explicitly identifying the points requiring independent expert verification. A companion Lean 4 formalization repository is available at https://github.com/Grisha-Pochuev/allender-polylog-genus-lean. The formalization is currently in active development and the repository records its current verification status and reproducible build instructions. Contact: n_854@mail.ru KEYWORDScircuit complexityACC^0constant-width circuitspolylogarithmic genusgraph genusplanar circuitsBoolean circuitscomputational complexityformal verificationLean 4 LICENSERecommended for this preprint: Creative Commons Attribution 4.0 International (CC BY 4.0), which is Zenodo's default license. Confirm that you are comfortable with reuse under attribution before publishing. ACCESSPublic / Open access PUBLISHERZenodo (leave the default, since this is the first public repository publication of this version) RELATED IDENTIFIER / REPOSITORYhttps://github.com/Grisha-Pochuev/allender-polylog-genus-leanSuggested relation if the form offers it: "is supplemented by" / "isSupplementedBy" (the Lean repository supplements the preprint). DOI10.5281/zenodo.21829785 (reserved Zenodo DOI; embedded in the final manuscript PDF) FILES TO UPLOAD1. allender_polylog_genus_acc0_zenodo_final.pdf [primary/preferred preview]2. allender_polylog_genus_acc0_zenodo_final.tex [source] OPTIONALzenodo_metadata_allender_preprint_v1.txt can also be uploaded for archival transparency, but it is not necessary because its contents are copied into Zenodo's metadata fields.