Robert Robere
Department of Computer Science
University of Toronto

 

Approximate Monotone Complexity of Boolean Functions

 

Department of Computer Science
Thursday, August 1, 2013, 1:00 p.m., Room EN-2022

---

Abstract

An approximate computation of a boolean function f: {0,1}n 6 {0,1} by a computational model M is a computation in which M computesf correctly on the majority of the inputs, rather than all of the inputs (that is, M is allowed to error on some fraction 0 < 1/2 of the inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many subareas of complexity theory, such as cryptography and derandomization.

In this talk, we present recent work on how to obtain exponential lower bounds on the size of approximate monotone circuits computing a particular boolean function. Our lower bounds tolerate errors that are asymptotically the best possible for approximate monotone circuits. As a corollary, we establish that for every i, there are functions that can be computed with no error by depth O(logi+1 n) monotone circuits, but that cannot be computed without large error by depth O(log n) monotone i circuits. In particular this separates the monotone NC hierarchy and separates monotone P from monotone NC in the case where the computations involved are allowed large errors. Previously, these separations were only known in the case of exact monotone computations. We give an overview of our results and, time permitting, discuss some of the techniques involved.

The work presented here is joint with Stephen Cook, Toniann Pitassi and Yuval Filmus.