Constant Depth Circuits, Fourier Transform, and Learnability (by Adam Klivans)

First, thanks to Jeff Erickson for the lone comment on my previous post. For a second I was worried that I would have to post about Quantum Learning to bait Scott Aaronson into commenting. Fortunately, we're past that. I also realize now that being in Chicago I'm just a two hour drive away from you Jeff at UIUC. Maybe you, Ernie, and I should get some 3-D hotcakes at the local Waffle House-- on me.

Many top notch researchers come to visit the Toyota Technological Insitute here in Chicago. This fall alone Lenore Blum, Bruno Codenotti, Prahladh Harsha, and Jaikumar Radhakrishnan will be in residence along with TTI's regular faculty.

Yishay Mansour visited in August for about two weeks, and I had the chance to ask him about his work along with N. Linial and N. Nisan which pioneered the use of discrete Fourier analysis in computational learning theory. The paper Constant Depth Circuits, Fourier Transform, and Learnability gives a quasi-polynomial time learning algorithm for constant depth circuits with respect to the uniform distribution. More importantly, it pointed out a connection between the Fourier concentration of a Boolean function and its learnability.

If f is a Boolean function, we could imagine writing f as a multilinear polynomial in n variables mapping {-1,1}^n to {-1,1}. Every Boolean function can be written as such a polynomial whose total degree is at most n. Each coefficient of this polynomial measures the correlation of f with that monomial. These are the Fourier coefficients of f. Linial, Mansour, and Nisan showed that if the sum of the squares of the coefficients of monomials of degree d and larger is small, then there is an n^{O(d)} time algorithm for learning f with respect to the uniform distribution-- roughly speaking it is sufficient to estimate the coefficients of only the low degree monomials and output this polynomial.

What does any of this have to do with constant depth circuits? They also proved that for any circuit of depth d, the sum of the squares of the coefficients on the terms of degree (log n)^d and higher decays rapidly. From the above paragraph this gives us a quasi-polynomial time algorithm. For a rough intuition as to why this is true, consider one implication of Hastad's Switching Lemma, namely that parity cannot even be approximated by constant depth circuits. Thus every coefficient of a sufficiently large monomial (each monomial is a parity function) must be small.

As it turns out, according to Yishay, the work stemmed from an effort to prove circuit lower bounds, rather than a plan to develop new learning algorithms. The authors were inspired by Kahn, Kalai, and Linial's work on the influence of variables on Boolean functions and thought that discrete Fourier analysis might be the right tool for studying circuits. They happened to be correct-- in an unexpected way.

Banff Revisited (by Adam Klivans)

Hey, you're back! And I'm really starting to feel comfortable at this posting gig. Thanks for all of the comments I got about my previous post-- all zero of them.

A few weeks ago Lance reported on the events from a complexity workshop he was attending at the Banff International Research Station, an institute similar to the International Space Station except that it's in Canada rather than outer space.

What Lance didn't mention was that at the exact same time, some important computer science conferences were taking place just down the street at the Banff Park Lodge. I was participating in the 17th annual Conference on Learning Theory (COLT) which was co-located with the International Conference on Machine Learning (ICML) and the Conference on Uncertainty in Artificial Intelligence (UAI).

Back when COLT stood for Computational Learning Theory (circa 1988-2002), the conference was known for focusing on the computational complexity of machine learning. Nowadays the conference still operates from a theoretical perspective, but, as the Conference on Learning Theory, the program covers everything from game theory and economics to kernel methods in addition to traditional PAC style results.

A PAC style result that appeared in COLT 2004 which may be of interest to the readers of this web log is Polynomial-Time Prediction Strategy with Almost Optimal Mistake Probability by Nader Bshouty. His paper solves a problem in the online learning setting. In this setting, an unknown function f is chosen from some fixed concept class and at time t a learner is presented with an input x chosen according to some distribution D.

The goal of the learner is to run in time polynomial in log t (and all of the other relevant parameters) and predict the value of f(x) with mistake probability O(1/t) (Haussler, Littlestone, and Warmuth proved that this mistake probability is optimal). Bshouty shows that if the concept class is PAC learnable, then there exists an online learning algorithm which runs in time polynomial in log t and achieves mistake probability O(log t/ t). His algorithm has an exponential improvement in running time as previous solutions ran in time polynomial in t. The algorithm works by iteratively creating a branching program based on hypotheses considered at previous time steps. A boosting-type procedure dictates which branch to take for any new input.

In the spirit of being controversial (Lance asked me to be controversial), I could discuss the pros and cons of the change from Computational Learning Theory to Conference on Learning Theory (as a concrete example of differences in the community, about half the participants at the COLT business meeting wanted to see COLT co-located with STOC in 2006-- University of Washington folks make your move-- and the others wanted to co-locate with ICML). I'll leave that, however, for my faithful readers to debate. I will point out that it's hard to argue with the increase in attendance at COLT over the last few years.

Favorite Theorems: The Harmonic Sieve (by Adam Klivans)

What does Lance Fortnow do after getting a paper accepted to FOCS? He goes to Disneyworld for a week, of course. While Lance blasts pasts celestial satellites on Space Mountain, I will humbly try to replace the irreplaceable.

Considering the topic of yesterday's post, if there were a list of favorite theorems in computational learning theory, a field which makes only brief appearances here on the weblog despite its many connections to computational complexity, Jeff Jackson's algorithm for learning DNF formulas would certainly be on it.

