This work is licensed under a
Creative Commons License.
|
Friday, March 14, 2003
Doing homework the hard wayIn yesterday's post I linked to some lecture notes of Vigoda on Valiant's result. Those notes also cite a paper of Zankó. Now every paper has a story but this one is a little more interesting than most.
In my first year as an assistant professor at the University of Chicago, I taught a graduate complexity course where I gave a homework question to show that computing the permanent of a matrix A with nonnegative integer entries is in #P. Directly constructing a nondeterministic Turing machine such that Perm(A) is the number of accepting computations of M(A) is not too difficult and that was the approach I was looking for.
In class we had shown that computing the permanent of a zero-one matrix is in #P so Viktoria Zankó decided to reduce my homework question to this problem. She came up with a rather clever reduction that converted a matrix A to a zero-one matrix B with Perm(A)=Perm(B). This reduction indeed answered my homework question while, unbeknownst to Zankó at the time, answered an open question of Valiant. Thus Zankó got a publication by solving a homework problem the hard way.
7:25 AM # Comments []
Thursday, March 13, 2003
Complexity Class of the Week: The PermanentPrevious CCW
Let A={aij} be an n×n matrix over the integers. The determinant of the A is defined as
Det(A)=Σσ(-1)|σ| a1σ(1)a2σ(2)...anσ(n) where σ ranges over all permutations on n elements and |σ| is the number of 2-cycles one has to apply to σ to get back the identity.The determinant is computable efficiently using Gaussian Elimination and taking the product of the diagonal.
The permanent has a similar definition without the -1 term. We define the permanent of A by
Perm(A)=Σσ a1σ(1)a2σ(2)...anσ(n) Suppose G is a bipartite graph and let aij be 1 if there is an edge from the ith node on the left to the jth node on the right and 0 otherwise. Then Perm(A) is the number of perfect matchings in G.Unlike the determinant the permanent seems quite hard to compute. In 1979, Valiant showed that the permanent is #P-complete, i.e., computing the permanent is as hard as counting the number of satisfying assignments of a Boolean formula. The hardness of the permanent became more clear after Toda's Theorem showing that every language in the polynomial-time hierarchy is reducible to a #P problem and then the permanent.
The permanent is difficult to compute even if all the entries are 0 and 1. However determining whether the permanent is even or odd is easy since Perm(A) = Det(A) mod 2.
Since we can't likely compute the permanent exactly, can we approximate it? The big breakthrough came a few years ago in a paper by Jerrum, Sinclair and Vigoda showing how to approximate the permanent if the entries are not negative.
1:49 PM # Comments []
Tuesday, March 11, 2003
Theory A and Theory BFour speakers are chosen for the NVTI Theory Day along two axis: In and out of the Netherlands, and Theory A and Theory B. For example I was the non-Dutch Theory A speaker. But what is Theory A and B?
In 1994, the Handbook of Theoretical Computer Science was published as a two volume set each containing many survey articles that have for the most part stood the test of time. From the backcover: Volume A [Algorithms and Complexity] covers models of computation, complexity theory, data structure and efficient computation. Volume B [Formal Models and Semantics] presents material on automata and rewriting systems, foundations of programming languages, logics for program specification and verification and modeling of advanced information processing.
Over the years, Theory A and Theory B have come to represent the areas discussed in the corresponding volumes. In the US the term theoretical computer science covers areas mostly in Theory A. For example STOC and FOCS, the major US theory conferences, cover very little in Theory B. This is not to say Theory B is not done in this country; it is just labelled as logic or programming languages.
Outside the US there is a broader view of what is theory. The European ICALP conference covers both areas and has two submission tracks A and B that again correspond to Theory A and B.
Some countries, like Britain and France, focuses mostly on Theory B. Other countries, like the Netherlands and Germany have many groups in both areas.
Some Europeans are upset that their research is not considered theory by the Americans. Too bad.
12:47 PM # Comments []
Monday, March 10, 2003
Talk PostedI posted the slides of my talk, "Church, Kolmogorov and von Neumann: Their Legacy Lives in Complexity" that I presented at the Dutch Theory Day last week, for those that are interested.
3:24 PM # Comments []