Friday, March 14, 2003
Doing homework the hard way
In 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.
Thursday, March 13, 2003
Complexity Class of the Week: The Permanent
be an n×n matrix over the integers. The determinant of the
A is defined as
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
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.
Tuesday, March 11, 2003
Theory A and Theory B
Four 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.
Monday, March 10, 2003
I 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.