The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data
Brynmor Chapman, Ryan Williams · 2015
We revisit a natural zero-sum game from several prior works. A circuit player, armed with a collection of Boolean circuits, wants to compute a function $f$ with one (or some) of its circuits. An input player has a collection of inputs, and wants to find one (or some) inputs on which the circuit player cannot compute f. Several results are known on the existence of small-support strategies for zero-sum games, in particular the above circuit-input game. We give two new applications of these classical results to circuit complexity: