A purely logical characterization of circuit uniformity
Steven Lindell · 2003
Utilizing the connection between uniform constant-depth circuits and first-order logic with numerical predicates, the author provides a purely logical characterization of uniformity based on the intrinsic properties of these predicates. By requiring a numerical predicate R to satisfy a natural extensibility condition-that it can be translated to a polynomially magnified domain based on tuple constructions-he shows that R must already be elementarily definable from>