This work is licensed under a
Creative Commons License.
|
Friday, October 31, 2003
Lessons from the IM ExperimentLast week 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 bit.
9:14 AM # Comments []
Wednesday, October 29, 2003
Changing Strings but not DistributionsLet 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 every string.
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.
9:29 AM # Comments []
Monday, October 27, 2003
Quantum Leaping to ConclusionsA 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 was PP.
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.
9:13 AM # Comments []