Electronic Commerce

The call for papers for the 2004 ACM Conference on Electronic Commerce is now available. I'm posting this note as my duty as a program committee member to spread the word of the conference.

Why would an electronic commerce conference want me, a complexity theorist, as a PC member? Electronic commerce has many surprising connections to computational complexity. Consider complex auction situations where different buyers wish to purchase different items with varying needs for combinations of these auctions. One needs to design such auctions which decisions made by the buyers, as well as determining the winner must be computationally efficient. This in addition to the usual needs of auctions to be revenue generating, robust against players trying to cheat the system and other notions of "fairness."

In a more philosophical sense, what is a large financial market but some sort of massive parallel computation device that takes pieces of information and produces prices for securities. How can we model and analyze this process? Computational complexity should play a major role in understanding this model of computing and allow us to develop more efficient financial markets.

Hello Chicago

Here I am, my first day back on the campus of the University of Chicago. It's quiet here, Chicago is on the quarter system and classes don't start here until September 29.

I was on the road during the August 22 anniversary of my first post on this weblog. I hope you have enjoyed reading it this year as much as I have had fun writing it.

Goodbye New Jersey

My office is all packed up and ready to be shipped. On Friday we move out of our house. I've moved my web pages to Chicago. Burned my files to CD's. It is disconcerting to see all my life's work (papers, talks, programs, grant proposals, editorial and conference stuff, course material, etc.) fit so easily on one CD-ROM. Uncompressed.

Moving is always sad. I've made many good friends at NEC, in and out of theory. But with change comes the excitement of the new chapter of my life ahead of me.

With being on the road and settling in, posting on this site will be quite sketchy over the next several weeks. But don't worry, as one California gubernatorial candidate would put it, I'll be back.

A New-To-Me Pumping Lemma for Regular Languages

I have a gap in my knowledge of work in theory done between 1979 (the publication of Hopcroft and Ullman) and 1985 (when I started graduate school). So every now and then I see a new result from this time that I should have known years ago. Here is an example from the Winter 1982 SIGACT News, a variation of the regular language pumping lemma due to Donald Stanat and Stephen Weiss.

Theorem: If L is regular then there is a positive integer n such that for every string x of length at least n, there are strings u, v and w with v nonempty such that x=uvw and for all strings r and t and integers k≥0, rut is in L if and only if ruv^kt is in L.

What surprises me about this result is that w does not appear in the conclusion and that the initial r could put the finite automaton in any state before it gets to u. Here is a sketch of the proof.

Let s be the number of states of a finite automaton accepting L. Let y_i be the first i bits of x. For any initial state a, y_i will map it to some state b. So one can consider y_i as a function mapping states to states. There are at most s^s such functions so if |x|≥s^s there is an i and a j, i<j such that y_i and y_j represent the same function. We let u=x₁...x_i-1 and v=x_i...x_j-1. The rest follows like the usual pumping lemma.

Using a result of Jaffe, Stanat and Weiss show that this condition is not only necessary but also sufficient to characterize the regular languages.

Splitting Sets

Can every infinite set in P be partitioned into two infinite subsets, each also in P? Uwe Schöning answers this question in the affirmative in the Winter 1982 SIGACT News.

Let's generalize the question by saying that a set A splits a set B if both A∩B and A∩B are infinite. Schöning really shows the more general result that any infinite recursive set can be split by a polynomial-time computable set.

Playing with this splitting notion yields lots of potential homework questions. Try these:

1. Show that every infinite regular language can be split by another regular language. Can every infinite context-free language be split by a regular language?
2. Show there is an infinite recursive set that cannot be split by any regular language.
3. Prove Schöning's result above: Every infinite recursive set can be split by a set in P.
4. For a real challenge, show that there is an infinite co-r.e. set that cannot be split by any r.e. set.

In recursion theory, sets that cannot be split by r.e. sets are called cohesive, and r.e. sets whose complements are cohesive are called maximal. For question 4 you are showing that maximal sets exist, a result first proven by Friedberg in 1958.

SIGACT News and The Cold War

Cleaning out my office I came across some old SIGACT News that Bill Gear had given me when he cleaned out his office after his retirement. The Winter 1982 edition is quite interesting. I was a freshman in college that year, well before I was part of the theory community.