A DNF formula is a Boolean formula written as an OR of ANDs (e.g. x_1 and x_2 OR x_3 and x_5). The size of a DNF formula is equal to the number of terms or ANDs. The problem of PAC learning an unknown polynomial-size (in n, the number of variables) DNF formula with respect to an arbitrary distribution remains one of the most notorious open problems in the field (for background on PAC learning see this post or Kearns and Vazirani's excellent book An Introduction to Computational Learning Theory).

In fact, even if we restrict the underlying distribution on examples to be the uniform distribution, the fastest algorithm for learning DNF formulas runs in quasi-polynomial time (a result due to K. Verbeurgt-- the main idea being that only terms of logarithimic length have a chance at being satisfied, so longer terms can be ignored).

If, however, we allow the learner to make queries to the unknown DNF formula, i.e. if the learner can choose any input x and ask for the value of the DNF formula evaluated on x, then the learner can succeed in polynomial-time.

The solution, due to Jeff Jackson in 1994, shows how to learn polynomial-size DNF formulas with respect to the uniform distribution in polynomial-time (again assuming the learner has query access to the unknown DNF). His algorithm, which he has called the Harmonic Sieve due to its use of Fourier analysis, builds on work due to Blum, Furst, Jackson, Kearns, Mansour, and Rudich (``Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis'') which showed that for any DNF formula with s terms, there exists a parity function which agrees with the DNF formula on roughly a 1/2 +1/s fraction of inputs.

The next step of the algorithm involves a novel application of Boosting algorithms (see this post for more on Boosting) for combining these parity functions to obtain an accurate hypothesis. The output of the Harmonic Sieve is not a DNF formula but a threshold of parity functions.

The Harmonic Sieve is one of the rare examples in computational learning theory of a polynomial-time algorithm for an expressive concept class. It is natural to ask whether the queries are essential for the algorithm. Unfortunately it seems like the answer is yes-- we do not know how to learn decision trees or even juntas (both strictly weaker concept classes than DNF formulas) in polynomial-time with respect to the uniform distribution unless the learner has query access to the unknown function. Removing the dependence on queries would be a real breakthrough.

By the way, the interface on blogger.com is worse than I ever could have imagined. Apologies in advance for formatting errors.

Favorite Theorems: Parallel Repetition

July Edition

Consider a simple Arthur-Merlin game: Arthur probabilistically chooses a string r sends it to Merlin who responds with y and then Arthur runs some algorithm A(r,y) to decide whether to accept. Merlin's goal is to achieve the highest acceptance probability possible p for Arthur. Suppose we run the game twice in parallel, Arthur sends r₁ and r₂ and Merlin sends y₁ and y₂ and Arthur accepts if A(r₁,y₁) AND A(r₂,y₂). The highest possible acceptance probability will be p².

Now consider the MIP model with two Merlins M₁ and M₂ who cannot communicate with each other. Arthur sends u and v to M₁ and M₂ respectively who respond with y and z. Arthur accepts based on some function A(u,v,y,z). Once again M₁ and M₂ try to achieve the highest possible acceptance probability p. Now we run the game twice in parallel, Arthur sending u₁ and u₂ to M₁ and v₁ and v₂ to M₂ receiving y₁ and y₂ from M₁ and z₁ and z₂ from M₂ and accepting if A(u₁,v₁,y₁,z₁) AND A(u₂,v₂,y₂,z₂).

One might assume that the best the provers can achieve is p² (an assumption in fact made in an early paper co-authored by a certain weblog author) but in some circumstances the provers can do better. However Ran Raz shows that if p is less than 1, one can get an exponential decrease in p with a polynomial number of parallel rounds in

A Parallel Repetition Theorem by Ran Raz

This paper settles one of the more perplexing aspects of multiple prover proof systems with a highly complicated proof. The result also plays a critical role in reducing the number of queries in probabilistically checkable proof systems which led to some optimal approximation bounds.

As a side note I am off on vacation tomorrow and Adam Klivans will guest blog in my absence. Enjoy.

Wisdom of Crowds

Keeping with this week's theme of prediction, I just finished reading The Wisdom of Crowds written by New Yorker writer James Surowiecki. The book makes the case that large groups can make great decisions, often better than any individual in a group, if three conditions occur:

1. diversity of the members of the group,
2. independent opinions of the group members, and
3. a method for aggregation of the opinions.

Surowiecki's very readable book gives many examples where group decisions do quite well (sports betting, Google's search techniques based on other's web pages, Linux) and where group decisions fail (stock market bubbles, committee meetings, strong CEOs).

Chapter 8 is devoted to science and how many widely spread scientists developing and criticizing various theories lead to explosive growth in our understanding. He also notes that this ideal world has its flaws as unknown researchers have a harder time selling their work than more established scientists.

I don't agree with all the conclusions drawn by Surowiecki but he does lay out what we need to do and not do to benefit from the pooled knowledge of a group. We can also draw lessons in computer science as computation and information gets more distributed that we need to integrate to find the best solutions we can.

Fun with Information Markets

Just over a year ago the Department of Defense cancelled their program on using markets to predict future world events, an overreaction that stopped funding a potentially powerful prediction tool. Robin Hanson has a comprehensive web page giving a history and plenty of links.

Information markets live in limited academic-based markets like the Iowa Electronic Market and offshore sites like Tradesports. For example the current price on Tradesports for Bush winning the election is 51.5 which translates to a 0.515 probability that Bush will win indicating a very close contest.

For each state, Tradesports has a security on whether Bush will win that state. They also have some bundles of states. The price for Florida is 50.1, Ohio 55.4 and Bush winning both Florida and Ohio is 47.1. This gives a surprising correlation between Florida and Ohio. If you believe the theory there is a very high 0.94 probability that Bush wins Ohio given that he wins Florida and with a 0.89 probability these two very different swing states will go the same way.

Tradesports gives David Vitter a 59 percent chance of becoming a senator from Louisiana. David Vitter is the brother of CS theorist and former SIGACT chair Jeff Vitter.

Micromorts

Currently on airplanes children under two can ride free by sitting on a parent's lap. The FAA is considering whether to require such children to have their own seat in a child seat similar to the ones most states require for cars. Sounds reasonable? One argument against goes as follows: If we require parents to pay for a seat for a children there is a chance they will drive instead greatly increasing their risk.

How can we evaluate risk? Decision scientists have developed a measure called micromorts (μmorts). A μmort is a one-millionth chance of death. Sounds gruesome but by counting micromorts we can analyze the right choices to keep the most people alive.

All of three lap children have died in airplane crashes where their parents survived since 1987. The average driver runs the risk of about .02 μmorts/miles. If the average car trip is say 500 miles that translates to about 10 μmorts for each child in the car. Three laptop children have died in airplane crashes where the parent has survived since 1987. This translates to the equivalent of 300,000 car trips or about 15,000/year. About 6 million children ride on laps on airplanes each year, so if more than 0.25% of them were to ride in a car instead because of the higher prices, we would about cost lives by requiring safety seats on planes. My numbers, drawn from various internet sources, don't tell the whole story but nevertheless we can and should do a full analysis before setting policy.

It would be nice to have a list of various activities and how many μmorts they use, say you feel like parachuting, you can get an idea of how dangerous it is compared to say riding a bicycle. But we don't get such lists and people have to use their own judgments and often make the wrong decisions. We can also give a cost amount to a μmort; how much is it worth to save lives?

By finding statistics online you can calculate the risks in your various activities. You need to use about 3 μmort/day on average to keep a 10% chance of accidental death in your life. Spend them wisely.

When to Announce?

Suppose you have some partial solutions of a popular problem. At what point do you announce your results? If you announce your partial results you run the risk of someone else taking your ideas and solving the full problem and you won't get as much credit as you deserve. If you wait and try to extend the work yourself someone else might get the same results you already have and you'll lose or at best have to share the authorship.

If you are completely altruistic you should announce your progress as this will best advance science quickly. But as in the end you need to worry about your own publication record, particularly for a young researcher, the answer isn't so clear. Of course it depends on many factors including your belief that you or others could extend the work as well as when the next conference deadline occurs.

Oddly enough before the internet (in the eighties) such decisions were easier. You could write up a technical report to establish your result and you would have months before your work spread throughout the community. This gives you plenty of time to try and extend the work. The quick spread of information not only improves collaborative work as it does, but forces us to make decisions that we could avoid in the past.

Small Circuits

Fix a constant k. In 1982 Ravi Kannan showed that some Σ₂^p∩Π₂^p language must not have n^k-size (nonuniform) circuits. Here is a proof sketch: A simple counting argument shows there is a function that depends only on the first 5k log n inputs that is not equivalent to a n^k-size circuit. Just by writing out the quantifiers in Σ₄^p you can compute the lexicographically first such function. Now we have two cases:

1. If SAT does not have polynomial-size circuits then SAT then Σ₂^p∩Π₂^p which contains SAT does not have n^k-size circuits.
2. If SAT has polynomial-size circuits then Σ₄^p=Σ₂^p∩Π₂^p (Karp-Lipton) and thus Σ₂^p∩Π₂^p does not have n^k-size circuits.

This is a wonderful example of a non-constructive proof and giving an explicit Σ₂^p∩Π₂^p language without quadratic-size circuits is open. With better known collapses we can improve the result from Σ₂^p∩Π₂^p to S₂^p.

Vinod Variyam recently observed that the class PP which is not known to contain S₂^p also cannot have n^k-size circuits. Here is his proof: If PP has n^k-size circuits then PP is in P/poly which implies the polynomial-time hierarchy and in particular Σ₂^p is in MA which is in PP which has n^k-size circuits contradicting Kannan.

Read Variyam's paper for details and references.

Larry Stockmeyer

We lost a great complexity theorist over the weekend. From Phokion Kolaitis:

It is with great sadness that I write to inform you that Larry Stockmeyer passed away. He died at his home as he had wished when he fell terminally ill a few weeks ago.

Larry was one of the pioneers of computational complexity who made fundamental and lasting contributions to the field. His death creates a void in our community that cannot be filled.

Indeed Stockmeyer developed many of the important early concepts in complexity such as alternation and the polynomial-time hierarchy, concepts that have laid the foundation for many important works in computational complexity. He had a number of great results throughout his career in complexity and nearly all areas of theoretical computer science. Our community has lost one of its giants.

Strangers in the Same Place

Professor X and Professor Y from the same university attend the same conference. At the end of the conference, Professor X says in a surprised tone "That's the most time I have talked with Professor Y all year." He shouldn't be surprised; this is a story I've heard over and over again (and have even told myself).

A professor's life has many responsibilities. Teaching and research of course but also paper writing, grant proposals, meeting with students, and administrative tasks including seemingly endless committee meetings. When I visit another university I leave most of these responsibilities behind so I can focus on research. I also expect the people who invited me to make time in their schedules so we can work together. That way even a short visit can be quite productive.

As the length of the visit increases it becomes harder to avoid these other responsibilities and the amount of research time per day decreases. In the extreme, two people who work at the same university for years end up spending very little time talking research together.

This explains why teleconferencing will never replace traveling no matter how technologically advanced. The social requirements of a short visit require people to spend time together in ways a teleconference cannot. What teleconferencing will do is "allow" me to attend those endless committee meetings wherever I am.

Journal Rankings

An assistant professor writes

In case you need a topic for your weblog: what about journal rankings for theoretical computer science journals? I was looking for something like that for my tenure portfolio. The only web-info I found on the topic was here whose reliability is hard to judge.

Thanks, I am always looking for topics. Journal rankings do not have as strong a perceived ranking in computer science due to the import we give to conferences. Nevertheless, deans like to classify journal articles in computer science like they do for other fields and ask for a ranking.

Here's how I rank theory journals.

1. Journal of the ACM.
2. SIAM Journal on Computing.
3. A large equivalence class of every other major theory journal.
4. Information Processing Letters which publishes short articles that don't merit publication in the above.

Any ordering of journal consistent with this list is okay though even here we have considerable fluctuation. In most theory journals the editor-in-chief rarely overrules the associate editors recommendations and thus have about the same average acceptance criteria. JACM has the tightest quality controls but still occasionally publishes some weaker papers and quite a few mediocre papers appear in SICOMP though I still rate it higher than the rest.

Special issues rank higher, especially those devoted to the best papers of a strong conference. On the other hand, I put no faith on the quality of theory papers that appear in non-theory and especially non-CS journals no matter how they are ranked in their respective field. More than a few rather weak CS papers have appeared in Science, the gold standard for many other scientific disciplines.

NSF Budget

The US House Appropriations committee has passed the NSF budget at a 2% ($111 Million) cut. There are still many more phases in the budget process to go but this cannot be viewed as good news for science. For various reasons, the NSF is lumped in the same budgetary group as Veteran's Affairs and the veterans lobby better than scientists.

The American Institute of Physics has a detailed report and perspective. Here also is a statement from the Coalition for National Science Funding and some comments from the Computing Research Policy Blog.

Favorite Theorems: Superlinear Bounds on Branching Programs

June Edition

Branching programs give us a nice way to model time and space bounds for Boolean functions in a simple non-uniform model. A branching program is a directed acyclic graph where every non-leaf node is labeled by a variable and has two edges labeled One and Zero. All of the leaves are labeled Accept or Reject. Given an input, one follows a path taking the One edge on a node labeled i if the ith input bit is one and the Zero edge otherwise.

The depth (length of the longest path) of the branching program represents time and log of the size represents space. Lower bounds on branching programs give us lower bounds on unrestricted computation.

In 1999, Miklós Ajtai gave the first polynomial-time computable Boolean function for which any subexponential-size deterministic branching program requires superlinear length.

A Non-Linear Time Lower Bound for Boolean Branching Programs by Miklós Ajtai In other words there exists a specified easily computable function that cannot be solved in linear-time unless one uses nearly linear space.

Ajtai creates a function based on quadratic forms and builds on techniques used in his slightly earlier paper.

For more details I recommend the paper Time-space tradeoff lower bounds for randomized computation of decision problems by Beame, Saks, Sun and Vee which gives a nice history of the problem and the techniques to solve it and generalizes Ajtai's work to the probabilistic setting.

Carl Smith 1950-2004

Maryland Professor Carl Smith passed away last night losing his year and a half battle with brain cancer. He was an expert in inductive inference and an active member of the computational learning community. He traveled extensively making many connections in Holland, Germany, Japan and especially Latvia where he is a foreign member of the Latvian Academy of Science.

Carl Smith also played an important role in the computational complexity community. He organized conferences in the early 80's at Perdue and Maryland on Recursion Theoretic Aspects of Computer Science, precursors to the current IEEE Conference on Computational Complexity. He also co-organized the third Complexity (then called Structures) conference in Georgetown in 1988.

Carl was a colleague and a good friend. We both had sabbaticals in Amsterdam in 1996-7, wrote some papers together and often visited each other afterwards. We shared a love of beer and baseball; I would plan my trips to Maryland around the Orioles home schedule.

I always enjoyed the time I spent with Carl and the many interesting discussions we've had. I, my family, and the entire theory community will miss him greatly.

Extracting Randomness

In this post I will describe some recent results in extracting randomness in terms of Kolmogorov complexity since I (and some others) find Kolmogorov complexity more intuitive than entropy. If you would like a background in Kolmogorov complexity, here are some notes from a short course I taught a few years ago. I have not verified that the Kolmogorov results listed below actually follow from the extractor results but it should be straightforward.

Let K(x) be the smallest program generating x. We say a string x is random if K(x)≥|x|. For this post we ignore O(log n) additive factors to avoid various coding issues.

The optimal extractor paper of Lu, Reingold, Vadhan and Wigderson gives us the following. Let n=|x| and K(x)≥k. For all α>0, there is a polynomial-time computable f such that f(x) outputs a polynomial list of strings of length (1-α)k such that most of these strings are random. Using probabilistic constructions of extractors, if one only requires f to be computable, we can set α=0 for k≤n/2.

Barak, Impagliazzo and Wigderson have a new result (mentioned here) on extracting randomness from independent sources. For any constant δ>0, there exists a k polynomial in 1/δ and a polynomial-time computable f such that if we have x₁,…,x_k with

1. |x_i|=n for all i,
2. K(x_i)≥δn for all i, and
3. K(x₁x₂…x_k)=K(x₁)+K(x₂)+…+K(x_k) (the x_i's are independent)

then f(x₁…x_k) is a random string of length n.

Even more recently Barak, Kindler, Shaltiel, Sudakov and Wigderson have even a stronger result in this direction (mentioned here). For any constant δ>0, there exists a ε>0 and a polynomial-time computable f such that if we have x₁,…,x₇ with

1. |x_i|=n for all i,
2. K(x_i)≥δn for all i, and
3. K(x₁x₂…x₇)=K(x₁)+K(x₂)+…+K(x₇) (the x_i's are independent)

then f(x₁…x₇) is a random string of length εn.

Some Links and Random Thoughts

Michael Nielsen is in the midst of a long series of posts on Principles of Effective Research. Much of what he says seems obvious but the obvious often needs to be pointed out. Update 7/27: Complete Principles now available.

Nielsen mentions a new Erdös number eBay auction. We shouldn't use eBay to get people to pay us to do our research; that's what we have graduate students for.

A couple of computational geometers Suresh Venkatasubramanian and Jeff Erickson have been quite active on their weblogs. Check them out.

Finally for some music to prove theorems by, the BBC has put the entire Beethoven sonata cycle with Portuguese pianist Artur Pizarro online.

Why are CS Conferences so Important?

In nearly every scientific discipline conferences play a minor role. Most conferences have a few plenary speakers mixed with massive parallel sessions where nearly everyone who wants to present can present. The vetting of papers occurs in journals and the quality of one's research is measured much by which journal the work appears.

Computer science conferences are much more selective and the quality of one's work is measured by which conference the work appears. Journals play a far lesser role and many important papers never appear in a journal at all. Why is computer science different?

The answer is technological, namely airplanes. Before air travel conferences were much more difficult to attend and drew from a much more regional audience. Those who made the great effort and time to attend a conference were allowed to present. But presenting your paper at such a conference would not reach the majority of your colleagues. Journals were the most efficient way to broadly publicize your research and took on the more important role and have kept that role for historical reasons.

Computer science started as a field during the jet age. Many more people from a wider geographical base could attend a conference. One could now widely disseminate their research through conferences well before a paper appeared in a journal. Journals still played an important role for refereeing, editing and archiving but never held the importance in computer science as conferences do.

Since then we've seen another technological revolution and the internet easily trumps conferences for quickly distributing your results. Perhaps some new scientific field starting today would have a different internet-based system for judging research. But conferences will remain the primary focus for computer science as journals do for the older scientific disciplines.

Time and Space Hierarchies

What the world needs are the time and space hierarchies clearly spelled out in one place.

A function t is time-constructible if there is a Turing machine M such that on input 1ⁿ outputs 1^t(n) in time O(t(n)). Space constructible functions are defined similarly. All the natural functions are time and space constructible.

DTIME(t(n)) are the set of problems computable by a multi-tape Turing machine in deterministic time O(t(n)) on inputs of length n. NTIME (nondeterministic time), DSPACE and NSPACE are defined similarly.

Let t₁ and t₂ be time-constructible functions and s₁ and s₂ space-constructible function. We let "⊂" denote strict subset. A function f(n)=o(g(n)) if lim_n→∞f(n)/g(n)=0.

1. If t₁(n)log t₁(n)=o(t₂(n)) then DTIME(t₁(n))⊂DTIME(t₂(n)).
2. If t₁(n+1)=o(t₂(n)) then NTIME(t₁(n))⊂NTIME(t₂(n)).
3. If s₁(n)=o(s₂(n)) then DSPACE(s₁(n))⊂DSPACE(s₂(n)).
4. If s₁(n)=o(s₂(n)) then NSPACE(s₁(n))⊂NSPACE(s₂(n)).

The DSPACE hierarchy is straightforward diagonalization. For DTIME the proof is similar but we lose log t₁(n) in the simulation of a k-tape machine by a 2-tape machine.

Straightforward diagonalization does not work directly for nondeterministic computation because one need to negate the answer. For NSPACE we easily get around this problem by using Immerman-Szelepcsényi.

The NTIME hierarchy has the most interesting proof that leads to requiring the "+1" in t₁(n+1). This can make a big difference for t₁(n) larger than 2ⁿ².

An NTIME hierarchy was first proved by Cook and in the strongest form by Seiferas, Fischer and Meyer. We sketch a simple proof due to Zàk.

Let M₁,… be an enumeration of nondeterministic Turing machines. We define a nondeterministic machine M that acts as follows on input w=1ⁱ01^m01^k:

• If k<m^t₁(m) then simulate M_i on input 1ⁱ01^m01^k+1 for t₂(|w|) steps.
• If k=m^t₁(m) then accept if 1ⁱ01^m0 rejects which we can do quickly as a function of the current input size.

This machine uses time O(t₂(n)). If NTIME(t₁(n))=NTIME(t₂(n)) then there is an equivalent machine M_i using time O(t₁(n)).

Since t₁(n+1)=o(t₂(n)) we have for sufficiently large m,

1ⁱ01^m0 in L(M) ⇔ 1ⁱ01^m01 in L(M) ⇔ … ⇔ 1ⁱ01^m01^mt₁(m) in L(M) ⇔ 1ⁱ01^m0 not in L(M) a contradiction.

Bringing Families to Conferences

When we have a conference or a workshop in a tourist location, like Banff, many of the participants bring their non-computer scientist spouses and sometimes their whole families. I rarely do so. The main purpose in attending conferences and workshops is not the talks but to meet with your fellow researchers. The main purpose of a family vacation is to spend time with the family. These conflicting goals would make me feel guilty during the whole conference no matter how I split my time. Sometimes I will bring the wife or the family a week before or after or between conferences but conference time is science time.

Still I cannot fault my fellow scientists who bring their families to conferences. I would much rather they attend the conference with their families than not come at all. Every professional has a major challenge in balancing family and work life and they need to find the right mix that works for them.

Final Notes from Banff

Some final notes from the Banff workshop. First a few lemmas used in Wigderson's talk.

Lemma 1: Let G=(V,E) with n vertices and m edges and m≥4n. Let cr(G) be the number of edge crossings in any planer layout of G. Then cr(G)≥m³/64n².

Lemma 2 (Trotter-Szemérdi): Suppose we have a set of points P and lines L in the plane. Let n=|P| and m=|L|. Let I be the number of indices, i.e. the number of pairs (p,l) with p in P, l in L and line l contains the point p. Then |I| ≤ 4((mn)^2/3+m+n).

Guy Kindler talked about a brand new set of results with Barak, Shaltiel, Sudakov and Wigderson. Among other things they improve on the Barak-Impagliazzo-Wigderson result I mentioned earlier by showing that for any constant δ>0, one can take seven independent sources of n bits each with δn min-entropy and combine them to get O(δn) bits of randomness.

Mario Szegedy talked about his recent work showing that the quantum hitting time of a symmetric ergodic Markov chains is the square root of the classical hitting time, a result that becomes a powerful tool in developing quantum algorithms.

Update 7/12: Group Photo now online.

RESULTAPHOBIA!

A Guest Post by Bill Gasarch and Brian Postow

In the 1970's there was some hope that deep techniques from Computability theory might crack P vs NP. Some nice results came out of this (e.g., Ladner's theorem that if P ≠ NP then there is a set inbetween). Then the oracle results seemed to say these techniques (whatever that means) would not work.

In the 1980's there was some hope that deep techniques from Combinatorics might crack P vs NP. Some nice results came out of this (e.g., PARITY not in AC₀, and the monotone circuits lower bounds). Then the Natural Proofs framework seemed to say these techniques (whatever that means) would not work.

So where are we now? Fortnow and Homer's paper on the History of Complexity Theory seems to say that we have no ideas at this time. A recent talk at Complexity seemed to say "we didn't work on this aspect of the problem since, if we solved it, we would have P ≠ NP."

We as a community seemed to be afraid of big separation results. We are almost scared of working on hard problems since they might not pan out. Is this wise? There are stories (some apocryphal some not) about people solving problems because they didn't know they were hard. (Examples below)

I recognize that working on problems with little hope of success is dangerous. But to shy away from a line of research BECAUSE it may lead to a big result seems... odd.

EXAMPLE ONE: Neil Immerman tells a story about Robert Szelepcsényi. Szelepcsényi's result that Context Sensitive Languages are closed under complement was announced in an issue of EATCS (in the same issue, two other articles mentioned Immerman's own proof that NSPACE is closed under complement, an effectively equivalent result). Szelepcsényi was an undergrad at the time, and his adviser gave him the famous problem as a challenge, probably not really expecting him to actually solve it. He did solve it, perhaps because he was never told that it was an old open problem that others had failed to solve.

EXAMPLE TWO: A prominent researcher (who told me about this, so its verified) was working on Σ₂-SPACE(n) = Π₂SPACE(n) but stopped since it might lead to the absurd result that Σ₁-SPACE(n)=Π₁=SPACE(n).

DEBUNKING: There is a RUMOR that Umesh Vazarani would have had Quantum factoring in P but didn't get it since it was obviously false. He has denied this. (I put this in so that someone doesn't post a comment about it.)

