Polylogarithmic Genus Does Not Increase the Power of Constant-Width Polynomial-Size Circuits

Abstract

Allender, Datta, and Roy claimed that constant-width polynomial-size Boolean circuits of polylogarithmic orientable genus compute exactly ACC^0. The published proof of the upper bound was later found to contain an incorrect topological assertion, and Eric Allender subsequently listed the corresponding question as open with a US$1000 prize. This revised preprint gives a different separator-based proof that avoids the handle-placement argument entirely. The central lemma shows that a layered graph with N vertices and orientable genus at most g can be made planar by deleting at most g(ceil(log_2 N)+1) whole layers. For constant-width circuits, these cuts yield only polylogarithmically many planar macroblocks with constant-size state interfaces. The planar blocks are simulated using Hansen's characterization of constant-width planar computation, with all block simulations packaged into one family so that a single fixed modulus is obtained. The resulting finite-state relations are then composed in a constant number of rounds with polynomial size. Version 6.0 substantially revises the earlier manuscript after additional adversarial review. In particular, it makes the compatibility with Hansen's circuit model explicit, closes the common-modulus issue, and strengthens the planarization, macroblock-boundary, and relation-composition arguments. The accompanying Lean 4 development checks the end-to-end separator-based reduction in the repository's normalized circuit model. The final checked declaration is Allender.allender_polylog_genus_in_ACC0. The verification is relative to an explicit external boundary consisting of standard facts about orientable graph genus and the published forward direction of Hansen's theorem; those external results are not re-proved from first principles in Lean. The paper also explicitly records a finite input-length-zero wrapper that lies outside the checked Lean declaration. Repository and reproducibility materials:https://github.com/Grisha-Pochuev/allender-polylog-genus-lean Independent expert review of the mathematical argument is welcomed. n_854@mail.ru