pipette
ENEnglish

Constant-Probability Witness Isolation Implies

Sebastian Ben Daniel

Preprint

En palabras de los autores

Valiant and Vazirani isolate a satisfying assignment of a circuit with probability . Dell, Kabanets, van Melkebeek, and Watanabe showed that success above implies and asked about the range in between. We show that every positive constant already implies the collapse: if a randomized nonuniform polynomial-size pruning procedure succeeds with probability on affine circuit inputs with at most satisfying assignments, then . Success on affine inputs with at most satisfying assignments suffices, where is the description length, and on inputs with one or two satisfying assignments the threshold drops to . No cryptographic assumption is used, and the procedure may read the entire circuit. The proof compiles a pool of circuits into one circuit whose satisfying assignments are indexed by tags in . Each member is assigned an affine region of tag space, and if one member is unsatisfiable, the satisfying set shrinks to that member's region. Because regions may overlap and have different dimensions, the collapse reduces to a combinatorial bound: no set of tags meets more than a fraction of an equally weighted family of affine subspaces of all dimensions below in exactly one point. This regional counting cannot go below order . The range between , achieved by affine hashing, and remains open.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 25 de septiembre. arXiv. Preprint, todavía sin revisión por pares.