Are there more cases of either people solving a problem because they didn't know it was open OR of people NOT working on a problem because they thought it was hard (and it wasn't that hard)? I'm sure there there are. If you know of any that have been verified please post to comments or email to gasarch@cs.umd.edu and postow@acm.org.

Gems of Additive Number Theory

Yesterday Avi Wigderson gave a talk entitled Gems of Additive/Combinatorial Number Theory where he presented three interesting results about the sizes of sets when you add all the possible numbers from one set with another.

Let A and B be subsets of an Abelian group G and define A+B = {a+b | a in A and B in B}. We define AxB as the same with multiplication when we work over a field. Let |A|=|B|=m.

1. Erdös-Szemerédi: Let A be a subset of the reals. Either |A+A|≥m^5/4 or |AxA|≥m^5/4.
2. Ruzsa: For all k, if |A+B|≤km then |A+A|≤k²m.
3. Gowers: Let E be a set of pairs (a,b) with a in A and b in B. Let A+_EB be the set of values a+b with (a,b) in E. For any δ and k, if |E|≥δm² and |A+_EB|≤km then there is an A'⊆A and B'⊆B with |A'|,|B'|≥δ²m and |A'+B'|≤mk³/δ⁵.

Later Russell Impagliazzo showed how to use finite field versions of these results in his upcoming FOCS paper with Barak and Wigderson. They show how to convert poly(1/δ) independent sources of distributions with δn min entropy to n nearly uniform random bits.

