a boolean function f on n variables can be written as both a DNF formula
where each term is of length at most k and a CNF formula where each clause
is of length at most k.
Show that for any input x of length n, f(x) can be evaluated by only looking
at O(k^2) inputs bits of x. (Assume you already know DNF and CNF mentioned
above)
Any idea? Thanks
