J. Pich

Efficient Adversaries

This work considers a generalization of prover-adversary games to many standard proof systems and shows that some of the major proof complexity lower bounds are constructive in the sense that they yield efficient algorithms computing winning strategies of adversaries in the generalized games.