Howdy from Banff

Another fourth of July out of the states, this time at the Banff International Research Station (BIRS), a Canadian mathematical conference center similar in spirit to Oberwolfach and Dagstuhl. BIRS is hosting a workshop on Advances in Complexity Theory with a pretty impressive collection of researchers.

Today's talks focused on PCPs and their applications. Guy Kindler gave an interesting presentation on his work with Khot, Mossel and O'Donnell showing that under a few believable assumptions, the Goemans-Williamson Max-Cut approximation is optimal.

Took some time off to see Greece win Euro2004. Sorry Luis.

JCSS To Pay Editors, Possibly Referees

The Elsevier owned Journal of Computer and System Sciences will pay an honorarium of $100 to a cognizant editor for each paper handled. According to Editor-in-Chief Ed Blum the intent "is to establish the practice of compensating editors for their scholarly contribution to scientific publication and is a partial response to the complaint that we scholars do all the work and the publishers reap all the rewards. This practice will apply to Guest Editors of Special Issues. I am aware that it does not address the problem of journal pricing. I am still working on that. I am pretty sure that we can also give a $50, honorarium to referees, but am awaiting a final OK [from Elsevier] on that." (Thanks to Bill Gasarch for this information.)

Update 8/7/04: JCSS is rescinding this new policy of awarding honoraria for papers handled.

Lessons from Economics

Rakesh Vohra pointed me to some interesting takes on journals in economics. Economics runs on a different model than computer science; conferences are less selective and economists are judged more on the quality of the journals where their papers appear.

The Berkeley Electronic Press offers an electronic subscription-based system for their journals. Look at the B.E. Journals in Theoretical Economics. Here you submit to all four journals at once and your paper gets accepted to one with the highest quality rating that the editors decide is appropriate for your paper.

NAJ Economics is Not A Journal but offers reviews of economics papers. One cannot submit papers but a strong rotating editorial board just finds papers freely available on the internet and post reviews of those they feel are worthy. From the FAQ:

The purpose of NAJ Economics is to work towards replacing the existing commercial system of scientific publication. Because papers published in printed journals are less available than working papers, which are freely available on the Internet, publication in the traditional sense inhibits scientific communication. It also generates additional costs as most printed journals charge high subscription fees, in particular to libraries. However, it does serve the useful purpose of certifying the scientific quality of published work. It also assures that articles remain available regardless of the idiosyncrasies of individual websites and links. Our immediate goal is to provide some of the useful certification functions of current journals at a negligible cost by reviewing papers that we think have substantial merit.

I have some quibbles about the service. Without submissions a lesser known author might have trouble getting his paper reviewed. The editors will have a nightmare keeping links up to date, especially since they seem to link to papers on people's homepages. They also don't have the ability to force improvements in the papers they review the way a journal can.

