The Setting
To simulate time-bounded computation in less space, one cuts the tape into blocks and evaluates the resulting computation graph: each vertex stands for a word of bits, such as the contents of one block at one moment, and the word at a vertex is fixed by the words at a few vertices below it. An evaluator finds the word at a vertex by recursion, recomputing the words below it instead of storing them.
The circuits of this item factor the rule at a vertex through arithmetic in a prime field. One child, the head, is singled out. The rule at a vertex is a sum over guesses of a selector on the head’s word times tests on the head and one child each. The cost of the recursion is measured by a potential, the meter: coins on the vertices, at least a fixed price more at a vertex than at its head, and at least a price growing with the guess length more than at each child. A family of circuits, one for each input, is ready when its parts are computable in a space bound .
Words as Vectors Over a Prime Field
For a prime , is the field of integers modulo ✦, and a coordinate vector over is a sequence of elements of ✦. The prime modulus chosen for a natural number is the largest prime with .✦
A -bit word is a natural number , read through its binary digits , least significant first. The bit length of a natural number is the number of its binary digits, with . The augmentation of a natural number at width is the coordinate vector given by (1)✦
The Boolean basis polynomial of a -bit word is the function on coordinate vectors (2)✦ and the word extension of a table of elements of indexed by -bit words is the function on coordinate vectors (3)✦ The pair extension of a table indexed by pairs of -bit words is the function on pairs of coordinate vectors that extends one argument at a time: (4)
Computing in Space
A stack machine is a finite-state machine with read-only heads on its inputs whose work storage is a finite set of stacks of bits.✦ For a family of words over an alphabet and families , , of natural numbers, all indexed by a set , is computable from in space on public inputs , written , when one fixed stack machine, at every index , reads as its public input and turns a stack holding the binary digits of into a stack holding those of , least significant first, within work bits, for a constant independent of .✦
For a map , computability after the change of index is : at each the public input is and the space bound is .✦
The Definition
Definition 1. A dependency circuit of width and fan-in on the vertices consists of a set of base vertices and, at every vertex , a head , children , a guess length , a base word , a semantic value , selector values and test values , for all natural numbers , , , , : (5)✦ The field of is for the prime chosen for the outer degree of , and the selector and test values of are read in . The augmented value of a vertex is (6)✦ and the word extension of the selector and the pair extension of the tests are, at coordinate vectors and over , (7)✦ (8)✦
The circuit is good when every semantic value is a -bit word, every guess length is at most , every base vertex has , and every vertex that is not a base vertex obeys the factored rule at each coordinate , in : (9)✦
The price of a guess length is (10)✦ and a meter for is a function from the vertices to the natural numbers, the coins, such that every vertex that is not a base vertex satisfies, for each , (11)✦
A family of dependency circuits, with widths , fan-ins , vertex counts and primes , is ready for public inputs , a space bound and parameters , families indexed by , when, for a constant independent of , (12)✦ and when the family is navigable in space : for every map and family over , whenever and a choice of a vertex of at each are computable from after the change of index , so are, with and standing for and , the bit saying whether is a base vertex, , and ; the child for every such computable with ; the selector value for such computable , , with , and ; and the test value for such computable , , , , under the same bounds with and .
In the paper, the result reads: a finite acyclic graph on polynomially many word identifiers with semantic values has base words, ordinary vertices with for , and history vertices with a distinguished child , children , a guess length and the identity in characteristic two, where edges to and ordinary edges weigh , edges to the weigh , is the maximal weight of a path from , and navigation and the local functions are uniformly computable.
What Is Checked
The definitions are stated over the field of the prime chosen for the outer degree , the coordinate vectors over it with the augmentation (1) and the extensions (3) and (4), and computability in space by stack machines.