Skip to content

An Amplification Trick and STOC 2010

June 3, 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 {n} by {n} table of some “multiplication” type operator, let {\circ} be the operator. More precisely, there is a set {S} of {n} elements and a binary operation

\displaystyle  \circ: S \times S \rightarrow S.

For any two elements {x} and {y} in {S}, their “product” is denoted by {x \circ y}.

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 {O(n^{2})} by brute force: try all the pairs {x,y} and see if

\displaystyle  x \circ y = y \circ x.

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 {\frac{n^{2}}{3}} 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 {O(n^{3})} time. That is, we could not beat the algorithm: try all {x,y,z} and check

\displaystyle  x \circ (y \circ z) = (x \circ y) \circ z.

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 {O(n^{2}\log \frac{1}{\delta})} to check whether or not an {n} by {n} table defines an associative operator.

In the above statement, {\delta} 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 {\cal S} are formal sums of the form

\displaystyle  \sum_{s \in S} a_{s}s,

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

  1. Addition: { \sum_{s} a_{s}s + \sum_{s} b_{s}s = \sum_{s} (a_{s}+b_{s})s}.
  2. Scalar multiplication: {b \sum_{s} a_{s}s = \sum_{s} ba_{s}s}.
  3. The operation {\circ}: {\left( \sum_{r} a_{r}r \right) \circ \left( \sum_{s} b_{s}s \right) = \sum_{r}\sum_{s} a_{r}b_{s} (r \circ s) }.

These operations can be done efficiently. The key is that the last operation can be done in time {n^{2}} 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 {\circ} on {\cal S} is also associative. Their algorithm is just this: select three random elements {\mathbf{a}, \mathbf{b}, \mathbf{c}} from {\cal S} and check that

\displaystyle  \mathbf{a} \circ (\mathbf{b} \circ \mathbf{c}) = (\mathbf{a} \circ \mathbf{b}) \circ \mathbf{c}.

The last step is the lemma:

Lemma: Suppose the operation {\circ} is not associative. Then with probability at least {1/8} the above random test will fail.

The point is that in blowing up the domain from {S} to {{\cal S}}, now any failure of associativity over {S} extends to at least {|{\cal S}^3|/8} triples from {{\cal S}}. 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?

\displaystyle \S

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

About these ads
6 Comments leave one →
  1. mikolalysenko permalink
    June 3, 2010 9:39 pm

    Actually, I just finished a paper which heavily used group algebras! (Albeit for a totally different application…)

    From a very high level view, the ideas in our paper were to use convolution algebras to compute workspaces for mechanical devices (ie collections of allowable translations/rotations for various joints). Of course the basic concept is much more general, and we also apply it to some related problems like shape symmetry detection. Here is a link for those who are interested:

    http://0fps.wordpress.com/2010/06/01/new-paper-out/

  2. June 4, 2010 5:29 am

    It is sobering news that Vladimir Arnol’d has passed away. With Martin Gardner, he was yet another lamed-vavnik of mathematics.

    Both Gardner and Arnol’d died full of years … but who will replace them?

    My aphorism database contains many contributions from Arnol’d. These are always provocative; for example: “One should speak the truth even at risk of provoking a scandal” and “One can always find imbeciles to prove theorems”.

    Only the greatest textbooks successfully inoculate new notions of naturality; Arnol’d’s Mathematical Methods of Classical Mechanics was one such book, organized around the naturality principle “Hamiltonian Mechanics is geometry in phase space.”

  3. Son Nguyen permalink
    June 6, 2010 8:29 pm

    I am learning the “Fast matrix multiplication problem” which embeds the matrix multiplication into convolution product of group algebra. The two problems seem to be not quite related. However, it’s fascinating to know another application of representation theory.
    Thank you for the nice post.

  4. ilyaraz permalink
    June 8, 2010 3:10 pm

    It would be nice to have an example of non-associative operation with O(1) non-associative triples.

    • ilyaraz permalink
      June 8, 2010 3:20 pm

      Actually, in the paper such an example is given. More precisely, 1 * 2 = 2. x * y = 3, otherwise.

Trackbacks

  1. An Amplification Trick and STOC 2010 | rssblogstory.com

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,887 other followers