But perhaps in this age of the internet one needs to separate the refereeing and distribution aspects of a journal. NAJEcon is an interesting step in that direction.

FOCS Accepted Papers

The list of accepted papers for the upcoming FOCS conference in Rome is out. [Thanks Suresh]

A few complexity papers to note: Ran Raz finds easy languages with no log-depth multilinear circuits. Andris Ambainis and Mario Szegedy have separate papers showing nice applications of quantum "random" walks. Barak, Impagliazzo and Wigderson show how to do extract nearly uniform distributions from multiple independent random sources as opposed to one random source and a few truly random bits. And lots more.

Don't Make it Too Easy or Too Much

Two easy ways to improve your paper but lessen your chances of acceptance at a conference: Add more results and simplify your proofs. Adding a result could only increase the usefulness of a paper but program committees see many results in a paper and conclude that none of them could be very strong. One of our students a few years ago had a paper rejected at STOC, he removed one of his two main theorems and won the best student paper award at FOCS.

Given the same theorem, the community benefits from a simple proof over a complicated proof. Program committees look for hard results so if they see a very simple proof, it can count against you.

You need to play the game. If you have many results depending on the situation, you can either split the paper or highlight one result and bury the others. It's a bit unethical to use a hard proof where you know an easy one but many people make an easy proof look harder by adding an unnecessary level of detail or proving a more general but less interesting theorem.

You do what you need to do, within ethical standards, to get your paper accepted. After you get it accepted, remember you have a rewrite for a proceedings version to get the paper written the way it should.

Note from Vereshchagin

I received the following from Nikolay Vereshchagin.

The combinatorial question I have discussed last summer at the rump session at Computational complexity (about partitioning a planar set into a small number of uniform parts) has been answered almost immediately by Ilan Newman and Gabor Tárdos. They have found a pure combinatorial proof. Recently I have written a note on the subject.

Complexity Conference Recap

The Complexity Conference ended yesterday. You can already find the papers on the IEEE site and if you don't have access you can often find versions of the papers on author's homepages.

We had a strong turnout and a nice variety of papers on many different areas of complexity with particularly strong showings in quantum complexity and structural complexity making a comeback.

Amit Chakrabarti asked about group isomorphism. Arvind and Torán showed that solvable group isomorphism is "almost" in NP∩co-NP.

Although I did not have my own talk in the conference, I presented a paper by Buhrman and Torenvliet since they unfortunately could not be in Amherst. I like giving talks on other people's work since you can be honest about the strengths of a paper without having to brag. My favorite result in their paper showed that if you take a many-one complete set for EXP, remove any easily computable set of subexponential size, what remains is Turing-complete for EXP. The proof is a clever recursive algorithm using the set itself to find safe places to map the reduction.

Next year we have our 20th conference in San Jose followed by Prague in 2006.

Rump Session Redux

This week I am in Amherst at the University of Massachusetts for the 19th IEEE Conference on Computational Complexity. Lots of fun papers and complexity theorists. This is complexity heaven.

Like last year, we had a number of interesting new results described at the rump session. Let me describe a couple of them to you.

Scott Aaronson follows up on his guest post about the complexity of agreement. Aumann has a famous theorem that two players who communicate cannot agree to disagree on the probability of some state of the world; after some discussion they will converge to a common probability. Aaronson looked at the complexity of this process and found that convergence comes relatively fast. He defined a notion of (ε,δ)-agreement where the probabilities are within ε of correct with a confidence of 1-δ and shows that such an agreement happens after polynomial in 1/ε and 1/δ rounds.

Neeraj Kayal looked at the complexity of the problem #RA, the number of automorphisms of a ring given by generators. He showed that factoring and graph isomorphism reduce to #RA and #RA sits in AM∩co-AM. As an open question he wondered about the complexity of determining whether a ring has nontrivial automorphisms where one is given tables for addition and multiplication. It remains open even for commutative rings.

Update 6/23: Kayal tells me I didn't accurately capture his rump session talk and sent me the following summary.

We have an algorithm that determines whether a ring has a nontrivial isomorphism even when the ring is given in the form of generators for its additive group and pairwise product of the generators expressed as a linear combination of the generators. (We get this by getting a characterization of all finite rigid rings and it turns out that we can test whether a ring follows this characterization or not without solving integer factoring.) Unfortunately however we do not know of a reduction from Graph automorphism to ring automorphism although we have found a cute reduction from Graph Isomorphism to Ring Isomorphism!

The open problem that I would love to solve is to decide whether two rings are isomorphic or not when they are given in the form of tables (one table each for addition and multiplication.) I do not know how to do this even for commutative rings.

Shimon Even (1935-2004)

Shimon Even was born in Israel on June 15th, 1935. He died on May 1st, 2004. In addition to his pioneering research contributions (most notably to Graph Algorithms and Cryptography), Shimon is known for having been a highly influential educator. He played a major role in establishing computer science education in Israel (e.g., at the Weizmann Institute and the Technion). He served as a source of professional inspiration and as a role model for generations of young students and researchers. Two notable avenues of influence were his PhD students and his books Algorithmic Combinatorics (Macmillan, 1973) and Graph Algorithms (Computer Science Press, 1979).

From a memorial page by Oded Goldreich.

Visa Problems Continue

Wisconsin Professor Dieter van Melkebeek has a paper at the ICALP conference but cannot go to Finland to present it. Why not? Delayed processing of his green card application has led to problems with his current visa putting him in some temporary state of visa hell. Dieter would actually have no trouble attending ICALP; he would just have problems coming back.

Dieter is one of many stories of people changing travel plans and missing conferences because of America's tougher requirements and slower processing of foreign immigration applications. An Indian graduate student with a paper at next week's Complexity conference could not get a visa in time. I would not be surprised if many graduate students will not start the fall semester on time awaiting my government's blessing to come to study here.

This is a story I have told before and will likely tell again. I understand the need for security but most scientific progress happens through collaboration and preventing or delaying this collaboration holds back the advancement of knowledge. Not since the 80's have we seen such a limitation on traveling though this time in reverse. During the cold war several countries would not let many of their best scientists out; these days we don't allow many of the world's best scientists in.

Riemann Hypothesis and Computational Complexity

A commenter asks a good question for a bad reason: Would a proof of the Riemann Hypothesis have any impact on complexity theory?

Rather surprisingly the answer is yes, particularly in the area of computational number theory. In the most famous example, Gary Miller in 1975 gave a polynomial-time algorithm for primality whose correctness could be proven by assuming the Extended Riemann Hypothesis (ERH). Of course in 2002 we had a polynomial-time primality algorithm with no assumption. However the original analysis of the algorithm gave a constant which depends on how ERH is resolved.

There are still many other problems in computational number theory that require ERH. For example, according to Eric Bach, the only polynomial-time algorithm computing square roots modulo p, when p is large relies on ERH. "The idea is to combine an algorithm that uses a quadratic nonresidue, such as Shanks's algorithm (this in Knuth v. 2 I am pretty sure) with a bound on the least quadratic nonresidue mod p (e.g. in my thesis it is proved to be <= 2 (ln p)^2 if ERH is true)."

Special Issues

Journals dominate the non-research talk at STOC. We had a long discussion at the business meeting about the special issue of STOC. A little background: For the past 24 years the STOC program committee selects 6-10 papers from the conference and one of the PC members serves as editor of a special issue of a journal where all these papers are invited to appear. The Journal of Computer and System Sciences (JCSS) has always hosted the special issue for STOC as well as a few other conferences including FOCS and Complexity.

JCSS became an Elsevier journal a few years ago when Elsevier bought Academic Press. Elsevier has come under attack over the past few years in our field for their pricing policies, an issue discussed in this weblog before. Some editorial boards have resigned and many others are considering it. The current PC chair (and fellow U. Chicago Professor) Laszlo Babai has strong negative feelings towards Elsevier and spearheaded the issue at the conference.

The STOC Executive Board has final say on the future of the special issue but based on the business meeting discussion, the special issue for STOC will likely move to SIAM Journal on Computing (SICOMP) perhaps as early as this year.

My concern, which I expressed at the meeting, is that we already have a culture where too many papers never appear in a journal, i.e., never get written with full proofs and go through a rigorous refereeing process. The more negative press we give towards journals the more likely authors will take the easy solution of no journal. When was the last time you downloaded the journal paper never written?

Update 6/18: Hal Gabow, chair of SIGACT, has set up a website containing additional information on the meeting and subsequent procedures.

STOC Business Meeting

STOC got underway Sunday with a full slate of talks and a lengthy business meeting last night. I do not have time for a long post now so I will just bring you up to date on some facts from the business meeting.

The attendance was 261 (242 paid + 19 local helpers). Later today I will update the contest post with the results.

