pipette
ESEspañol

Near-Inverse-Linear Barriers for Explicit Affine Witness Isolation

Sebastian Ben Daniel

Preprint

In the authors' words

We study randomized nonuniform polynomial-size transformations that output explicit binary affine filters for circuit inputs whose nonempty satisfying sets are affine. The filter may depend on the entire input description; no affine basis is supplied. For every fixed , a worst-case singleton success guarantee , where is the witness arity, implies . More generally, any success guarantee yields satisfiability circuits of size for length- descriptions with at most witness variables, hence subexponential in when . Conversely, SAT search-to-decision gives deterministic perfect isolation, making polynomial-resource fixed-exponent strong affine isolation equivalent to . For explicit unions of at most affine components, success implies the same collapse whenever and . The inverse-linear endpoint is not claimed.

Main resultLimitation the authors admit

Appeared: Friday, October 9. arXiv. Preprint, not yet peer-reviewed.