All reports by Author Stephen A. Cook:

__
TR16-064
| 19th April 2016
__

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman#### Exponential Lower Bounds for Monotone Span Programs

__
TR13-054
| 4th April 2013
__

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook#### Average Case Lower Bounds for Monotone Switching Networks

Revisions: 1

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

An approximate computation of a Boolean function by a circuit or switching network is a computation which computes the function correctly on the majority of the inputs (rather than on all inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many subareas ... more >>>