STOC 2005 will be in Baltimore May 22-24 and STOC 2006 will be in Seattle. There were announcements of three new journals, the previously mentioned ACM Transactions on Algorithms and two on-line open-access journals Logical Methods in Computer Science and Theory of Computing.

Most of the business meeting was devoted to the future of the special issue and I left around 11 PM last night before this discussion had ended. This discussion will require a post of its own in the near future.

STOC runs through Tuesday. Much more as the week goes on.

Favorite Theorems: Connections

May Edition

I have always loved results that find connections between previously-thought different areas of complexity. This month we highlight one of the best.

Extractors and Pseudorandom Generators by Luca Trevisan

Informally a pseudorandom generator takes a small random seed and generates strings that can fool every probabilistic algorithm. To describe an extractor we start with some distribution D over strings of length n. Let p be the maximum probability of any string in D and let k = log(1/p). An extractor uses D and a small number of truly random bits to create a new uniform distribution of strings of length close to k.

Both pseudorandom generators and extractors have many uses in complexity and many papers in the field show various constructions to improve the parameters of both. Trevisan showed that one can view any pseudorandom generator as an extractor and then derives better extractors from known pseudorandom generator constructions.

Pseudorandom generators fool resource-bounded algorithms while extractors nearly uniform distributions in an information-theoretic sense. That makes this connection all the more amazing. Trevisan's paper has affected the how researchers think about and prove results in both areas.

Win a Gmail Account

My first weblog contest. Guess the paid attendance (including students and postdocs) at next week's STOC conference. Closest to the correct answer receives an invitation for a Beta Gmail account (donated by weblog friend Meridel).

Rules: Send your guess in the subject of an email to stocguess@fortnow.com. Include your name and email in the body of the message. One guess per person. All guesses must be sent by Saturday noon CDT. Closest guess to the attendance announced at the business meeting Sunday night will receive an invitation to open a Gmail account (still in Beta testing). In case of tie, first closest guess received will win. Anyone involved in STOC organization is ineligible. Not responsible for delayed or undelivered email. My decision of the winner is final. Contest not sponsored or affiliated with Google or ACM SIGACT.

Good luck.

Results Update 6/14: Total paid attendance was 242. The closest at 254 was Nanda Raghunathan, second place at 223 was Kamalika Chaudhuri and third at 265 was Chandra Chekuri. We have some extra invites so we've decided to give gmail accounts to all three. Congratulations and thanks to everyone who participated.

Professional Societies

Professional Societies perform valuable roles in academics. They give awards, sponsor conference and publish reasonably-priced journals as well as bulletins, newsletters and reviews. Societies disseminate information among researchers about future activities and the state of the field. They form an advocacy group representing the scientists in government and universities. Most importantly they give a focal point that lets us identify as a community.

Unfortunately in theoretical computer science no single group plays all these roles and thus one interacts with a large number of professional societies during an academic career. Let's look at some of them.

First most comes the Association for Computing Machinery (ACM) as the largest society devoted to computer issues. ACM tries to cover the entire computing profession so computer science research issues do not get center stage. They do publish several journals and give many of the important awards such as the Turing award.

ACM has a number of special interest groups (SIGs). SIGACT, the Special Interest Group on Algorithms and Computation Theory, is the main organization devoted to theoretical computer science in the US. They sponsor STOC and other conferences and publish SIGACT News. Many theorists join SIGACT without joining ACM.

The IEEE Computer Society also deals with computer issues and has a Technical Committee on Mathematical Foundations of Computer Science that sponsors conferences including FOCS and Computational Complexity. Why do we need both a Computer Society and ACM and a SIGACT and a TC-MFCS? Perhaps for the competition?

None of these societies serve as a strong advocate for computer science research and so we have the Computing Research Association. The CRA has as its members not individuals but academic departments and research labs. They have a newsletter, advocate and keep us informed on government policy on computer science, and collect information such as the Taulbee Surveys giving salary and job information in CS research. The CRA also has a strong focus on women's issues in CS research.

Let's not forget the Society for Industrial and Applied Mathematics (SIAM) that helps sponsor some conferences (SODA) and publishes the well-respected Journal on Computing.

The European Association for Theoretical Computer Science (EATCS) covers not just Europe but captures theory from an international perspective. They sponsor conferences like ICALP and publish a hefty bulletin three times a year. Also many countries have their own computer science and/or theoretical computer science societies.

Then based on my research interests I have now or at some time been a member of AMS, MAA, ASL, SIGecom and the Game Theory Society. Where does it all end?

BEATCS Complexity Column

With the June issue, Jacobo Torán takes over the editorial duties of the BEATCS Complexity Column. Following with tradition, he wrote his first column, Space and Width in Propositional Resolution. A strong start to what should be a great run of columns.

Survey Papers

Let's end this week how we started it, with a survey paper. Luca Trevisan has recently posted on ECCC a new survey Some Applications of Coding Theory in Computational Complexity. The survey gives a rather in-depth look at several different types of codes with some connections to private information retrieval, average-case complexity and probabilistically checkable proofs. Trevisan gives a broader and more in-depth look at coding theory than an earlier yet also excellent survey by Madhu Sudan focusing on list decoding.

Survey papers play a valuable role in our field. As computational complexity has broadened over the years, one cannot hope to keep on top of all of the many areas. A survey paper written by an expert in the field can perform many valuable tasks including

• Putting the main results of an area in a common framework. Early work often uses different notation and definitions making it hard to compare one paper to another. Fixing the notation and definitions allow us to easily compare different results. A well-liked survey can also influence future notation.
• Proofs get easier over time and a survey can give easier-to-follow proofs of old results. A survey can also develop a common proof technique useful for many result in the area.
• Giving the author's informed opinion to the importance of different results in an area.
• Stating open problems and directing future research in that area.

In case I've managed to put the survey bug in you, here are two topics where we've seen several recent research papers but lack good surveys that I know of.

1. The complexity of Nash Equilibrium
2. ε-biased Sets

Complexity Registration Deadline

Tomorrow is the last day for early registration for this year's Complexity Conference in Amherst. I promise a good time will be had by all.

IEEE Fellowship at the State Department

Are you an American IEEE member? Now you can help guide American foreign policy. IEEE-USA has announced an Engineering and Diplomacy Fellowship where IEEE members can serve as a Fellow in the U.S. State Department and continue to advise them afterwards. These fellowships are being offered for a few professional societies; perhaps the ACM should try to get in on this.

Some more background from FYI.

Impagliazzo's Five Worlds

Boaz Barak in a comment last week mentioned one of my favorite survey papers, Russell Impagliazzo's A Personal View of Average-Case Complexity presented at the 1995 Complexity Conference. In that paper he describes five possible worlds and their implications to computer science.

• Algorithmica: P = NP or something "morally equivalent" like fast probabilistic algorithms for NP. This was the world I described last week but looking back at Impagliazzo's paper, he does a nicer job.
• Heuristica: NP problems are hard in the worst case but easy on average.
• Pessiland: NP problems hard on average but no one-way functions exist. We can easily create hard NP problems, but not hard NP problems where we know the solution. This is the worst of all possible worlds, since not only can we not solve hard problems on average but we apparantly do not get any cryptographic advantage from the hardness of these problems.
• Minicrypt: One-way functions exist but we do not have public-key cryptography.
• Cryptomania: Public-key cryptography is possible, i.e. two parties can exchange secret messages over open channels.

Impagliazzo does not guess which world we live in. Most computer scientists would say Cryptomania or Minicrypt.
The paper goes on to give one of the better justifications for Levin's definition of average-case complexity.

Visas and Titles

Thanks to Technorati I can track who links to this weblog. Recently an Indian student Nitish Korula started a new blog Pseudo-Random Thoughts where he describes the trials of getting a visa so he can start grad school at Illinois in the fall. Good luck Nitish, we're rooting for you.

Meanwhile I agree with Will Baude at Crescat Sententia that most U. Chicago undergrads address faculty as "Professor" rather than say "Mr. Fortnow" as is the official Chicago custom. A decade ago I was more likely to get "Mr. Fortnow" which I never loved since it actually feels more formal than Professor or Doctor.

Graduate students as well as my colleagues call me "Lance," at least to my face. First year grad students sometimes take time to grow out of addressing professors as "Professor." I had this problem myself way back when. A fellow student couldn't shake the professor habit until he started playing sports with them. You just can't say "Throw me the ball, Professor Leighton."

In the end I don't really care that much what you call me. However I do enjoy those letters from Germany that covering all the bases address me as "Herr Dr. Prof. Fortnow."

What if P = NP?

A New York Times essay looks at the hardness of understanding math. The essay quotes from the book The Millenium Problems by Keith Devlin which describes the seven million-dollar Clay Mathematical Institute Millenium Problems including the P versus NP question. So I took a peek into Devlin's book.

