Critical Mass

In the left column of this weblog's homepage, I've added a new "weblogs" section to list the academic weblogs that I have been following. Not very long right now, so start up a relevant weblog and I'll add you to the list.

What is Critical Mass? This is a weblog written by U. Penn English Professor Erin O'Connor. Not much computer science but she covers a number of issues about academic freedom, an important issue to every academic. Take a look.

Don't forget that the 2004 Complexity Conference submissions are due today. Have a great Thanksgiving!

Theory and XML

XML (eXtensible Markup Language) has become quite a popular data format in recent years. XML roughly corresponds to a tree. For example,

<person><name>Harry</name><age>29</age></person>
<person><name>Jane</name><major>Computer Science</major></person>

represents a tree. The root having two children, each labeled "person". The first of these children has two children named "name" and "age". The first of those children has a leaf node labeled with the phrase "Harry". For a larger example, see the RSS feed for my weblog.

XML was designed as a flexible way to present documents for later displaying. Since the XML format can be easily produced and parsed, XML also serves as a standardized method for transferring data between databases, far better than the old CSV (Comma-Separated Values) format.

Recently there have been some work on directly manipulating and querying the XML data. As a theorist, this seems like a bad idea, particularly for larger databases. While XML completely represents the underlying tree, it is not a good implementation of that tree. Basic tree operations like parent and sibling are very expensive just looking at XML. About the only thing one can do quickly with XML is depth-first search. Far better to "shred" the data into a better tree implementation like a DOM (Document Object Model) or a full-fledged database and do the work there, rewriting a new XML if needed.

One issue though is when the XML file is on the order of 5-10 GB, a bit larger than what can be stored in the memory of a typical desktop machine. One can stream through the file rather quickly but cannot recreate the tree. This opens up some interesting theoretical questions:

1. Given a stream of data in XML format, how can one do efficient analysis and manipulations of the underlying tree? I suspect one would want to sometimes shred subtrees, but you cannot determine the size of the subtree until after its been streamed. Perhaps some randomness or streaming the file multiple times might be helpful.
2. XML might not be the right model of a tree for this purpose. What is the best way to stream a tree or other data structure to allow an efficient implementation of the basic operations of the data structure? Perhaps some redundancy might be useful.

Rational Functions and Decision-Tree Complexity

I thought I should mention some of my favorite and most frustrating open questions over the years. Here's one of them:

Let f:{0,1}ⁿ→{0,1}. Let h and g be n-variable degree d polynomials over the reals. Suppose for all x in {0,1}ⁿ, g(x)≠0 and f(x)=h(x)/g(x). Is there a constant k such that the decision-tree complexity of f is bounded by d^k?

The decision-tree (or query) complexity is the number of bits of x that need to be viewed to determine f(x). The queries to the bits of x can be adaptive. I'm particularly interested in the case where d is poly-logarithmic in n.

Nisan and Szegedy answer the question in the affirmative if g(x)=1. Their result holds even if f(x) is only approximated by h(x). However if we allow arbitrary g(x), h(x)/g(x) can closely approximate the OR function which requires looking at all of the bits. The case where we require exact equality of f(x) and h(x)/g(x) is the open question at hand.

Update 1/14/26: Solved!

Midwest Theory Day

Over the years a number of localized theory workshops have developed which bring together researchers from around the area to mingle and learn about some of their research. For example BATS (Bay Area Theory Seminar-San Francisco area), CATS (Capital Area Theory Seminar-Washington DC), DIMACS Mixers (New Jersey), Netherlands Theoriedag and others including many I've never heard of.

In the middle of America we have the Midwest Theory Day. Generally since 1980 this is a day of talks held in the fall in the Chicago area and in the spring somewhere else in the Midwest such as the University of Wisconsin, Indiana, Illinois, Purdue, Notre Dame, etc. The next Midwest theory day will be held December 13 at DePaul University and in the spring on April 24 at the University of Iowa.

So come to Chicago or attend (or organize) you own local area theory seminar and meet your theory neighbors.

Editors Needed

Back in my science-fiction reading days, I particularly remember one editorial written in one of those anthology magazines about 1980: In the near future, you will be able to access, via your personal computer, any science fiction story right after it has been written. If you like a certain author, you can read other stories from that author, even if we didn't decide to put it in this magazine. In this future world, will you still need me, the editor? The answer is yes, for there will be way too much dreck out there for you to find the good stories within, and you will need people like me to point them out to you.

The future is now and though I haven't kept up with science fiction, the same issue applies to academic publications. Recent posts by Michael Nielsen and on Slashdot have asked: With nearly all new papers in physics and computer science easily accessible on the web, how do you find the ones worth reading?

Conferences have traditionally played this role in computer science. But, by definition, paper choices are decisions by committee and with the massive growth in the field, many good papers do not appear in the major conferences.

