An Amplification Trick and STOC 2010

How to tell if an operation is associative and more

Leonard Schulman is the program chair of STOC 2010. He is of course an expert in many areas of computational complexity. He has made important contributions to areas such as game theory, quantum theory, and in general theory theory.

Today I want to thank Len for doing such a great job with this years program, and thank the rest of the committee: Timothy Chan, Ken Clarkson, Constantinos Daskalakis, Irit Dinur, Faith Ellen, Alan Frieze, Parikshit Gopalan, Piotr Indyk, Valentine Kabanets, Yael Kalai, Howard Karloff, Robert Kleinberg, Assaf Naor, Noam Nisan, Chris Peikert, Jaikumar Radhakrishnan, Oded Regev, Alexander Russell, Aravind Srinivasan, Santosh Vempala, and Andrew Yao. I look forward to seeing the talks, and seeing everyone in Boston soon.

I also thank the committee for not rejecting one of my papers this year. Since I did not submit one, it was extremely unlikely that I would get rejected. But thanks anyway. I once had a nightmare, what if someone by mistake, got a rejection email and yet they had not submitted a paper.

Len was at Georgia Tech years ago. Actually he left Tech to go to Caltech, just as I arrived. I do not believe these events were linked; I certainly would have loved to still have Len here at Tech—not Caltech.

Len did a very clever piece of work with Sridhar Rajagopalan, in 1999, that I wish to talk about. What I like so much about their work is it shows how surprising upper bounds can be. It also shows how clever Len and Sridhar can be.

Multiplication Tables

Suppose I present you with a simple by table of some “multiplication” type operator, let be the operator. More precisely, there is a set of elements and a binary operation

For any two elements and in , their “product” is denoted by .

Given such a table there are many natural questions you might ask:

1. Is it the multiplication table for an associative operator?
2. Is it the multiplication table for a group?
3. Is it the multiplication table for an abelian group?
4. Is it the multiplication table for a group with some property X?

For example question (3) can be solved in time by brute force: try all the pairs and see if

Years ago Zeke Zalcstein and I worked on such problems. In particular we showed, in 1978, that there was a constant-time randomized algorithm for checking if a group was abelian. Much more recently Bin Fu proved both upper and lower bounds for this problem. He proved, a lower bound for deterministic algorithms, and re-proved our old result.

Zeke and I worked hard on the first question, to check whether an operator was associative and we could do no better than the obvious brute force time. That is, we could not beat the algorithm: try all and check

We never tried to prove a lower bound, but it seemed “clear” that you would have to somehow try all the possible triples. Of course this is no proof, and is completely wrong.

Testing Associativity

Len and Sridhar’s solution is quite clever in my opinion. They proved

Theorem: There is a randomized algorithm that runs in time to check whether or not an by table defines an associative operator.

In the above statement, is the error probability of the algorithm. I will sketch their proof—as always please look at their well written paper for all the details and some additional results.

The key insight is to look at the “algebra” defined by the operation. The elements of this algebra are formal sums of the form

where lies in the Galois Field of two elements. They point out that if the operation defined a group this would be called the “group algebra.” There are three natural operations defined on these elements:

1. Addition: .
2. Scalar multiplication: .
3. The operation : .

These operations can be done efficiently. The key is that the last operation can be done in time by a brute force method. Just form all the products and collect like terms.

It is not hard to show that the table is associative if and only if the operation on is also associative. Their algorithm is just this: select three random elements from and check that

The last step is the lemma:

Lemma: Suppose the operation is not associative. Then with probability at least the above random test will fail.

The point is that in blowing up the domain from to , now any failure of associativity over extends to at least triples from . In a sense their associative testing algorithm is using an amplification trick. Very neat

Open Problems

Can their method be used to get other properties of tables in less than the obvious time? The “group algebra” type approach seems quite powerful. Can it be used to solve other problems?

A sad postscript: the great Vladimir Arnold passed away in France earlier today. I talked about some of his conjectures before here.