Devlin doesn't hide his feelings about the P versus NP problem as "the one most likely to be solved by an unknown amateur." He does make a point that if P = NP we can break RSA and "the current dependence of the Western economies on secure communications over the Internet demonstrates just how high are the P = NP stakes."

Let's play make believe and assume P = NP in a strong way, say that we can find satisfying assignments of Boolean formula in nearly linear time with small constants. It will have a dramatic influence on the Western economy but not at all in the way Devlin perceives. We'll lose public-key cryptography but what we will gain from it will make the whole internet look like a footnote in history.

Learning becomes easy by using the principle of Occam's razor--we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of weather and earthquakes and other natural phenomenon.

Everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I'm just scratching the surface.

P = NP would also have big implications in mathematics. One could find short fully logical proofs for theorems but these fully logical proofs are usually extremely long. But we can use the Occam razor principle to recognize and verify mathematical proofs as typically written in journals. We can then find proofs of theorems that have reasonably length proofs say in under 100 pages. A person who proves P = NP would walk home from the Clay Institute not with one million-dollar check but with seven.

Informatics in Indiana

Many universities try to integrate information technology into many different disciplines usually through their computer science departments. Our neighbors to the east are creating a bold experiment in this integration, the Indiana University School of Informatics, with fastly growing departments spread over several of their campuses.

What is informatics? According to Indiana, Informatics is

• understanding the impact technology has on people.
• the development of new uses for technology.
• the application of information technology in the context of another field.

Their research groups already encompass quite a few areas including biological, chemical and social issues of information technology.

I visited the Informatics department in Bloomington a few months ago and sensed an excitement of growing a new discipline and bringing in many information technology researchers from different scientific disciplines. Note the real distinction between computer science that studies and improves the nature of computation and and informatics that aims for integration of information technology between various areas of study.

Mixing researchers from vastly different disciplines has had its shares of successes and failures and only time will tell how successful the Indiana experiment will become. But I'm extremely impressed with the commitment from the University and the state to this area of informatics and I expect we'll hear much more from Indiana in this area.

Comments

Some strong comments on Rocco's post on the recent Columbia theory day. In my own highly biased point of view, I find the study of efficient computation critical in a society that becomes continually reliant on computation on both explicit computers and implicitly in various biological, economic and physical systems. And how can one study efficient computation without developing reasonable models of computation and analyzing those models?

I don't mean to sound so altruistic; I get paid to do what I love. But I do truly believe one needs to understand the mechanisms that make up our world if we wish to improve them. I write this weblog, in part, to educate about the beauty and applications of theoretical computer science.

A comment about comments. I understand that many of you choose to post anonymously rather than register at Blogger and I'm fine with that. If you don't mind please add your name at the end of the comment. I like to know who is behind the comments and its useful to match up different comments by the same person. Of course, I'd rather get your comments anonymously than not at all.

Update 5/21: Stanley Fish, the departing Dean of the Arts and Sciences of University of Illinois at Chicago argues more for a separation of academic research and policy.

I exit with a three-part piece of wisdom for those who work in higher education: do your job; don't try to do someone else's job, as you are unlikely to be qualified; and don't let anyone else do your job. In other words, don't confuse your academic obligations with the obligation to save the world; that's not your job as an academic; and don't surrender your academic obligations to the agenda of any non-academic constituency � parents, legislators, trustees or donors. In short, don't cross the boundary between academic work and partisan advocacy, whether the advocacy is yours or someone else's. Marx famously said that our job is not to interpret the world, but to change it. In the academy, however, it is exactly the reverse: our job is not to change the world, but to interpret it.

A Part-Time Ph.D.?

A question from a reader (slightly edited):

There are no part-time (or even full time) Ph.D. programs at top universities in computer science or mathematics that can be completed by those who work full time. For various personal reasons I find myself in a position that requires me to work full time; however, I am passionate about theoretical computer science/mathematics. Unfortunately, most American schools do not accommodate Ph.D. students under these circumstances. Is this a decision based upon the assumption that those who work full time will not produce good/enough work, or is this a decision based, simply, upon the fact that professors want to work standard hours and teaching a course from 5:30 - 6:20 is quite non-standard?

Courses are not a major issue. The course requirements for a Ph.D. usually do not significantly differ than those for a Masters and many universities offer a Masters program in computer science for full-time workers. I do see two other major barriers to a part-time Ph.D.: Funding and Research.

Nearly all Ph.D. student get funded for tuition and some living expenses via a fellowship, teaching assistantship or research assistantship. Government agencies generally don't give fellowships to part-time students and a TA or RA requires about twenty hours a week, leaving someone who already has a full-time job with no time for actually completing the Ph.D.

But suppose you felt that a Ph.D. was worth the expense or were independently wealthy and for some reason still had to work a full-time job. Ph.D. level research in math and theoretical computer science requires intense background study and long stretches of thinking, understanding the problem and working through many different ideas until one actually makes significant progress toward original work. For this one needs time and the relationship is not linear. Someone who can spend forty hours a week focusing on research will be far more than twice as successful as one who can only spend twenty.

The dominant limitation on number of Ph.D. students in CS departments is funding. If you have a record that would have gotten you in to a top computer science department as a full-time Ph.D. student and you bring your own money to the table, I suspect at many schools you can work out a part-time schedule. But you'll find doing original research on a part-time basis a daunting if not impossible task.

Randomized Blogspace

A report from Theory Day co-organizer Rocco Servedio

On Friday May 14 a special Columbia/IBM Research/NYU Theory Day was held at Columbia University in New York City. The New York area theory days started at Columbia in 1982; this one was a special event to mark both the 25th anniversary of the CS department at Columbia and the 250th anniversary of Columbia University.

More than 280 attendees came out to hear four talks by outstanding theorists:

• Richard Karp (UC Berkeley): Current Challenges in Computational Genomics: Haplotyping
• Shafi Goldwasser (MIT/Weizmann): Proving Hard-Core Predicates using List Decoding
• Prabhakar Raghavan (Verity/Stanford): Finding Information in Networks
• Peter Shor (MIT): Quantum error correction and fault tolerant quantum computation

The day ended with a panel discussion on "The Future of CS Theory." Avi Wigderson (IAS) joined the four speakers for the panel, which was moderated by Mihalis Yannakakis (Columbia). Here is a brief summary of what was said.

Mihalis started things off by observing that over the past 50 years CS theory has enjoyed outstanding successes and has had tremendous impact on computing. Indeed, some of the successes were so profound that they gave rise to whole new fields of computer science (databases, security) that are no longer thought of as "CS theory". Mihalis asked each of the panelists to briefly give their views on the future of CS theory. Some highlights of what they said:

Avi observed that CS theory can (and should) have more impact on early education, starting in high school or even earlier. We can give important insights into fundamental ideas such as adversaries, randomness, learning, recursion, games, proofs, and "getting things done efficiently" (which Avi referred to as "the oldest profession in the world"). He also highlighted some specific goals for CS theory at this point, which included showing that BPP ≠ NEXP; coming up with non-natural proof techniques for circuit lower bounds; discovering new types of quantum algorithms; developing a general theory of what types of algorithms can give optimal approximation ratios; and proving that SL = L and that MATCHING is in NC.

Dick Karp warned against taking anyone's advice or predictions too seriously. That said, he advocated for a healthy balance between foundational questions at the core of CS theory and new questions that arise from the role of computation in the world and the sciences. He highlighted three areas of interest for the future: (1) the study of large scale distributed systems such as the Web, incorporating ideas from economics and game theory; (2) connections with areas of natural science, ranging from statistical physics to quantum mechanics to biology; and (3) the "new face" of AI in which stochastic and graphical models and statistical inference are playing a big role.

Peter also commented on the perils of predicting the future; we sometimes tend to think that there will be no more revolutionary ideas simply because we don't know what those ideas will be. But such ideas will come along from "out of the blue" as they always have. He noted that while past predictions for the future of CS theory have tended to be on the doom and gloom side, things have actually turned out pretty well -- there are interesting jobs and demand for theorists in industry; theory is more and more noticed and used by practitioners; and rather than becoming increasingly recondite and inward-looking, theory is building stronger connections with mathematics, physics, and other disciplines.