What we need are "editors"! You can help. Write a survey paper, or spend a page in your research papers discussing the important earlier results in a field. Maintain a web page pointing to papers you find interesting. Start a weblog saying what you find interesting--you don't have to post long or often, just to say, hey, this paper is worth looking at. This way people with similar interests to you can find out what at least you think is important. Only by many of us working together can we make the interesting papers stand out.

A Regular Problem

Here's a problem from Janos Simon. For a set A, let L(A)={x | for some m≥0, x^m is in A} Simon asked, as a homework problem, to show that if A is regular then L(A) is also regular. The standard solutions require an exponential increase in the number of states. Simon asks whether this is needed in general. If A is accepted by an n-state DFA, can one find a poly(n)-state DFA for L(A) or is an exponential state DFA for L(A) required?

As an aside the submission deadline for the Complexity Conference is right around the corner. Get your papers ready.

Opportunities at Chicago (Blatant Plug)

[I will do this just once. Feel free to use the comments link to mention your own institution.]

We are seeking theory graduate students and faculty (all ranks) in the Computer Science Department of the University of Chicago. The Toyota Technological Institute, located on the University of Chicago campus, is looking for both faculty and postdoctoral candidates.

The Theory Group has expanded over the past few years and will continue to grow. We have a long tradition of outstanding doctoral students and notable research accomplishments.

Click here for further information.

25 Years of Science Times

It happened right after I started high school in suburban New Jersey, the start of the Science Times section in Tuesday's New York Times. The Science Times not only helped get me excited about science but made me feel others could get excited over science as well. I've kept reading it off and on during these past 25 years. The Science Times has reported on a fair amount of research in complexity and theoretical computer science, for a time some joked that a result was not important until it appeared in the New York Times.

