The Tour

I know this is not a sports weblog and I don't even like bicycling but anytime an American named Lance wins a major championship I can't let it go unnoticed.

The Move

Way back when I was a graduate student, I moved from Berkeley to MIT. I put what few belongings I had into boxes and shipped them via UPS. My brother flew out and we drove across the country together. Those were the days.

Now making the move back to Chicago is not nearly so simple. We have houses to sell and buy. Getting our kids ready for a new school. Real estate agents, lawyers, mortgage and insurance people to deal with. Meanwhile there is academic work that needs to get done before the real move. Conference and grant deadlines don't move to accommodate my move.

So this weblog might get a little spotty until I get settled into Chicago, sometime in mid-September. I'll try to find some time for some posts during that time but don't expect too much. If you are having complexity weblog withdrawal check out the archives. Nice thing about complexity--old stuff doesn't (usually) get stale.

Juntas

Eldar Fischer gave a talk today on his paper on testing juntas. So what is a junta? According to the American Heritage Dictionary, a junta is a "A group of military officers ruling a country after seizing power", named after such groups in Central and South America in the 80's. In this paper a junta refers to a function that depends on a constant number of variables.

Back when I was young (those 80's) we had a different name for a function that depends on a constant number of variables: NC⁰, a specification of NC^k, functions computable in constant fan-in circuits of depth O(log^k n). If k = 0 we have constant fan-in and constant depth, which means it depends on a constant number of variables.

Digression: NC stands for "Nick's Class" named by Steve Cook in honor of Nick Pippenger. Pippenger repaid the favor with the class SC but enough of that for now.

Juntas are just one example I'm seeing of a trend of new names and definitions of concepts defined years ago. Makes me feel old. Of course back then we likely studied concepts were thought were new but might not have been. Just part of the great circle of math.

Citeseer

Perhaps the NEC project most valued by computer scientists is Citeseer developed by Steve Lawrence, with help from Lee Giles and Kurt Bollacker and others. Citeseer is a free web-based service that scans the internet for computer science technical reports, parses the citations and cross-links the papers. You can use Citeseer to see, based on citations, which papers are most relevant to a particular topic. You can sort papers or even computer scientists (not necessarily a good thing). Since the papers are cached you also quickly get hold of old versions of many papers.

With the changes at NEC, I often get asked what will happen to Citeseer. Don't worry--Citeseer will soon have a new safe home and will continue to provide computer scientists with an easy way to track down papers.

Quantum Advice

Another rump session talk by Scott Aaronson showed that BQP/qpoly is contained in EXP/poly. In other words, everything efficiently quantumly computable with a polynomial amount of arbitrarily entangled quantum advice can be simulated in exponential time with a polynomial amount of classical advice.

Let me try to put this in context while avoiding quantum mechanics. Advice is method for encoding a different program for each input length. We define the class P/poly as those languages computable in polynomial time with access to a polynomially-long advice string a_n where the string a_n depends only on the length of the input. P/poly is equivalent to those problems having nonuniform polynomial-size circuits.

Quantum advice is a bit more tricky, since it can be in a superposition of regular advice strings. Formally, quantum advice is an exponentially long vector of numbers β_a where β_a is the amplitude of advice string a. For simplicity let us assume those numbers are real and we'll also have the restriction that the sum of the squares of the amplitudes is one.

You can see there are far more ways to give quantum advice than classical advice. But the quantum machines are limited in how they can use the advice. Harry Buhrman asked whether one can give any limit at all to what one can do with quantum advice. Scott Aaronson gives an answer: No better than classical advice as long as you are allowed (classical) exponential time.

Ideally one would like that efficient quantum algorithms with quantum advice can be simulated with efficient quantum algorithms with classical advice. Still Aaronson's result shows that even with fully entangled advice one cannot get all the information out of it.

A Combinatorial Theorem Proven by Kolmogorov Complexity

During the rump session of complexity, Nikolai Vereshchagin presented a combinatorial theorem that he proved using Kolmogorov complexity. Let A be a finite subset of N×N where N is the set of natural numbers. Let m be the size of A, r be the number of nonempty rows of A and c the number of nonempty columns.

We say A is good is every nonempty row has m/r elements and every nomempty column has m/c elements of A. A rectangle has this property, as does a diagonal. We say A is k-good if every nonempty row has at most km/r elements and every nonempty column has at most km/c elements. A is good if it is 1-good.

Vereshchagin's Theorem: There is a constant c such that for all finite subsets B of N×N with n = log |B| there is a partition of B into at most n^c sets each of which is n^c-good.

Vereshchagin asks whether there is a purely combinatorial proof of this theorem. If you know of one let me know.

For those who know some Kolmogorov complexity, let me sketch the proof: We label each point (x,y) of B with the following five values: K^B(x,y), K^B(x), K^B(y), K^B(x|y) and K^B(y|x). We partition the points into sets with the same labels. Standard counting arguments from Kolmogorov complexity show that each partition is n^c-good for some c.

Update

The Rump Session

One of the nice aspects of the Complexity Conference, the rump session, I don't see at many other conferences. Here anyone who wants to, mostly students, get ten minutes to lay out their latest research.

This year we had one of the best rump sessions ever with five really neat results, listed below. Don't worry if you don't immediately understand the results, I will talk about some of them in more detail in future posts. All but Vereshchagin are students.

1. Nikolai Vereshchagin: A combinatorial theorem proven by Kolmogorov complexity with no known direct combinatorial proof.
2. Troy Lee: For every finite set A and x in A, CND^A(x) ≤ log |A| + O(log³|x|). CND is the nondeterministic version of Sipser's distinguishing complexity.
3. Scott Aaronson: Everything efficiently quantumly computable with a polynomial amount of arbitrarily entangled quantum advice can be simulated in exponential time with a polynomial amount of classical advice.
4. Kristoffer Hansen: Constant-width planar circuits compute exactly ACC⁰, constant depth circuits with a mod gate for some fixed composite.
5. Samik Sengupta: If co-NP has an Arthur-Merlin game with a polylogarithmic number of rounds then co-NP is in NP with quasipolynomial advice and the exponential hierarchy collapses at the third level.

Coming Home

Howdy from Aarhus, Denmark where I am attending the 18th Annual IEEE Conference on Computational Complexity. As readers of this weblog probably have figured out, this is, by far, my favorite conference. Complexity is smaller and more relaxed than the broader theory conferences like STOC and FOCS. I know most of the participants and have a genuine interest in the most of the papers here. While elsewhere theorists try more and more to find connections to applied areas, here we are happy to focus on the fundamental power of efficient computation.

During the rest of the year I attend some conferences in broader areas or in areas that are not in my major focus. But coming to Complexity is coming home, and it always feels great to be back where I belong.

Complexity Abstracts

In the early years of the complexity conference, some researchers complained that if they had new results or their papers were not accepted in the conference, their results would not be known. So we started up Complexity Abstracts, an electronically available document where anyone can publish a one-page abstract of their work. The abstracts were made available right before the conference.

Last year, the first abstracts editor, Bill Gasarch, resigned his job after 11 years of collecting the abstracts. Personally I thought that in this new internet age, with sites like ECCC, the Complexity Abstracts were no longer as valuable a resource. But at the business meeting of last year's conference the Abstracts were greatly supported and Steve Fenner volunteered to take on the job of editor.

Fenner's first collection has just been posted ahead of the Complexity Conference next week in Denmark.

For the Love of Math

A doctor, lawyer and mathematician were discussing whether it was better to have a wife or a girlfriend. The doctor said it was better to have a wife because it is medically safer to have a single partner. The lawyer said it was better to have a girlfriend to avoid the legal hassles of marriage. The mathematician said it was better to have both.

"Both?" said the doctor and the lawyer. "Yes," said the mathematician, "That way the wife thinks I'm with the girlfriend, the girlfriend thinks I'm with the wife and I can do some math."

I was reminded of that joke by the recent New York Times article Pure Math, Pure Joy and the accompanying slideshow. Those pictures look all too familiar.

The greatest lovers of math though are not the famous mathematicians at places like Berkeley and Harvard. Rather the mathematicians who take low-paying jobs with high teaching loads at less-strong colleges or move from visiting position to visiting position just to have some occasional time to do math. They have a dedication (or perhaps an addiction) I can never fully appreciate.

Expanders from Epsilon-Biased Sets

Expander graphs informally are graphs that given any subset S that is not too large, the set of vertices connected to S contains a large number of vertices outside of S. There are many constructions and applications for expander graphs leading to entire courses on the subject.

The adjacency matrix A of a graph G of n vertices is an n×n matrix such that a_i,j is 1 if there is an edge between vertices i and j and 0 otherwise. Noga Alon noticed that a graph that has a large gap between the first and second eigenvalue of the adjacency matrix will be a good expander.

We can use ε-biased sets to get expanders. Let S be a ε-biased set for F^m for F the field of 2 elements. Consider the graph G consisting of 2^m vertices labelled with the elements of F^m and an edge from x to y if y=x+s or x=y+s. This kind of graph G is known as a Cayley graph.

By looking at the eigenvalues the adjacency matrix A of G we can show G is an expander. The eigenvectors v are just the vectors corresponding to the functions g in L described earlier. For any vector a we have

(Ag)(a) = Σ_{s in S} g(a+s) = g(a) Σ_{s in S} g(s) since g(a+s) = g(a)g(s). Let g(S) = Σ_{s in S} g(s). We now have that Ag = g(S) g. So g is an eigenvector with eigenvalue g(S). If g is the constant one function then g(S)=|S|. Since S is an ε-biased set, g(S)≤ε|S| for every other g, so the second eigenvalue is much smaller than the largest eigenvalue and G must be an expander.

SIGACT

The June 2003 SIGACT News is out. Aduri Pavan wrote this months Complexity Theory Column on "Comparison of Reductions and Completeness Notions".

As I have mentioned before in this weblog, I heartily encourage joining SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory. You get the SIGACT News, discounts on conferences and as I discovered last night from home, you apparently get online access to the STOC proceedings. Not to mention supporting the theory community. All this for the low price of $18 ($9 for students).

What about the ACM itself? I have been an ACM member since graduate school since I feel it is important to support the main computer science organization. But for the additional $96 ($42 for students) there are no real significant benefits over joining SIGACT alone.

Epsilon-Biased Sets

ε-biased sets are an interesting concept that I have seen recently in a few papers but never seemed to have a clear description. At FCRC Eli Ben-Sasson gave me a good explanation and I will try to recreate it here.

Let F be the field of 2 elements 0 and 1 with addition and multiplication done modulo 2. Fix a dimension m. Let L be the set of functions g mapping elements of F^m to {-1,1} with the property that g(x+y)=g(x)g(y). Here x+y represents addition done coordinate-wise modulo 2. One example of a g in L is g(x₁,x₂,x₃)=(-1)^x₁ (-1)^x₃.

There is the trivial function g in L that always maps to 1. For every non-trivial g in L exactly half of the elements in F^m map to 1 and the others to -1. If one picks a reasonably large subset S of F^m at random then high probability, g will map about half the elements to 1 and the rest to -1. In other words the expected value of g(x) for x uniformly chosen in S is smaller than some small value ε. If this is true we say S is ε-biased for g.

An ε-biased set is a set S such that for all nontrivial g in L, S is ε-biased for g. Formally this means that

Σ_{x in S} g(x) ≤ ε|S|. Not only do reasonable size ε-biased sets exists but they can be found efficiently. Naor and Naor found the first efficiently constructible ε-biased sets of size polynomial in m and 1/ε.

One can extend the notion of ε-biased sets to fields F of p elements for arbitrary prime p. L would now be the set of functions g mapping elements of F^m to the complex pth roots of unity, e^2π(j/p)i for 0≤j≤p-1 again with the property that g(x+y)=g(x)g(y). Various constructions have created generalized ε-biased sets of size polynomial in m, 1/ε and log p.

For applications let me quote from the recent STOC paper by Ben-Sasson, Sudan, Vadhan and Wigderson that used ε-biased sets to get efficient low-degree tests and smaller probabilistically checkable proofs. You can get more information and references from that paper.

Since the introduction of explicit ε-biased sets, the set and diversity of applications of these objects grew quickly, establishing their fundamental role in theoretical computer science. The settings where ε-biased sets are used include: the direct derandomization of algorithms such as fast verification of matrix multiplication and communication protocols for equality; the construction of almost k-wise independent random variables, which in turn have many applications; inapproximability results for quadratic equation over GF(2); learning theory; explicit constructions of Ramsey graphs; and elementary constructions of Cayley expanders.

Whose hands are on the FOCS cover?

Sometimes I learn interesting aspects of the history of theory from this weblog. On an old post on conference covers, Pekka Orponen left a comment saying that Alvy Ray Smith originally designed the FOCS cover back in 1973, when the conference was SWAT: Switching and Automata Theory. Here is Smith's story about the cover where he states the hands are his.

Smith had three papers in SWAT before moving into computer graphics and co-founding companies such as Pixar. So next time you are looking up a FOCS paper take a look at the hands of a one-time theorist who made a difference.

Walter Savitch

After the FCRC meetings I attended were concluded, I headed up to UCSD for the celebration of Walter Savitch for his sixtieth birthday and upcoming retirement. He gained his fame in complexity for Savitch's Theorem that shows "P=NP" for space.

I learned quite a bit at the meeting. Walt Savitch was Steve Cook's first student, his only student while Cook was at Berkeley in his pre-Toronto pre-"SAT is NP-complete" days. Also as Cook said, Savitch is the only student he has had with a theorem named after him. That theorem made up a good part of Savitch's Ph.D. thesis. At the celebration Cook gave an overview on propositional proof systems.

After coming to UCSD, Savitch did some work on computational linguistics and one of the leaders of the field, Aravind Joshi, gave a talk on combining trees to keep the structure when parsing sentences.

Savitch is probably best known now in computer science for his textbooks in introductory programming that likley many of you have used.

Congrats Walt on a fine career and here's hoping retirement doesn't slow you down.

FOCS 2003

The list of accepted papers for FOCS 2003 has been posted. As usual, many (but not all) of the papers are available on the authors' web sites.

Boosting

As promised I added links to the papers in the post on the STOC business meeting. Let me say some more words on the winner of the Gödel prize

Valiant developed the concept of PAC (Probably Approximably Correct) learning as roughly where a learner sees a small number of labelled examples from a distribution and with high confidence will generate a hypothesis that with high probability will correctly label instances drawn from the same distribution.

A strong learner has confidence close to 100%; a weak learner has confidence only slightly better than 50%. Schapire, using a technique called boosting, showed how to convert a weak learner to a strong learner. This is a wonderful theoretical result but the algorithm had problems that made it difficult to implement.

In their Gödel prize winning paper, A decision-theoretic generalization of on-line learning and an application to boosting, Freund and Schapire develop the adaboost algorithm that solves many of these issues and has become a staple of the theoretical and practical machine learning community.

Boosting has its own web site where you can find much more information about the algorithms and applications.

Alonzo Church

Alonzo Church was born a hundred years ago today in Washington, DC. Church is best known for the λ-calculus, a simple method for expressing and applying functions that has the same computational power as Turing machines.

With Rosser in 1936, he showed that λ-expressions that reduce to an irreducible normal form have a unique normal form. In that same year he showed the impossibility of decided whether such a normal form existed.

Church's thesis, which he states as a definition: "An effectively calculable function of the positive integers is a λ-definable function of the positive integers."

Again in 1936, Kleene and Church showed that computing normal forms have the equivalent power of the recursive functions of Turing machines. And thus the Church-Turing thesis was born: Everything computable is computable by a Turing machine.

The λ-calculus also set the stage for many of the functional programming languages like lisp and scheme.

Alonzo Church passed away on August 11, 1995 in Ohio.

Thoughts on FCRC

I have mixed feelings about the Federated Computing Research Conference. It is a good idea to get many different areas of computer science together. I do get to see many people I haven't seen in years who went into non-theoretical areas of CS.

On the other hand 2200 participants made the place quite crowded and it seemed to take away from the informal atmosphere of most theory conference. Since STOC and Electronic Commerce had nearly a complete overlap I jumped back and forth between talks never really feeling fully part of either conference.

For the first time the Complexity conference was not part of FCRC because 2003 is a Europe year for Complexity. In an informal poll I took of STOC people interested in complexity most liked having both conferences at the same place but would rather that happen in isolation, like last year in Montreal, rather than as part of the much larger FCRC meeting.

In what seems to be a trend in CS conferences, wireless internet was made available at the conference site. As you walked around you would pass many people sitting on chairs and on the ground hunched over their laptops disconnected from the conference and connected into another world. Seemed a bit depressing but I too found the net hard to resist--it is always tempting to simply open my laptop and connect, checking email and posting to this weblog.

The Business Meeting

Update (9/3/03): STOC 2004 CFP

Last night was the business meeting for STOC. This used to be a raucous affair with major battles over issues like whether to have parallel sessions, but now in its old age is more for distributing information like

• Awards: Godel Prize for best paper published in a journal in last seven years: Yoav Freund and Rob Schapire for their adaboost algorithm.
  Knuth Prize for lifetime research activity: Miklos Ajtai.
  STOC Best Paper: Jointly to Impagliazzo and Kabanets for "Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds" (you read it here first) and Oded Regev for "New Lattice Based Cryptographic Constructions".
  The Danny Lewin Best Student Paper Award: Thomas Hayes for "Randomly Coloring Graphs of Girth at Least Five" Thomas Hayes is from my once and future department at U. Chicago.
• Future Conferences: FOCS 2003 in Boston, STOC 2004 in Chicago and FOCS 2004 in Rome, its first time outside North America. On Friday, a day after agreeing to return to Chicago, Janos Simon asked me to give the presentation on STOC 2004, which is always fun. Laszlo Babai, another member of the Chicago faculty, will be PC chair of that meeting.
• Registration numbers, NSF report, progress on scanning in old papers and redoing submission software. I'm not going to do a full business meeting report--someone else does that and will eventually appear in SIGACT news.