Prabhakar observed that what we think of as CS theory is really two main thrusts of work with some overlap: there is the theory of computation as an inherent phenomenon (i.e. when we study MOD 17 gates and what they can do even though nobody will ever build one), and the theory of computation as it is practiced (i.e. most of the world's cycles are spent making a billion people happy rather than crunching data for a few thousand scientists). The Web is a paradigmatic aspect of the second thrust; he noted that in this area economic factors may play a role at least as important as traditional resource bounds like time and space. Prabhakar also stressed the importance of backing up claims of practical relevance for our work (and, on an unrelated note, mentioned this weblog in a slide entitled "Randomized Blogspace".)

Shafi observed that CS theory is having an increasing impact on classical mathematics such as coding theory, number theory, and signal processing. On the other hand, we are also dedicating more energy (and having more success) in solving problems in the real world -- both of these trends are good signs for the field. She advised researchers to follow their own tastes and interests rather than anyone else's recommendations when it comes to "the next big challenge for the field."

After these statements the floor opened up to questions and discussion with the audience. A brief summary:

One questioner noted that the theoretical models of parallelism from 20 years ago don't correspond to how large distributed systems work now, and asked whether a similar phenomenon could be taking place with quantum computation -- are we studying the right model? Some panelists responded that while we aren't likely to end up with quantum computers that correspond exactly to quantum circuits, it seems likely that algorithms developed for the quantum circuit model will prove useful if/when we do get quantum computers in one form or another.

There was quite a bit of discussion about the role of CS theory in the undergraduate curriculum and what undergraduate CS majors should know about theory. Some panelists opined that NP-completeness, undecidability, models of computation, and algorithms are core topics that even high school students perhaps should know. A view emerged that there is real (potential) widespread interest out there in the "gems" of CS theory, and that we should do a better job of explaining what is fascinating and beautiful about our field to students.

In response to a question about the future status of the P=NP question, some panelists observed that other great research communities (mathematics, physics) have tussled with unsolved questions for centuries. We seem to be stuck right now, but on the bright side we have some understanding (natural proofs, for instance) of why we are stuck -- perhaps mathematicians should step back and think about why the Riemann hypothesis is still unresolved.

To close, here are three quotes lifted more or less verbatim from the panel discussion (but left anonymous here):

• "The future for DNA computation is dim" (in response to the question "What is the future for DNA computation?")
• "Polynomial time computation is a complex object to understand."
• "We are so much closer to understanding each other's talks than the mathematicians are."

Cornell's New President

On Friday I went to an alumni reception for Jeffrey Lehman, new president of Cornell University. Besides learning that the cinderblock dorms where I spent my freshman year are finally being demolished, a number of interesting aspects of university life came out of the question and answer session.

One question asked about lack of student activism on campus. Lehman acknowledged the problem outside of environmental issues and told of his plan for a mock presidential election at Cornell before the real election. This seemed like a weak answer--mock elections we had in high school. I doubt college students could get excited about a mock election when most of them can vote in the real thing.

On the other political end was a question about the liberal bias in faculty. Lehman acknowledged this as well but didn't consider it a problem as long as the conservative voice was not silenced. This was a good answer.

On affirmative action he said that Cornell needed more minority applicants and was working on a suggestion to start attracting students even in middle school. And someone asked a question about whether Cornell should have common core courses for the students, an interesting issue for me since even small changes in the University of Chicago's traditionally strong core have caused major controversy. Lehman said that Cornell will continue its tradition of not having any fixed course requirements for all students (besides the swimming test).

Favorite Theorems: Probabilistically Checkable Proofs

April Edition

No single topic has dominated computational complexity over the past dozen years than probabilistically checkable proofs (PCPs). Arora, Lund, Motwani, Sudan and Szegedy, in a paper on my 1994 list, showed that every language in NP has a polynomial-sized PCP that can be verified by probabilistic polynomial-time verifier using O(log n) random coins and some constant number of queries. Well beyond the complexity interest in this result, PCPs give hardness of approximation results for a variety of NP-complete problems.

Researchers in many exciting papers have improved the parameters of the PCP results in order to get improved limits on approximation. But one paper really puts it all together for some tight results.

Some optimal inapproximability results by Johan Håstad, JACM, Volume 48, 2001.

Håstad's paper shows that every language L in NP has a PCP with with O(log n) random coins and 3 queries, where

1. If x is in L then the verifier is convinced with probability arbitrarily close to one.
2. If x is not in L then no proof can convince the verifier with probability more than one-half.

There parameters are the best possible.

The paper gives some optimal approximation results. Consider Max-3-SAT, where one wants to find an assignment that maximizes the number of satisfied clauses of a 3-CNF formula. We can satisfy 7/8 of the clauses by choosing a random assignment, a process we can also derandomize. Håstad's result implies that no better algorithm exists unless NP is easy. The paper also gives improved lower bounds on approximation on problems like vertex cover and max cut.

Håstad's paper pulls in tools from a large collection of research papers. Madhu Sudan's lecture notes describes Håstad's results and the techniques and papers leading up to it. There's also been exciting PCP research since Håstad's paper but I'll have to leave that for another day.

An Auction of Google

For those with an interest in auction theory, the Google IPO auction gives an interesting testbed for auction mechanism design. Instead of having an investment bank set a fixed price for the IPO, instead Google will auction off the shares.

A New York Times article today describes many of the decisions and possible pitfalls of the various kinds of auctions Google might use. Also check out the Google SEC filing. One can learn quite a bit about auctions as well as the business of search engines from this rather informally written document. I have never had so much fun reading a prospectus.

My prediction: Great interest in Google will highly overvalue the stock whatever auction mechanism they will use. If you are interested in investing in Google, hold off until the price settles or you will suffer the dreaded "winner's curse."

Page Charges

The Journal of the ACM has started asking for page charges.

Author's institutions or corporations are requested to honor a page charge of $60.00 per printed page or part thereof, to help defray the cost of publication. Page charges apply to all contributions. Payment of page charges is not a condition of publication; editorial acceptance of a paper is unaffected by payment or nonpayment.

SIAM also recently asked us for $72/page for a Journal on Computing paper.

I despise page charges. Authors do the research, write the papers, give the journals the copyright and now the journals want us to pay for the privilege. I know the charges are optional and come from research funds but we have other needs for the money. The page charges on a moderate-sized paper could, for example, send a grad student or two to a major conference.

We have problems in our field with expensive for-profit journals and papers that never appear in refereed journals at all. We need to encourage authors to send their articles to journals run by the non-profit societies. We should not then send them a bill for doing the right thing.

Games

A readers asked about the complexity of games like Go and Chess. David Eppstein has a nice site giving a short description and references to a number of specific games.

Let us thought put such games in a general framework. We have a board and each player in turn can make one of a list of legal moves that depend on the current placement of pieces on the board. We focus on deterministic games of complete information, as opposed to games like backgammon or poker.

Games like Go and Chess are played on a fixed board, one could just enumerate all of the possible board combinations and perform perfect play in a constant amount of time. So we need to look at generalized versions of Go and Chess where the size of the board and the set of rules can vary.

Let's place this in a general setting. We have a polynomial-time algorithm that given a board and the current player can tell whether the game has ended with its outcome or can give a list of legal moves for the player. Chandra, Kozen and Stockmeyer have a seminal paper on these alternating games: If we restrict the length of the game to polynomial-time, such games characterize PSPACE (problems solvable with polynomial memory and unlimited time). Games with arbitrary long play on polynomial-size boards characterize EXP (exponential time).

So we have results like given an opening position on a generalized Go games, it is EXP-complete to determine if a player have a forced win. But even if the official Go rules allow it, I find it hard to believe that players can play the game for an exponential number of moves. So it makes sense to add some artificial stopping rules that cause the game to end after a reasonable amount of time and such games are usually PSPACE-complete.

The PSPACE-completeness results hold for many very simple games. This mirrors the fact that complexity does not arise from complicated actions, rather from the interactions of many simple actions.

New Web Host

I'm moving my web hosting service--if you can read this you are accessing the new host. I will wait a day or two to post again until the changeover is complete.

Meanwhile enjoy this Guardian column by John Sutherland describing how the British higher education system has evolved over the past four decades (via Crooked Timber). Many of the same issues apply in America and I suspect many other countries as well. Sutherland sums it up nicely.

The big question. Is the whole system in better or worse shape than it was in 1964? I don't know. All I do know is that I'd like to do it all again, and get it right this time.

America Losing Its Edge

Some required reading if you haven't seen it yet, a New York Times article on how America has lost some of its scientific leadership role over the rest of the world.

The article does not go much into the reasons behind the change so let me make some conjectures. For a long while now, the majority of Ph.D. students in the US came from other countries. As the academic job market in the US got tighter, many of these researchers went back to their home countries and established strong research groups there. Also recent technological changes have taken away some comparative advantage of doing research in the states as communication and access to research papers has become a much easier task.

I welcome the added competition, the more globalization of science that we have, the more we will all push one another with scientific research becoming the big winner. In my own field, I like seeing countries like Israel becoming theory powerhouses and definite growth of theory in places as diverse as India and Australia. A few years ago it would have been unthinkable to have STOC or FOCS overseas but recently STOC 2001 was held in Greece and the upcoming FOCS will be in Rome.

Most of all I hope the article serves as a wake-up call to American legislators. Time to give NSF that large budget increase that they've been talking about for several years now.