Today the New York Times celebrates the 25th Anniversary Issue of the Science Times. It features 25 questions such as Does Science Matter? and What Is the Most Important Problem in Math Today? (Hint: It's not P versus NP).

I'll end this post with a quote from the essay of Alan Lightman:
All of the scientists I've known have at least one quality in common: they do what they do because they love it, and because they cannot imagine doing anything else. In a sense, this is the real reason a scientist does science. Because the scientist must. Such a compulsion is both blessing and burden. A blessing because the creative life, in any endeavor, is a gift filled with beauty and not given to everyone, a burden because the call is unrelenting and can drown out the rest of life.

CISE Reorganization

The Computer and Information Science and Engineering Directorate of the NSF has completed it reorganization. The CISE web site details the new structure.

CISE now has four divisions. Instead of each division have a large number of specific programs, each division contains a smaller number of clusters covering a broader research area. I'm happy to see "Computational Complexity" specifically mentioned in the Formal and Mathematical Foundations Cluster in the Division of Computing & Communication Foundations. However it shares that cluster with such diverse topics as "computational algorithms for high-end scientific and engineering applications" and "analysis of images, video, and multimedia information." Hopefully funding panels will meet in the more specific areas to avoid trying to compare proposals from vastly different areas of computer science.

Quantum and Biological Computing sit in a different CCF cluster, Emerging Models and Technologies for Computation. This shows NSF's hopes for these new technologies but may also give them a way to phase out these areas if the technologies don't show promise.

Program announcements for the CCF clusters are still under development. The ITR solicitation is still not expected until Thanksgiving. So if you plan a grant proposal this year, you'll still need to wait.

The Web and Research

I received the following email from David Molnar, a Berkeley graduate student. He asks some interesting questions about the use of the web and research. Instead of just answering them immediately, I though I would share his email (with his permission) and let you think about it. Feel free to comment. I'll also address some of his points later in future posts.

Molnar's Letter:

I wanted to follow up on your comment about theoretical computer science and e-mail/IM. Also, use of weblogs.

1. There's a piece of folklore about how IP=PSPACE was proved pursuant to some race between many researchers carried out over e-mail. I've once or twice found myself in e-mail races with other people on mailing lists when we're responding to something technical. Do you think the day will come when some major theorem is proved in an IM chat room? :)

2. Weblogs as place for ideas. A friend of mine asked me if I thought researchers in theory would be interested in putting up a web page (actually, we were discussing a wiki) about open problems. My response was pretty much like what you see in Oded Goldreich's FAQ -- "well that's nice, but good research problems are hard to find, and people seem to reserve them for themselves or their close colleagues."

   The point: I find that I'm starting to use my weblog as a place to deposit ideas for problems that I just don't have time to pursue, or aren't in what I think is my main line of research. In the old days they would have gone into a notebook somewhere and no one would have seen them. Now maybe someone will pick them up -- and I think that's great (especially since I usually don't know how to progress). At the same time, I wonder how peoples' concerns about ownership of ideas will affect the way they use weblogs. What do you think?

The PCP Theorem

This week I started teaching the PCP theorem: Every language in NP has a proof that can be probabilistically checked with only O(log n) random coins and a constant number of queries. One graduate student asked me which came first, the PCP theorem or the connection to hardness of approximation. That seemed like a strange question; after all why would so much effort be put into reducing parameters like number of random coins or queries unless there was some application behind it. But then again, so much emphasis is now in the literature on these parameters that he probably thought these were always the parameters people cared about the most.

To put the record straight: Feige, Goldwasser, Lovász, Safra and Szegedy made the connection between the interactive proof literature and approximation. Arora and Safra showed the importance of reducing random coins and queries and proved a weaker version of the PCP theorem. The theorem in the above form was proved by Arora, Lund, Motwani, Sudan and Szegedy.

I have been teaching off the notes of Madhu Sudan from a short course he taught on the PCP theorem. The notes don't go through every detail, but they give one of the better expositions of what is still quite a complex proof.

What happened at NEC?

The NEC Research Institute (NECI) died just over a year ago. I didn't feel comfortable talking about it then so let me say a few words now.

I joined NECI in 1999 just after its tenth anniversary. When I joined its mission and focus was basic research in computer science and physics. NECI gave me considerable time and resources to study fundamental questions in computational complexity. It was an exciting place to be.

Soon thereafter some changes were occurring. NEC modified the mission of NECI to focus on producing technologies with basic research secondary. Some researchers (though not us theorists) were encouraged to join "technology groups" to find practical applications of their research. But during this time, the administrators always supported basic research and I never felt uncomfortable doing theory.

But then on November 1, 2002, NECI merged with NEC CCR&L, a more applied research lab in the same building to form NEC Laboratories America. The new mission makes no mention of basic research. The scientists in charge were replaced by engineering/management types. Many of the research scientists, particularly physicists, were let go.

My job was never in immediate danger but NEC was no longer the place for me and so I went on the job market; no one was surprised when I decided to leave.

A corporation like NEC needs to make decisions for the health of the company. I do not fault NEC for the decisions that it made and they gave me a few great years. Still I mourn the NEC Research Institute, quite a special place during its thirteen year run.

Lessons from the IM Experiment

Last 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.

Changing Strings but not Distributions

Let f be a function that maps Σⁿ to Σⁿ. Let U represent the uniform distribution on Σⁿ 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 n³ 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(0ⁿ)=0ⁿ, 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.

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 P^PP was PP.
There is one more for your blog: A⊆ B implies B⊆ A^B but not A^B⊆ B (duh!)

He goes on to say he made his quantum leap to conclusions since for the quantum class BQP, P^BQP=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⊆A^B without needing to assume A⊆B.

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 Σ₂ is in BPP if NP is in BPP. The rest is straightforward induction. Here is our first proof:

Σ₂=NP^NP⊆ NP^BPP⊆BPP^BPP=BPP. 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 Σ₂ 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 NP^A in BPP^A for all A.

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 Messaging.

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 fortnow@yahoo.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.

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.

TTI

There are two computer science departments on the University of Chicago campus. The one I belong to, a department in the physical sciences division of the University and the other, the Toyota Technological Institute at Chicago (TTI-C). What is TTI-C?

The Toyota Technological Institute, a university covering various engineering disciplines located in Nagoya City, Japan, was founded in 1981 from funds from the Toyota Motor Corporation as directed by the Toyoda family. They decided to start a computer science department and locate it in the states to have a broader access to computer science faculty and students. For various reasons they settled on Chicago and set up an agreement with the University of Chicago, using space in the University of Chicago Press building. TTI-C has just officially started up and have already signed up a few strong faculty members including theorist Adam Kalai and Fields medalist Stephen Smale. TTI-C plans to increase its faculty size and start up a graduate program in the near future.

Although there will be some sharing of courses and a few of our faculty (including myself) sit on a Local Academic Advisory Council for TTI-C, TTI-C will formally maintain itself as a separate institution from the University. Nevertheless close collaborations between our department and TTI-C has already established an exciting research environment for our combined faculty and students.

The Agony of Defeat

This is for my friends in Boston who suggested I do a sports post.

One of the great parts of my job is working with people from around the world. I was working with a graduate student, Luis Antunes, from Portugal when we found out that Portugal would play the US in the 2002 World Cup. We had various rounds of taunting back and forth with me fully knowing the US didn't stand a chance in that match. When the US did win, Luis tells me the whole country went into a deep depression. By contrast, for the most part people in the US didn't care.

I can now understand Portugal's pain as the city of Chicago has gone into a similar kind of quiet depression over the Cubs failure to advance to the world series. Impressive what sports can do to the psyche of a city or a country.

Memo to my friends in Boston: Hope things go well for the Sox so your city doesn't end up feeling tomorrow like Chicago does today.