claimroutineinferred_dep
Explicit polynomial-size occurrence list
Rationalized instance is an explicit polynomial-size occurrence list
shows the output is computable in polynomial time
Claim·§8.1 Constraint satisfaction and Vertex Cover·inside corGap hardness from a fixed SDP integrality gap
Statement (paper)
The occurrence list on the variable set , with one occurrence for each , and ordered neighbor tuple in , where the occurrence applies the -predicate prescribed by to the resulting query variables and has weight , has nonnegative rational weights summing to one. It consists of occurrences on variables, and it can be written down in time polynomial in the size of the input, with each weight of polynomial binary length.
In plain English
The rationalized instance is given by an explicit list of occurrences on the variables , one for each , vertex and ordered tuple of neighbors in . Its weights are nonnegative rationals summing to one, it has occurrences, and it can be written down in polynomial time with polynomially long weights.
Why it's here
This shows the reduction's output is a genuine, efficiently computable -instance. It uses the rational table from the previous claim, which makes the weights rational with constant-size description, and the constant left degree from the Unique Games lemma, which keeps the number of neighbor tuples polynomial. The later claims can then compare this instance's value to the original verifier's value, and the reduction is polynomial-time.
Classified routine:
Straightforward bookkeeping: summing the weights over the |L_Φ|h^{a(s)} neighbor tuples per s recovers the rational law θ̂, and polynomial size follows from the constant left degree h (lem-simple-strong-left) and the constant-size rational table θ̂ (previous claim).