A Free Lunch Theorem For Circuit Complexity

A guest post from Dieter van Melkebeek

This week, about 50 computer scientists gather at Schloss Dagstuhl for a seminar on "Complexity of Boolean Functions." The setup follows a long tradition that started back in 1944 at Dagstuhl's mathematical sister institution in Oberwolfach: a flexible program of talks, ample time for discussion, and Deutsche Gruendlichkeit in a wonderful setting.

I'll highlight an aspect of roughly one talk per day. Given the wide variety of topics, the selection is idiosyncratic rather than representative. For a full list of the talks, check out the seminar web page.

On Monday, Philipp Woelfel discussed time-space tradeoffs for integer multiplication. Every program computing the product of two n-bit integers in time T and space S has to satisfy TS = Ω(n²), and this lower bound is tight. One may expect that the same time-space tradeoff holds if we're only interested in the i-th bit of the product, where i is part of the input. However, Philipp showed a randomized program (with polynomially small error) that does the job using only O(n log n) time and O(log n) space, for a product TS of O(n log² n). It remains open whether the TS = Ω(n²) lower bound for the simpler problem holds in the deterministic setting.

I stole the title for this weblog entry from Peter Bro Miltersen. Right before lunch on Monday, he presented his "free lunch theorem": Lower bounds for circuits that consist of a gate C applied to symmetric functions of ANDs (type I) imply lower bounds for circuits that consist of a gate C applied to symmetric functions of AC⁰ functions (type II). The proof outline goes as follows. Consider a circuit of type II. By the switching lemma, hitting it with a random restriction transforms each of the AC⁰ functions into small decision trees, each of which can be written as a small OR of small ANDs. For any given decision tree, at most one of its ANDs can be true. It follows that a symmetric function of decision trees is a symmetric function of all the ANDs involved in these decision trees. This transformation gives us a circuit of type I that isn't much larger than the original circuit.

Part of Tuesday was devoted to quantum computing. Andy Yao presented an approach to unify and generalize the known quantum lower bounds for (i) locating an item in a sorted list of n elements and (ii) sorting a list of n elements. Both in the classical and in the quantum setting, we know that (i) takes Ω(log n) comparisons and (ii) takes Ω(n log n) comparisons. Problems (i) and (ii) are instantiations of the following more general problem, which is parameterized by a partial order P on n elements: Using comparisions only, determine an unknown linear order of n elements that is guaranteed to be consistent with P. We obtain problem (i) by setting P to be a linear order on all but one element, and (ii) by making P empty. If we denote by e(P) the number of linear extensions of P, we have that e(P) = n in case (i) and e(P) = n! in case (ii). Since there are e(P) different outcomes and each classical comparison gives us at most one bit of information, we need at least log e(P) such comparisons. Thus, one obtains the classical lower bounds for (i) and (ii) in a uniform way. The simple information theoretic argument breaks down in the quantum setting. Nevertheless, using the notion of graph entropy, Andy proved a lower bound of Ω(e(P)) - O(n) for the number of comparisons in the quantum setting. He conjectured that the O(n) term can be dropped, which would yield a uniform proof of the quantum lower bounds for (i) and (ii).

On Wednesday morning, Omer Reingold talked about recent progress towards a simpler or more combinatorial proof of the PCP Theorem. In particular, he presented a more modular way of composing proof systems, a crucial step in the known proofs of the PCP Theorem. Wednesday afternoon was kept free for a hike in the woods - one of the nice traditions at Dagstuhl.