Friday, October 24, 2003
When Good Theorems Have Bad Proofs
Here is one of my favorite examples of a bad proof for what turns out
to be a correct theorem.
Theorem: If NP is in BPP then the whole polynomial-time
hierarchy is in BPP.
Let's focus on simply showing Σ2 is in BPP if NP is
in BPP. The rest is straightforward induction. Here is our first
Do you see the problem with this proof?
To get a correct proof (first due to Zachos) we need to use Arthur
Merlin games. Consider a Σ2 language L as an
∃∀ expression. Since NP is in BPP, we can replace the
∀ with a probabilistic test. This gives us what is known as MA
or a Merlin-Arthur game where the powerful Merlin sends a message that
Arthur can probabilistically verify. A now classic result shows that
MA is contained in AM, where Arthur provides a random string to Merlin
who must then provide a proof based on that string. Once again we
apply the NP in BPP assumption to allow Arthur to simulate Merlin
probabilistically and now we have a BPP algorithm for L.
The problem in the first proof is in the second
"⊆". The assumption NP in BPP does not imply
NPA in BPPA for all A.
Wednesday, October 22, 2003
Talk to Me
How has the internet most affected the study of science? In one word:
communication: the ability for scientists to discuss and share their
research with each other quickly and cheaply. So I strive to find new
ways to use the internet to improve communication. Starting this weblog
is one such example. I'd thought I would try another: Instant
Now many of you are thinking I am crazy, but for different
reasons. Some of you out there have been using instant messaging for
years and wondering how I could consider it s "new"
technology. But many of you out there have barely figured out how to
read your email attachments and have hardly even heard of IM.
On a trial basis, for my weblog readers, I will welcome your
instant messages. Talk to me about this weblog, about complexity and
computer science in general or about whatever you want. Maybe I'll
start a trend and all computer scientists will IM each other. Maybe
not but it's worth trying out.
I'm using Yahoo Instant Messaging; my Yahoo id is the imaginative
"fortnow" (note: I do not read email sent to
email@example.com). I put a button on the left column of the weblog
home page that tells you when I am online and you can click to
connect. I look forward to hearing from you.
Monday, October 20, 2003
What's happening at the NSF?
There is a big reorganization in the CISE directorate of NSF. To
understand what's happening, let's review the previous structure..
The National Science Foundation, like
most government bureaucracies,
has a tree-like structure. At top is the office of the director (Rita
Colwell). Below that are several directorates including the
Directorate for Computer and
Information Science and Engineering
(CISE) headed by Peter Freeman. By law every organization in NSF
cannot be just "science" but "science and
engineering" except for the Foundation itself.
Below CISE were several divisions, including Computer-Communications
Research (C-CR) headed by Kamal Abdali. C-CR ha several programs
including the Theory program headed by Ding-Zhu Du.
Peter Freeman, who recently became head of CISE, has decided to
reorganize the whole directorate. Exactly what it will become should be
announced next week but there are some hints in this
presentation. Change is always scary but I'm hopeful theory will
survive. I'll give more details when I know them.
To overcome the tree structure of NSF, there are a number of
cross-disciplinary programs. One such program, Information and
Technology Research (ITR), has produced several large, medium and
small grants to a variety of projects, including many applications of
theory. This is the last year of ITR solicitations and the
calls have been well behind schedule, probably not unrelated
to the CISE reorganization.
This year's topic will be on "ITR
for National Priorities" with more details promised by
Thanksgiving. Unconfirmed rumors have the program will
be more focused and only making medium sized grants.