Friday, October 31, 2003
Lessons from the IM Experiment
I started an experiment using instant messaging. I thank the
many of you who sent me IMs, a great way for me to meet you, the
readers of this weblog. I plan to keep trying IM for a while but I
have had learned a few lessons which seem obvious in retrospect.
Instant messaging can be a time sink. I love communicating with
people, which is the main reason I keep this weblog going. However, as
most academics, I have much going on and can't afford to have many
lengthy discussions. I've also learned there is no clean way to end an
IM conversation. So please feel free to IM me but don't take it
personally if I rudely keep the conversation short.
Just because the nice icon on the home page says I'm online it doesn't
mean that I am at my computer and available to chat at the
moment. Often I am and I will but if not I will eventually see your
message and respond. If there is really is something important that
you want to discuss with me via IM we can setup a scheduled time via
email. I often do this with phone calls so why not IM too?
I've also discovered IM conversations can be recorded, posted on the
web and could be used in a court of law. I need to be
careful about what I say.
I have already had some interesting research conversations and ideas
for weblog posts via IM. The
last post came in part because of some IM
questions about the Feigenbaum-Fortnow paper. Email became a powerful
research tool when email use hit a critical mass among computer
scientists sometime in the mid-late 80's. I believe IM will also follow that
curve and I hope to keep ahead of it and perhaps nudge it a little
Wednesday, October 29, 2003
Changing Strings but not Distributions
Let f be a function that maps Σn to
Σn. Let U represent the uniform distribution on
Σn and D be the distribution that one gets by applying
f to a string drawn from U.
We wish to find f that change x but keep the underlying distribution
close to the same, in particular we want the following properties,
(1) Prob(f(x)≠x)≥2/3 when x is drawn from U.
(2) U and D should be statistically close, informally no algorithm
making a polynomial number of samples will be able to distinguish,
with high confidence, whether those samples came from D or U.
Achieving such an f is easy, consider f that just flips
the first bit of x. (1) holds all the time and U=D.
Suppose we add a restriction to f:
(3) In the bits where x and f(x) differ those bits are 1 in x and 0 in
f(x). For example, f(011)=010 is allowed, but f(011)=f(111) is not.
An f fulfilling (1), (2) and (3) is impossible. (1) and (3) means that
f will reduce the number of ones on most of the strings and taking say
n3 samples we will notice a statistical difference in the
number of bits which are 1 depending on whether the samples were drawn
from U or D.
Suppose we replaced (3) with a weaker restriction:
(3') In the first bit where x and f(x) differ, that bit is 1 in x an 0
in f(x). So f(110)=011 is allowed but f(001)=010 is not allowed.
Can an f fulfilling (1), (2) and (3') exist? Not so clear, but Peter
Shor found a simple example: f(0n)=0n, and for
the other x, f(x)=x-1 where x is viewed as a nonnegative integer
written in binary. D is indistinguishable from U yet f changes nearly
These questions are related to an old paper
I had with Joan Feigenbaum which has gotten some recent attention
because of a nice new FOCS paper
by Bogdanov and Trevisan that builds on our paper. The proofs in these
papers work partly because (1), (2) and (3) cannot all happen even for
arbitrary distributions U. Both papers give a negative result for a nonadaptive
case; the adaptive case corresponds to (1), (2) and (3') and Shor's
example shows that the proof techniques will not directly lead
to a solution in the adaptive case which remain open.
Monday, October 27, 2003
Quantum Leaping to Conclusions
A quantum computing graduate student sent me email over the
weekend. He had thought he had proven some surprising results about the
class PP and was wondering if he was making some mistake. After some
discussion here was his reply:
Ok I get it. Somehow I jumped to the conclusion that PPP
There is one more for your blog: A⊆ B implies B⊆
AB but not AB⊆ B (duh!)
He goes on
to say he made his quantum leap to conclusions since for the quantum
class BQP, PBQP=BQP, he thought the same property must hold
for all classes.
I present this because he suggested it for my weblog and as a public
service for those who might make a similar mistake. Yes, in case you
were wondering, for reasonable classes A (like A=P), B⊆AB without
needing to assume A⊆B.