Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Robert Robere:

TR16-188 | 21st November 2016
Toniann Pitassi, Robert Robere

Strongly Exponential Lower Bounds for Monotone Computation

For a universal constant $\alpha > 0$, we prove size lower bounds of $2^{\alpha N}$ for computing an explicit monotone function in NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where $N$ is the number of variables of the ... more >>>

TR13-054 | 4th April 2013
Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

Average Case Lower Bounds for Monotone Switching Networks

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint