The Setting
Take a mean-payoff game on a vertex set of vertices, given by an input string of length , and the randomized solver for its zero-threshold winning set, run on a Turing machine with a random tape. The run has two phases. The preparation reads and fixes the parameters, among them the number of samples, a power of two, and the number of steps, where . The post phase spends fair bits on each step, which give a uniform sample index in , runs the solver one step at a time as a stack machine, and writes out the answer. The question is how large the stored numbers, the stored vectors and sets, and the stack become over that many steps, and what each phase costs.
The library bounds the growth in one step and over a run, the size of every state reached, and the cost of the two phases.
The Stack Machine
A register pack is a record of eight registers, stored as bit strings and unary counters: the budgets, holding the positive rational support weights and the budgets ; a box, given by its reference width and its corners and ; a counter; two vectors and ; a list of vectors; an orientation; and a list of orientations.✦ An orientation is a choice of or together with a list of masks, each mask a set of vertices written as a bit string and also called an exception.✦ A stack cell is a pair of a tag, a natural number written as a unary counter, and a register pack.✦
A machine state is a pair of a current cell, which holds the job being called, a task of the solver, or the value being returned, and a stack of cells holding the pending frames, the suspended calls that await the value of a job.✦ The height of a machine state is the number of cells on its stack. The top tag of a machine state is the largest tag among its current cell and the cells of its stack.
An environment is a tuple of the arena , the game graph with its transformed weights , where is the weight of the edge , and four counters: the sample exponent , the number of samples, the number of trials and the step budget of the basic solver, the solver that the machine calls on boxes of small width.✦ A control accumulator is a pair of an environment and a machine state.✦
A step of the machine takes an environment , a sample index and a state to the state , chosen by the tag of the current cell.✦ The tags name the jobs solve, ask, trials, update, centers, orient, orientation trials, orientation plus, tighten and reweight; a job either returns a pack, as a current cell with the return tag , or pushes a frame onto the stack and calls another job. Under any other tag the step resumes the frame on top of the stack, chosen by its tag among trials head, vector cons, median, first center, second center, centers head, orientation loop, orientation tail, orientation head, orientation cons, combine, first tightening, second tightening, floor and ceiling box passing, solve tight, solve oriented, reweight head, solve reweighted, cap high, cap low and include inner; on an empty stack the state stays as it is.✦
The trials job, started with a counter on a budget and a box, runs the solve job on that budget and box times in turn and returns the list of the vectors obtained; with it returns the empty list.✦ The ask job on a budget and a box runs the trials job with trials on them and returns the median of the resulting vectors, taken coordinatewise in the box.✦
The basic solver, run on the arena with step budget , is called by the solve job on boxes of width at most . The update job and the first center frame call the ask job on a box narrowed about a vector to width , and the orientation loop uses the sample index to pick one of its centers, about which it may call the orient job on a box of width . Trials are amplified by medians and majorities: the median frame returns the coordinatewise median of the trial vectors, and the combine frame returns the orientation that chooses exactly when a strict majority of the trial orientations do, carrying all their masks.
The update job on a box and a vector asks on the box narrowed about , first with the budget reduced in and then with the budget reduced in , and returns the average of the two vectors obtained, clipped to the box. The centers job, started with a counter and a vector on a budget and a box, applies the update job times in turn, starting from , and returns the list of the vectors obtained, the centers.✦
The grid width of a box of width is .✦ The floor and the ceiling of a box are its lower corner and its upper corner . The tightening steps test whether a returned vector moves the floor or the ceiling of a box relative to . The cap width of a box of width is .✦
For a box with midpoint and width , a scale and a vector , the positive displacement set is the set of coordinates with ✦, and the negative displacement set is the set of coordinates with ✦. At the -th center, with the sample count as scale, the orientation loop forms both sets. If, for the support weights, the positive set has measure above one half, it returns the orientation choosing with the complement of that set as exception; otherwise, if the negative set has measure above one half, it returns the orientation choosing with the complement of that set as exception; otherwise it calls the orient job at the center picked by the sample index✦, and the orientation tail frame extends the orientation returned by the two sets✦.
The base orientation of support weights , a box with lower corner and width , and a vector is formed from the set of coordinates with : if has measure above one half for the support weights it chooses with the complement of as exception, and otherwise it chooses with as exception.✦ The orient job returns it on a box of width at most , taking for the vector of the basic solver on that box.✦
On a box of width above , the orient job computes the centers of the box with the centers job, with counter and the midpoint of the box as first center, and then continues in the orientation loop.✦ The orientation trials job, started with a counter on a budget and a box, runs the orient job on them times in turn and returns the list of the orientations obtained; with it returns the empty list.✦
The tighten job on a budget and a box asks on the box with the budget reduced in .✦ If the vector returned moves the floor of the box relative to , it moves the floor to and tightens again; otherwise it asks on the same box with the budget reduced in ✦, and if the vector returned moves the ceiling relative to , it moves the ceiling to that vector and tightens again✦. When neither the floor nor the ceiling moves, it returns the box.✦
After tightening, the solve job calls the orientation plus job on the budget and the tightened box, then the reweight job with the orientation returned. The reweight job takes the masks of the orientation one at a time, asks on the box with the budget reweighted by that mask according to the choice or , and returns the list of vectors obtained.✦ The solve job then calls itself on the box capped high for the choice and capped low for the choice , by the cap width✦, and the cap high and cap low frames take the coordinatewise minimum, respectively maximum, of the vector returned and the vectors of that list.
The solve job on a budget and a box first tests the budget: if it is small, it returns the vector prescribed for a small budget on the box; otherwise, on a box of width at most it returns the vector of the basic solver, and on a wider box it tightens the box and continues as follows.✦
The control loop runs one step for each index of a list of sample indices: from an accumulator it passes through the accumulators , where (1)✦
Small States and Their Mass
Fix natural numbers , and . The size of a string, a number, a state or an input is the size of its encoding. A register pack is -small when its budgets, its box, its two vectors and every vector of its list have at most entries and every number in them has size at most , its counter has length at most , and every mask of its orientation and of its list of orientations has at most entries.✦ A stack of cells is -small when the pack of each of its cells is✦, and a machine state is -small when the pack of its current cell and its stack are; is the set of -small machine states.✦
The mass of a register pack with list of vectors , orientation and list of orientations is the natural number (2)✦ where is the number of masks of an orientation . The mass of a machine state is the sum of the masses of the packs of its current cell and of the cells on its stack.✦
The Two Phases
The preparation is a machine with step bound on the input string . It computes by repeated doubling of a single unit, parses as a game and sets up the root: the top width , the number equal to the binary length of plus one, the sample exponent with its power of two✦, ✦, ✦, and the initial state, which calls the solve job on the box with every entry of the support weights and equal to and the budgets , over an empty stack. It returns the counter together with the chunk length , the bound , the number of chunks into which the post phase cuts its random digits, the width and the initial accumulator.✦ The resource of an input string is the number (3)✦
An input of the post phase is a string of random digits together with the counter, the chunk length, the bound , the number of chunks, the width and the initial accumulator that the preparation returns.✦ The sampler cuts the digits into chunks: its state holds the chunk length and the bound, the samples drawn so far and the digits not yet read✦, and each of its steps splits off the next chunk, reverses its digits, reads them as a number and reduces it below . The post phase runs the control loop from the initial accumulator over these sample indices and writes out the bit string marking the vertices whose coordinate , in the vector of the final current cell, exceeds half of .✦ The cost of the post phase on an input is (4)✦ where is the step bound of the machine that runs the post phase on and is the cost of writing out its output bits.
The Claim
Theorem 1. Let be an environment, a sample index and a machine state. Then (5)✦ Let , , , and be natural numbers such that and , every number of the arena has size at most , and . If is -small, then (6)✦ If moreover is a natural number with and , the control loop from over any list of sample indices ends in a state with (7)✦ For any list of sample indices and any , the accumulator reached after the first steps of the control loop from satisfies (8)✦ If is -small and is at least each of , , , , and , then (9)✦ There is a polynomial such that every input string satisfies (10)✦ and there are constants and such that every input of the post phase satisfies (11)✦
In the paper, the result reads: every endpoint, center and returned coordinate lies in , the reachable support weights are and the reachable budgets with exponents and summing to at most , so that every number has bits and the local work attached to one invocation of the solver is polynomial, where and are the paper’s parameters.
What Is Checked
The claim is stated over the stack machine of the solver: register packs, orientations, cells and machine states with their height and tags, environments and accumulators, the step with its ten jobs and twenty-two frames, and the control loop (1); over -small packs, stacks and states and the mass (2); and over the two phases, the preparation with its resource (3) and the post phase with its sampler and its cost (4).
Beyond the claim, the library proves two size bounds inside the post phase. After any number of its steps on a counter, the state of the sampler has size at most , where is the size of its starting state together with the counter✦; and the coordinatewise minimum or maximum that the cap high and cap low frames take of a vector and the first vectors of a list has size at most , where is the size of the vector and the list.