There are some interesting technical articles that I will get to in future posts. But the first two pages were letters to the editor that are chilling reminders of the cold war during that time.

On page two was the following short note from Witold Lipski, Jr. and Antoni Mazurkiewicz from the Polish Academy of Sciences.

We are very sorry to inform you that due to the situation in Poland we do not see any chance to organize our 1982 Conference on Mathematical Foundations of Computer Science.

MFCS started in 1972 as an annual conference rotating between Poland and Czechoslovakia, and now between Poland, Slovakia and the Czech Republic. There was no conferences in 1982 or 1983 and the conference did not return to Poland until 1989.

Talking about the Czechs, there was a much longer letter on page one from James Thatcher of IBM. Here are some excerpts.

On a recent trip to Europe, I visited Prague and had the pleasure of talking with Dr. Ivan M. Havel who is a friend and colleague of many years. Ivan Havel received his Ph.D. in CS from Berkeley in 1971. He joined the Institute for Applied Computer Technology in Prague in 1972 and then in 1974 became a member of the Czechoslovakian Academy of Sciences, in the Institute of Information Theory and Automation.

Ivan's brother, Vaclav Havel, an internationally known playwright, was imprisoned in 1979 for four and a half years for his activities in connection with the Charter 1977 movement.

In 1980, possibly related to his refusal to denounce his brother, Ivan Havel was removed from his position in the Academy of Sciences and was unemployed for several months. Last May, he and Vaclav's wife were arrested and charged with "subversion" for allegedly "collecting and distributing written material oriented against the socialist state and social establishment, with hostile intentions." After four days detention, they were released.

He is employed as a programmer-analyst by META, a home-worker program for the handicapped.

Ivan Havel remained a programmer until after the Velvet Revolution in 1989. After some political work in 1990, he became a docent (associate professor) at Charles University and director of the Center for Theoretical Study where he remains today.

His brother Vaclav went on to become president of the Czech Republic.

My Life in Email

When I move back to Chicago, I will go back to my old email address . I got to thinking about how my career can be described by my email addresses.

As an undergrad at Cornell, I spent several years working for computer services writing an email system in assembly language for the IBM 370. The system was scrapped shortly after I left for grad school at Berkeley. After a year at Berkeley, I followed by advisor, Michael Sipser, to MIT.

I had email addresses at Cornell and Berkeley but I have long since forgotten them. At MIT I wanted the userid "lance", but the name was taken by Lance Glasser, then an MIT professor. So my email became .

When I graduated and went to Chicago, I decided to stick with the userid "fortnow" for an email of . This bucked the trend at the time of having first names for email at Chicago so I had to have aliased to . When the university started system wide email I got though also works.

When I did a sabbatical in Amsterdam my email became or simply . When I moved to the NEC Research Institute my email because aliased to and when the NEC Research Institute became NEC Laboratories America I got my current email .

In addition to this, the ACM has created permanent email addresses, permanent as long as you are an ACM member and I did create an address though I never did give it out (until now). My brother and I now own the domain fortnow.com and I have what I do call my permanent address, . I also am the default receiver for fortnow.com mail, which means that addresses like , or even will all go to me.

All of the email addresses in this post still work and forward to me. But I will stick to using two main email addresses, for work related email and for non-work emails.

I used javascript to generate the emails in this post to avoid adding even more to my heavy spam load. We'll see if it works or whether I start getting spam sent to .

Information Markets for Fighting Terrorism

A few months ago I had a post describing information markets, a system of buying and selling securities that pay off if a given future event happens. Based on the price of a security, one can get an estimate of the probability that that event will occur. Studies have shown that information markets are better predictors than polls or experts.

Information markets have taken a blow in the past few days. The US Department of Defense has cancelled a program that would have set up limited futures markets on securities based on terroristic activities. They bowed to pressure from senators who consider it morally wrong to bet on events on future terrorist attacks. I understand their concerns but computer scientists and economists have produced what could have been a powerful tool in controlling terrorism and it is quite a shame to see it discarded so easily.

David Pennock sent me some links on a more positive point of view from CNN, Fortune and Wired and a fun CNN piece on the Tradesports Poindexter future.

Update (8/1): A well-written New York Times column A Good Idea with Bad Press and a nicely argued opinion piece by David Pennock.

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.