### Friday, February 21, 2003

**More on Perfect Graphs**

Today I saw Maria Chudnovsky give a talk at Princeton on her new result with
Paul Seymour finding a polynomial-time algorithm for testing perfect
graphs, a result I mentioned
in an earlier post. The algorithm actually tests for Berge graphs
which are graphs with no induced odd cycle of length at least five or
the complement of such a graph. An earlier result of Chudnovsky,
Robertson, Seymour and Thomas showed that a graph is perfect if and
only if it is Berge. Otherwise the new algorithm does not use the
techniques of the earlier paper.
The algorithm looks for some basic structures that would imply the
graph is not Berge. If these structures don't exist then one does a
cleaning process that simplifies the search for odd cycles. A
cleaning process is described in another paper by Chudnovsky,
Cornuéjols, Liu, Seymour and Vuškovic.

While the algorithm will test whether the graph is Berge, it is still
open to determine whether a graph had an odd cycle of length at least
five.

Chudnovsky's web
page now has papers describing all of these results as well as other
pointers on perfect graphs.

1:12 PM
#
Comments
[]

### Monday, February 17, 2003

**Complexity Class of the Week: BPP**_{path}

Previous CCW
Let us call a nondeterministic Turing machine M *balanced* if for
every input x, all of its computational paths have the same length,
i.e., the number of nondeterministic bits depends only on x and not on
previous guesses. We can define the characterize class BPP as follows:

L is in BPP if there is a balanced nondeterministic polynomial-time M such that

- If x is in L then there are at least twice as many accepting as
rejecting paths of M(x).
- If x is not in L then there are at least twice as many rejecting
as accepting paths of M(x).

Suppose we use the same definition without the "balanced"
requirement. This gives us the class BPP_{path} studied mostly
in a 1997
paper of Han, Hemaspaandra and Thierauf.
BPP_{path} contains BPP by definition but it contains much
more. Let us show that SAT is contained in BPP_{path}.

Let φ be a formula with n variables. Consider the following
machine M(φ): Guess an assignment a for φ. If a is rejecting
then reject. If a is accepting then guess n+1 bits, ignore them and
accept.

If φ is not satisfiable then M(φ) will only have rejecting
paths. If φ is satisfiable then it will have at least
2^{n+1} accepting paths and at most 2^{n}-1 rejecting
paths fulfilling the requirements of the definition of
BPP_{path}.

Han, Hemaspaandra and Thierauf prove many other results about
BPP_{path}. The class contains MA and
P^{NP[log]} (P with O(log n) queries to an NP language like
SAT). BPP_{path} is contained in
P^{Σ2[log]}, BPP^{NP} and
PP.

Whether BPP_{path} is contained in ZPP^{NP} or Σ_{2} remain
the most interesting open questions about this class.

10:05 AM
#
Comments
[]

### Sunday, February 16, 2003

**News for Nerds. Stuff that Matters.**

I noticed that Slashdot has
recently mentioned some TCS research. This would therefore be
theoretical computer science that matters to nerds.
The first was a pointer to Scienceblog article
on the work of Roughgarden and Tardos on selfish routing. Here is
their main example: Consider two roads from city A to city B. The
first road takes an hour and the second road takes p hours, where p is
the fraction of people who take the second road. The best way to route
to minimize total travel time is for half the people to take the
second road (average time = 3/4 hour). If everyone acts selfishly, the
only equilibrium is everyone taking the second road for an average
time of one hour. For more details see Tim Roughgarden's home page.

The other article pointed to Microsoft's research Penny
Black Project which hopes to prevent spam by making sending email
"expensive." The
variation
using complexity requires the sender to solve a moderately hard
problem generated by the intended recipient.

Always keep in mind that what happens at Microsoft research,
especially amongst the theoreticians, should not be read to imply any
future email policy at Microsoft, no more than one can determine
future NEC policies from my own research.

10:11 AM
#
Comments
[]