This work is licensed under a
Creative Commons License.
|
Friday, April 02, 2004
More News from DagstuhlAnother Guest Post from Dieter van Melkebeek
Thursday morning, Shuki Bruck gave the first talk at the workshop that dealt with actual Boolean circuits. He pointed out that cyclic circuits can be combinational and may allow us to realize Boolean functions with fewer gates and/or less delay. Consider the following circuit with inputs x1, x2, x3, and outputs f1, f2, f3, f4:
|-----------------------------------| | | | x1 x2 -x1 x3 | | | | | | | | | | | | | | v v v v | | | |-> \/ ----> /\ ----> \/ ----> /\ --| | | | | v v v v f1 f2 f3 f4Although the circuit is topologically cyclic, the outputs are well-defined and only depend on the inputs. (Look at the cases x1=0 and x1=1 separately.) A careful analysis shows that every acyclic circuit that outputs f1, f2, f3, and f4 needs at least 5 nonunary gates. Thus, circuits with feedback allow us to gain a factor of 4/5 in terms of number of gates needed to compute these functions. (As usual, we do not count negations.) Shuki presented a sequence of Boolean functions for which the reduction in the number of nonunary gates asymptotically reaches 1/2 if we only allow gates of fanin at most 2. He raised the question how significant the reduction can be if we allow larger fanin.Thomas Thierauf presented an NC2 algorithm for unique perfect matching. A perfect matching in a graph is a collection of disjoint edges that cover all vertices. It is known for some time how to decide the existence of a perfect matching and how to construct one in randomized NC2:
It is open whether perfect matchings can be constructed deterministically in NC.
- Assign random weights from a small range of integers to the edges of the graph such that with high probability there is at most one minimum weight perfect matching. If we are in the situation with a unique minimum weight matching M, we can decide whether a given edge belongs to M by evaluating two determinants of matrices with integer entries that are exponential in the weights. Since the weights are small, we can do the latter in NC2.
- Run the NC2 algorithm on all edges in parallel and verify that the result is a perfect matching M.
To decide whether a graph G has a unique perfect matching, Thomas first runs step 2 above (with unit weights). If that test fails, the algorithm rejects since G either has no perfect matching or has more than one. If the test is passed, the algorithm additionally verifies that G has no perfect matching M' other than M. Such an M' exists iff G contains a cycle that alternates between edges from M and edges in G-M. The latter can be cast as a reachability problem in a graph that is roughly a concatenation of directed copies of M and G-M. Since directed graph reachability can be computed in NC2 and the input to the reachability problem can be computed in NC2 by step 2 above, the additional test runs in NC2, as does the entire algorithm.
On Friday, Oded Lachish discussed the current records on unrestricted circuit lower bounds for explicit functions in n Boolean variables. For circuits that can use any binary gate, the record dates back to 1984 and stands at 3n. For circuits that can use any binary gate except parity and its negation, the record has recently been improved from 4n - O(1) to 5n - o(n). Both records use the technique of gate elimination, and Oded conjectured that the 3n result can be improved along the lines of the recent 5n - o(n) result.
The workshop ended at noon on Friday. One statistic: among the 33 talks, 3 were blackboard only, 5 used handwritten slides, 1 printed slides, and 24 were computer presentations.
Finally, I have one suggestion for those readers who have attended a Dagstuhl seminar in the past. In a response to changes in financial support, the Dagstuhl office is requesting information about research publications that grew out of or have otherwise been significantly influenced by a Dagstuhl seminar. If you are an author of such a publication, please send the information to office@dagstuhl.de. Let's try to keep the wonderful tradition of Dagstuhl alive!
2:39 PM # Comments []
Wednesday, March 31, 2004
A Free Lunch Theorem For Circuit ComplexityA 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 = Ω(n2), 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 log2 n). It remains open whether the TS = Ω(n2) 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 AC0 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 AC0 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.
1:03 PM # Comments []
Tuesday, March 30, 2004
Changes in Introductory TheoryComments to my last post basically ask how has the introductory courses in theory has changed over the years. My first reaction: remarkably little. Theoretical models of computation do not depend on the current hot technology, particularly at the undergraduate level. Many of the basic results we teach today were also taught say 25 years ago. But without doubt theory courses have changed their emphasis on various topics over the years.
Every professor teaches a theory course differently so there is no fixed answer to what has changed. But here are some trends that I have seen (from a distinctly American point of view):
But remember these are exceptions. Basic topics like Turing machines, undecidability, NP-completeness, Savitch's theorem and time and space hierarchies still get taught much the way they were taught in the 70's.
- Less emphasis on automata theory, particularly for context-free languages. Many schools do away with automata theory all together.
- Less depth in computability theory. Most courses will cover undecidability but you'll less often see the recursion theory or even Rice's theorem taught.
- Does anybody still teach the Gap, Union and Speed-Up Theorems and Blum complexity measures anymore?
- Only one new theorem since the mid-70's has become a fundamental part of an undergraduate complexity course: The 1988 Immerman-Szelepcsényi Theorem stating that nondeterministic space is closed under complement.
- There has been a trend in adding some recent research in complexity as the end of a course based on the interests of the instructor: Randomized computation (though recent algorithms for primality might change how it gets taught), cryptography, interactive proofs, PCPs and approximation, quantum computing for example. Parallel computation has come and gone.
5:49 PM # Comments []
Monday, March 29, 2004
Opening DayToday starts the spring quarter at the University of Chicago and I start teaching undergraduate complexity. Many of the most beautiful concepts in theory get taught in the course: The Church-Turing thesis, universal Turing machines and undecidability, the P versus NP problem and much more.
Today's students have an understanding of computers that come from exposure at an early age that I cannot imagine. Still you cannot truly view computer science as a science until you learn its mathematical foundations. This course gives that foundation and uses it to pose (and sometimes answer) many basic questions: What is a computer? What can we compute? What can we compute quickly?
As computers become more and more part of our daily lives, these basic questions take on greater importance and I'm excited, as always, to tackle them with a new group of students.
9:02 AM # Comments []