On span programs
Mauricio Karchmer, Avi Wigderson · 2002
A linear algebraic model of computation the span program, is introduced, and several upper and lower bounds on it are proved. These results yield applications in complexity and cryptography. The proof of the main connection, between span programs and counting branching programs, uses a variant of Razborov's general approximation method.>