The Setting
In a dependency circuit, the -bit value of each node is fixed by the values of a head child and of further children through an identity over a prime field, in which a few guessed bits are summed out. Lemma 5 is about evaluating such a circuit by recursion in little space. The evaluator holds three registers of field vectors, shared by all levels of the recursion, and answers requests: a request at a node asks it to add a multiple of the value of , written as a field vector with an extra coordinate , to one register and to leave the other two as they were. The question is whether every request is answered whatever the registers hold at the start, and with how large a stack.
Dependency Circuits
A dependency circuit of width with children per node has as nodes the numbers below some , some of them flagged as base nodes. Each node has a head child , children for , a number of guess bits, a first value , which is the value prescribed at a base node, and a semantic value ; the guesses at are the numbers . The outer degree of is ✦, and its modulus is the largest prime with ✦; scalars are elements of the field ✦. The two local rules of , read in , are the proposal at a coordinate , a guess and a head value , and the allowance test , which also takes a child index and a child value .
A vector is a sequence of elements of . The augmented vector of a number has the binary digits of , least significant first, in coordinates to , a in coordinate and zeros beyond✦; the augmented value of a node is ✦. For a -bit word , the Boolean basis polynomial is the product over of where bit of is and of where it is .✦ The word extensions of the two rules at vectors and are (1)
The circuit is good when every node has and , every base node has its first value as semantic value, and every other node obeys the identity rule (2)✦
The price of guesses is , where is the bit length of a number .✦ A meter for is an assignment of a number of coins to each node that pays for every step down from a node that is not a base node, at the price of no guesses to the head child and at the price of the guess bits of to each child: (3)✦
Flow Machines
A flow machine consists of a set of states, whose elements are written , and a set of frames, whose elements are written , each with a code, a number written or , together with an action, which takes a state and a frame to a new state and a move.✦ A move finishes, written , continues with a frame , written , or calls a child frame to be followed by a return frame , written .✦ The fee of a frame is (4)✦
Execution within a budget , which bounds the total fee of the return frames suspended at one time, is defined inductively. The machine started on a state in a frame executes within to a state , written , when its action at finishes with state ; when the action continues with a state and a frame such that ; or when the action calls with return frame from a state , and and for a budget with .✦
The Evaluator
Over a prime , a pool is an assignment of a vector to each of three registers, numbered modulo : (5)✦ For a register and a vector , is the pool with added to register and the other two unchanged✦, and is the unit vector with in coordinate . A request at a node of is a triple of , a scalar and a target register ✦; its head register is ✦, its array register is ✦, its reverse is ✦, and its result on a pool is the pool (6)✦ For a request and a scale , the request on the head child of with scale is the request at the head child of with scalar , read in , and target the head register of . For a request , an index and a scale , the request on child array of with scale is the request at the child of with scalar , read in , and target the array register of .
A frame of the evaluator of consists of a request , a program counter among , , , , , and , counters , , , and , and two scalars and .✦ The entry frame of has all counters and scalars zero✦; for the other program counters, , , , , and denote the frame with the request of the frame at which the step is taken, the entries shown and zeros elsewhere. With the interpolation weight of degree , the step of the evaluator on a pool , at a frame with request , is given by the program counter: (7)✦ where .
The evaluator of is the flow machine whose states are the pools over the modulus of , whose frames are those above and whose action is the step (7).✦ The pairing of numbers and is the number whose binary digits, least significant first, are those of , each preceded by a , then a , then those of ; longer tuples are nested to the right.✦ The codes of the evaluator use it: a pool has the code ✦, with the base- packing of the first coordinates of a vector, and a frame has the code ✦, with the number of its program counter, from for to for in the order listed✦, and scalars read as numbers below .
A node of is solved for an assignment of coins when every request at , started in its entry frame on any pool , executes within the budget to its result .✦
Space Bounds
Fix an index set , public inputs , words over an alphabet , and space bounds . A family of numbers is computable from a family in space , written , when one fixed stack machine, with finitely many states, read-only heads and stacks of bits, at every index reads as public input and turns a stack holding the bits of into one holding the bits of , least significant first, within bits for a constant independent of .✦ A family is linear in when for one constant and every ✦, and it fits in when its bit lengths are linear in ✦. For a map , computation along is computation in which the instance has public input and space bound .✦
A family of dependency circuits with descriptions , numbers that describe the circuits , is ready for when its widths and its numbers of children per node are computable from in space , its numbers of nodes and the numbers of contents of a register fit in , and its local structure is computable along every map : whenever the descriptions and nodes of the circuits are computable in space , so are the base flag, the number of guess bits, the head child and the first value of these nodes, their children at computable child indices, and their proposals and allowance tests at computable arguments in range.✦
A family of flow machines is uniform in space for descriptions when its actions are computable in space over the family of all triples of an index, a state and a frame of , with public input and bound : , where the action at yields the state and a move with tag , to finish, to continue and to call, and , are the codes of the frames the move names, in order, with in place of a missing one.✦
The Claim
Theorem 1. Let be a good dependency circuit with a meter . Then every node of is solved for : for every scalar , every target register and every pool , the evaluator of satisfies (8)✦ Let further , for , be good dependency circuits forming a family ready for with descriptions , let be a meter for , and let be nodes of with whose budgets are linear in . Then the semantic values of these nodes are computable in space : (9)✦
In the paper, the result reads: under these assumptions the augmented value of is computable in work space, and more strongly a pool of exactly registers in supports the request adding to register and restoring every other register, from every initial assignment of the pool, within that space including pool and stack, with the paper’s weight of , a parameter of the paper, its field and the simulated time.
What Is Checked
The claim is stated over good dependency circuits with their meters, the pools (5), requests and their results (6), the evaluator with its step (7), and execution within a budget charged by the fee (4); its second part adds families of circuits ready for a space bound and computation in space .
For a family of flow machines uniform in space for descriptions , and executions within budgets linear in , the final states are computable in space from the starts: (10)✦
The guess sum of a node at a vector is the vector whose coordinates are (11)✦ and whose further coordinates are zero. For a request at a node of a good circuit that is not a base node, and every pool , the weighted sum of guess sums along the line through the head register in the direction of the augmented value of the head child is the change the request asks for: (12)✦
A node with solved children, for a meter , is a node that is not a base node and whose head child and children , , are solved for .✦ At such a node of a good circuit, every request is answered within the budget of the node from every pool : (13)✦