Source-linked AI summary
Topology inside NC$^1$
Eric Allender, Samir Datta, Arsenii Karnaukhov, Sambuddha Roy, Alexander Shekhovstov
TL;DR
The paper asks whether relaxing planarity can characterize complexity classes between ACC0 and NC1. It proves that polylogarithmic genus and crossing number still characterize ACC0, whereas thickness two suffices for all of NC1.
Problem
The paper studies whether graph-theoretic relaxations of planarity can yield constant-width circuit characterizations for complexity classes between ACC0 and NC1.
Method
It analyzes constant-width polynomial-size circuits under polylogarithmic genus, crossing number, and thickness constraints, using planar ACC0 and branching-program characterizations.
Results
Polylogarithmic genus and crossing number characterize ACC0, while thickness two suffices to compute all problems in NC1.
Takeaways & Limitations
Polylogarithmic genus provides no additional computational power over planar constant-width circuits, and genus, crossing number, and thickness do not characterize TC0.
Takeaways & Limitations
A constant-width circuit characterization of TC0 remains an open problem, and the preliminary version’s main proof was incorrect.
Abstract
from arXiv · showhide
We show that ACC$^0$ is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC$^0$. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of planarity, including crossing number and thickness. We show that constant-width circuits of polynomial size and thickness two already suffice to capture all of NC$^1$.
1. Introduction
The paper investigates whether graph-theoretic relaxations of planarity yield constant-width circuit characterizations between ACC0 and NC1. It proves that polylogarithmic genus and crossing number remain within ACC0, while thickness two reaches NC1.
- The study targets TC0 because it lies between ACC0 and NC1, using graph notions intermediate between planar and unrestricted circuits.
- Constant-width polynomial-size circuits of polylogarithmic genus compute exactly ACC0.The result extends Hansen’s planar characterization and shows that polylogarithmic genus adds no computational power in this model.
- Constant-width polynomial-size circuits of thickness two already compute all problems in NC1.
- Polylogarithmic crossing number yields the same computational class as polylogarithmic genus, namely ACC0.
- The paper leaves a constant-width circuit characterization of TC0 as its main open problem.The proved characterizations rule out crossing number, genus, and thickness as likely candidates for such a characterization.
2. Definitions and Preliminaries
The preliminaries define layered constant-width circuits and graph-theoretic measures that generalize planarity. They establish Hansen’s planar ACC0 characterization as the starting point for the genus analysis.
- A layered digraph partitions vertices into levels, with every directed edge going from one level to the next.
- The width of a layered digraph is the maximum number of vertices in any level.
- A width-w circuit is a layered digraph of width w whose vertices are AND gates, OR gates, input variables, or negated input variables.Inputs may occur at any level and may appear multiple times.
- Hansen’s theorem states that ACC0 equals the languages accepted by constant-width planar circuits of polynomial size.
- Genus is the least number of handles needed for a crossing-free embedding, with planar graphs having genus zero.
- The revised proof does not need the preliminary version’s detailed assumptions about embeddings of circuits on genus-k surfaces.Instead, it uses a simpler proof based on a theorem about graph genus.
3. Small Genus Characterizes ACC0
Constant-width polynomial-size circuits of polylogarithmic genus characterize ACC0. The proof partitions each circuit into few planar or single-layer segments and simulates their state transitions within ACC0.
- A language is in ACC0 exactly when it is accepted by constant-width circuits of polynomial size and polylogarithmic genus.
- A genus-g circuit can be partitioned into at most 3g + 10 consecutive segments, each planar or spanning only one layer.The partition is constructed greedily; too many disjoint nonplanar subgraphs would force genus greater than g.
- Planar segments are converted using Hansen’s characterization into constant-depth AND, OR, MOD_m circuits, with one modulus depending only on the circuit width.A common modulus can simulate the finitely many moduli arising from widths at most w.
- The ACC0 transition function maps each width-w boundary state and input to the next boundary state for every circuit segment.The function f(x, v, i) outputs the state z produced by segment i from input x and starting state v.
- These transitions form a width-2w layered graph, and acceptance reduces to path existence checked by a polynomial-size depth-2 disjunctive normal form.For segments Θ(log n) layers apart, enumerating the at most 2^wl paths yields a polynomial-size DNF.
4. A new characterization of NC1
The paper characterizes NC1 using constant-width polynomial-size circuits on three pages, via an equivalent three-stack computation model and a thickness-two consequence.
- Three-page characterization: Three-page circuits use a common spine, with each wire confined to one upward-planar half-plane.The three half-planes form the pages, and the spine serves as the shared intersecting line.
- Thickness consequence: Every graph embedded on three pages has thickness at most two by grouping the first two pages together and the third separately.The first group and the third page each contain no crossings within their respective edge sets.
- Three-stack simulation: The stacks(a, b, c) model uses three bounded-height pushdown stores and a computation register with fixed, input-independent instruction locations.Its instructions push, pop, copy, or discard bits, combine stack values with AND or OR, or combine a stack value with an input literal; running time is polynomial.
- Three-stack simulation: Oblivious three-stack computation maps to three pages by representing stack heights as page widths and the register as the spine.Stack operations correspond to moving bits toward or away from the spine, while Boolean combinations are implemented by bringing relevant bits together.
- Three-stack simulation: Barrington’s permutation branching programs encode five state bits in stacks of heights 2, 2, and 1, with transposition instructions reduced to two types.Type 1 swaps tops of two stacks; Type 2 swaps two bits within one stack, and every instruction can be simulated using these types.
- Three-stack simulation: The simulation needs maximum stack heights (3,3,2), because Type 2 operations add one place to each of the other two stacks.A Type 2 operation on the first stack uses heights (2,3,2), and one on the second uses (3,2,2).
5. Discussion
The paper leaves a constant-width circuit characterization of TC0 unresolved, ruling out several candidate approaches while identifying related positive characterizations and an intriguing genus–solvability connection.
- A constant-width circuit characterization of TC0 remains an open challenge for future work.
- Crossing number, genus, and thickness do not appear to provide characterizations of TC0 in this framework.The authors state that their results seem to rule out these graph-theoretic approaches.
- Algebraic approaches based on regular sets seem unpromising because regular sets not complete for NC1 lie inside ACC0.
- Counting accepting paths in a width-two planar branching program is hard for NC1 under ACC0 reductions, ruling out many arithmetization-based approaches to TC0.
- Related work characterizes #AC0 and hence TC0 through restricted branching-program path counting, while arithmetic NC1 has a log-width planar branching-program characterization.
- The authors note an intriguing linkage between graph genus and algebraic solvability and leave its deeper explanation open.They also report that quasipolynomial-size ACC0 admits equivalent polylogarithmic-genus circuit and polylogarithmic-genus nondeterministic branching-program characterizations in the nonuniform setting.