The Setting
A solver input consists of a box , with corners in for the vertex set of the game, , and reference width , and of budgets : positive rational support weights and budgets . On such an input the randomized subroutine Solve returns a vector of , and the randomized subroutine Orient returns an orientation for , which chooses or and carries a list of exceptional sets. Procedure 4.1 (Repeated comparison), called Ask, and Procedure 4.2 (Repeated orientation), called OrientPlus, amplify the two subroutines by repetition: each runs its subroutine for trials, the global trial parameter, and combines the answers into one.
The library writes both as recursive procedures on raw data, that is, on data encoded as bit strings and unary counters, executed step by step by a machine with an explicit call stack, and states each step together with what the combined raw answer represents.
Raw Data, Medians and Majorities
Raw data are written in bits: a count as a unary counter, a counter of length standing for , an integer as a binary word, and a vector of as a raw vector, the list of the words of its coordinates. We write when the raw datum represents the object . A raw solver input is a raw box , whose parts include a raw lower corner with entries, together with raw budgets . Lists are written , with the empty list, the list with put in front, and the concatenation of in this order. A list of raw data represents a list of objects when the two lists have the same length and each entry represents the entry in the same place.
A raw orientation is a pair of a bit and a list of bit masks, each a bit string standing for one exceptional set.✦ A raw orientation represents an orientation for when is true exactly when chooses and , the th mask representing the th exceptional set.✦
The raw median of a list of raw vectors, with respect to a raw box with lower corner , is when the list is empty, and otherwise the raw vector whose th entry is the median of the th entries , where the median of numbers is the entry in place , counting from , of their list sorted in increasing order: (1) For vectors of a box , their median is the lower corner when , and otherwise the coordinatewise median, the vector whose th coordinate is the median of ; it is again a vector of .
The raw majority of a list of raw orientations is the raw orientation whose bit is true exactly when more than half of the bits are true, and whose masks are those of all entries, concatenated in order: (2)✦ For orientations for , their combined orientation is the orientation for that chooses exactly when , and whose list of exceptional sets is , the lists of all the concatenated in order.
The Machine
A frame of the machine is a record of registers: a raw solver input , a unary counter , two raw vectors, a list of raw vectors, a raw orientation and a list of raw orientations; a register that a step does not set is empty.✦ A state of the machine is a current frame above a stack of suspended frames, a list with its top first, so that is with the frame pushed on top.✦ Every frame carries a label. The current frame is either labelled with the procedure it runs on its registers, written as that procedure applied to them, or is returning a value in a register, written ; a suspended frame is labelled with the step that resumes it.
A step maps a state, read together with the environment, to the next state; we write when the step takes the state to the state . The environment is the arena of the game written as raw data, with four unary counters, the trial count among them.✦ The label of the current frame chooses the step, and when that frame is returning, the label of the frame on top of the stack does.
The Claim
Definition 1 (Procedures 4.1 and 4.2). Let be a raw solver input, a unary counter and a stack. The procedure Ask on runs a procedure on with counter , below a frame that waits for its result: (3)✦ The procedure returns the empty list when , and otherwise runs Solve on below a frame that keeps the remaining count: (4)✦ A raw vector returned to is kept in a frame while the remaining trials run, (5)✦ and is put in front of their list when it returns: (6)✦ A list returned to is replaced by its raw median (1) with respect to : (7)✦ If for a box of reference width in dimension , and for vectors of , then (8)✦
The procedure OrientPlus follows the same scheme, with a procedure and frames , and , running Orient in place of Solve and collecting raw orientations in a list , which it replaces by its raw majority (2): (9)✦ (10)✦ (11)✦ (12)✦ (13)✦ If represents a list of orientations for budgets , then (14)✦ (15)✦ and (16)✦
In the paper, the result reads: for its given solver input, Ask runs independent copies of Solve and returns their coordinatewise median, and for its given orientation input, OrientPlus runs independent copies of Orient and returns the majority choice in together with the concatenation of all exceptional-set lists in trial order, retaining minority-trial lists and duplicate entries.
What Is Checked
The steps (3) to (7) and (9) to (13) are stated over states of the machine, with frames holding a raw solver input, a unary counter and raw vectors or raw orientations, and with read from the environment; (8) and (14) to (16) are stated over a box of reference width in dimension with a list of its vectors, and over budgets with a list of orientations for , all given with raw data that represent them.