Approximating Boolean Functions
You can fool all the functions some of the time, and some of the functions all the time, but you cannot fool all the functions all the time, or even most of the time.
Eric Blais and Li-Yang Tan are both complexity theorists. Eric just finished his PhD and is currently a Simons Postdoctoral Fellow at MIT, while Li-Yang is about to finish his doctorate at Columbia.
Today Ken and I wish to talk about their recent paper on approximations to Boolean functions.
This paper entitled “Approximating Boolean functions with depth-2 circuits” just appeared at CCC 2013. We both were unable to attend the meeting, but in reading the paper I am quite excited about their result. I think it could have many interesting applications.
A circuit with -many wires can be described as a graph by a binary string of length by listing the gates in order of -sized labels and giving the targets of each wire out of each gate. Since there are Boolean functions on variables, one for each binary string of length , it follows that many require size such that , so . If there are arguments such that , we can create a circuit in disjunctive normal form (DNF) by using a gadget of up to NOT and AND gates to distinguish each such , and running a wire from each gadget to a big OR with inputs. This has size about , which becomes in the case of the parity function. The issue in their paper is whether strictly exponential bounds can be beaten when the function need only be computed approximately.
You may skip this history if you like. In ancient times these functions were called switching functions—indeed even FOCS bore the name “Switching and Automata Theory.” Later they became Boolean functions. I am not sure when things switched—OK, bad pun.
The reason for the initial name was they were studied for their importance to the phone company, when there was one phone company. Such functions were used to control phone calls: even though in those days phone lines themselves were analog, the switching of calls was digital. You either connected Alice to Bob or Alice to Eve or Alice to …, even if their conversation was really just over a wire that carried their voice as an analog signal.
In these early times the idea of ““—as in people, gates, variables…—had not been invented yet. By this I mean that the theoretical interest of researchers was occupied even by Boolean—I mean switching—functions of a few variables. For example, Donald Davies studied the cost of implementing three-variable functions in his paper, Switching Functions of Three Variables in 1957. Such results were non-trivial, in some ways harder than -notation style work of today, owing to the use of ingenious special-purpose designs and encodings.
Davies worked at the National Physical Laboratory in the 1940′s, and is said to have “spotted mistakes in Turing’s seminal 1936 paper ‘On Computable Numbers,’ much to Turing’s annoyance.” Rest assured that Alan Turing’s main theorem on the halting problem is just fine.
Let’s leave switching functions, and move on to -variable Boolean functions and the work of Blais and Tan.
The General Approximation Result
Suppose that you wish to compute a Boolean function, but it is very complex in some measure. A natural idea is to try to approximate it. Since the function returns either or it seems that an approximation in the usual sense is useless. What would it mean to answer ? Actually as I write this it could be a type of confidence level. If you say it means that you are pretty sure that the answer is but do not completely rule out that the answer is . Hmmmm. This is not unlike what the weather forecasters do—tomorrow has a chance of rain. Perhaps another day we should discuss this type of approximation.
Well Blais and Tan use another notion of approximation—a quite standard one. Suppose that is a Boolean function. For some small say that the function -approximates provided
for all but an fraction of the inputs. If the function has inputs, then this means that it must be right on
of the inputs. Note that if uses the first sense of approximation with real values above, then the function obtained by rounding may well meet this condition.
Clearly some functions are easy to approximate. The -ary AND function is trivial: just say no all the time and you are right for all but one input. Also it would seem clear that more interesting functions might be quite a bit harder to approximate. The parity function comes to mind—a function that is impossible to compute exactly without reading all the inputs. But there is a surprise here in Blais and Tan’s paper, which I will explain shortly. Their first main result is:
Theorem 1 For every there is a constant such that for all n and each n-ary Boolean function , there is a DNF of size at most that ε-approximates .
A little note on asymptotic notation: The way they actually state their theorem is,
“Every Boolean function can be -approximated by a DNF of size .”
One needs a certain skill in translating asymptotics rigorously. Some things are always clear: is the number of variables regarded as the input size, the base of doesn’t matter since it’s a constant that gets absorbed into the “” (but is base 2 by default), and the constant in the depends on but not on . What’s less clear is that asymptotics are being used over all but “Boolean function” means just one . The statement could mean a function defined on all of by a sequence of Boolean functions for each , and then the constant in the could depend on the chosen sequence, but it doesn’t—the correct version is as above. Their proof uses , but the statement is valid for all ; for —or whenever —their upper bounds lose their power and are met by their lower bounds which then become .
The cool point in any event is that for any fixed , the quantity goes to 0 with , so approximation beats strictly exponential size.
Width and Fooling
The part of their results Ken and I like best, however, has to do with the idea of the width of a DNF. This is defined to be the maximum arity of an AND gate in any of the DNF terms, and intuitively means the number of input variables that get read in any one place. For the parity example above the width is which is the maximum of course. But for the majority function, it suffices to have an AND gate of size for each -subset of the variables, so the width is about .
Now especially with parity, it is hard to conceive being able to compute these functions with DNFs of any lower width, or even approximate them. If a term leaves one variable unread, for parity it means the answer could be anything, fifty-fifty, and it seems that term must be useless. But the magic combination of approximation, the probabilistic method, Fourier analysis, and covering-code constructions gives their other main theorems:
Theorem 2 For every there is a constant such that for all -ary Boolean functions , there is a DNF of width at most that -approximates .
In the case of parity, we can build with and of size . These bounds are nearly tight, and moreover the construction gives one-sided error: for all of odd parity.
Ken and I would have had the opposite expectation, that small-width DNFs would be so weak that they can be collectively “fooled.” In cryptographic complexity, for a function to fool a class of weaker functions means that no can gain any advantage in computing values of —that from the perspective of functions in , the function looks random, unpredictable, and importantly is not approximable in Blais and Tan’s sense. But they prove the opposite: every Boolean function can be approximated by DNF’s of smaller width—and for parity still sub-exponential size. Hence “all the smaller-width DNF’s cannot be fooled most of the time.” At least we think Abraham Lincoln would have agreed.
They have other results for Boolean functions that are monotone up-or-down in each of the variables, called unate functions, and polynomial threshold functions which have the form for some real-valued polynomial . Here is a table of upper and lower bounds from their paper:
The paper includes full details of proofs, which are interesting for their mix of randomization, analysis, and covering-code constructions.
What other applications can be found for their constructions, and for small width?
Yesterday, today, and tomorrow are collectively the 150th anniversary of the Battle of Gettysburg. Here is the NY Times story on 11/20/63 covering the speech Lincoln had given at Gettysburg the previous day.