Topology restricts power of small efficient computer circuits
Topology inside NC$^1$
Computational Complexity
Summary
This work explores how the shape or 'layout' of computer circuits affects what they can compute efficiently. The authors show that certain complex circuits constrained to a limited 'width' and organized with a shape close to flat (planar or with low 'genus') can only solve problems within a specific class called ACC0. Extending this, they find that allowing slightly more complex shapes (like thickness two) enables solving a larger class called NC1. This helps us understand the limits and possibilities for designing circuits with certain physical or logical layout restrictions.
What this means in practice
- •For hardware designers: Know that restricting circuit layouts to planar or low-genus graphs limits computation to ACC0, guiding design choices for efficient hardware.
- •For parallel computing engineers: Use circuits with thickness two layouts to efficiently realize computations within NC1, optimizing parallel algorithm implementations.
A theory result. No direct application yet.
Authors
Eric Allender, Samir Datta, Arsenii Karnaukhov, Sambuddha Roy, Alexander Shekhovstov
Abstract
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$.