Three From CCC

Comments on three papers from the Conference on Computational Complexity

Michael Saks is Chair of the Program Committee of this year’s Conference on Computational Complexity (CCC). He was helped by Paul Beame, Lance Fortnow, Elena Grigorescu, Yuval Ishai, Shachar Lovett, Alexander Sherstov, Srikanth Srinivasan, Madhur Tulsiani, Ryan Williams, and Ronald de Wolf. I have no doubt that they were faced with many difficult decisions—no doubt some worthy papers could not be included. The program committee’s work does not completely end after the list of accepted papers is posted, but it is not too early to thank them all for their hard work in putting together a terrific program.

Today I wish to highlight three papers from the list of accepted ones.

The biggest danger in selecting three is that I will disappoint the authors of the remaining papers. Of course that assumes that they care what we say at GLL, so perhaps there is really no danger. In any event I selected the papers because they caught my immediate fancy. I plan on discussing others later on, but let’s just look at these now. Two concern favorite problems of mine, and the third is an amazing result—in my opinion.

Of course as a PC member, Mike was not allowed to submit a paper, so it follows that he is not an author of any of the CCC papers we mention. But one of his recent papers, with Ankur Moitra of Princeton IAS, appeals to me as an example of learning from the past. Their paper analyzes an old algorithm for learning a distribution from random samples to show that it runs in polynomial time, and beefs it up to apply in more-general cases. Their proof uses linear programming duality and analyzes invertible matrices that have bad condition numbers, something Ken and I have been thinking about in connection with the Jacobian Conjecture and other matters. Their paper appeared at FOCS 2013.

Something New About Kolmogorov Complexity

Linear list-approximation for short programs (or the power of a few random bits) by Bruno Bauwens and Marius Zimand.

They study the Kolmogorov complexity of —the length of the shortest program that generates . One of the great “paradoxes” of Kolmogorov complexity is that while most strings have about the length of , it is impossible to compute the function . Even worse it is impossible to prove in a fixed theory that for large enough for any . See here for more details.

Their cool result is that given a string they can construct a list of “answers” so that one of them is a description of length of . The computation of this list can be done by a randomized algorithm that uses only random bits. As they say:

Thus using only few random bits it is possible to do tasks that cannot be done by any deterministic algorithm regardless of its running time.

Very neat.

Progress on Group Isomorphism

Algorithms for group isomorphism via group extensions and cohomology by Joshua Grochow and Youming Qiao.

Group isomorphism for groups defined by multiplication tables () is one of my favorite problems—note the initials are “Gp” for group and “I” for isomorphism—while the more-storied graph-isomorphism problem gets the shorter moniker . The best general bound remains the longstanding one of order , which we have discussed recently and before. That result uses just one important but trivial property of finite groups: any proper subgroup of a group is at most one half the size of the group.

A curious consequence of the classification of finite simple groups is that isomorphism for simple groups is easy—in polynomial time. This is because finite simple groups are all -generated. By the way there appears to still be no chance to get a direct proof of this: all roads to -generation lead through the whole classification theorem. Indeed a proof of -generation would greatly simplify the classification proof itself, as remarked in this MathOverflow thread.

So the “hard” cases are all groups that have non-trivial normal subgroups. Suppose that and are two groups that we wish to see if they are isomorphic. Let be a non-trivial normal subgroup of . An obvious idea is to try and find the corresponding of . Suppose that we could do this. Then we can check whether is isomorphic to by recursion. The obstacle is that even if they are the isomorphic it is possible that the subgroups “sit” inside their respective groups in vastly different ways. This is what makes hard and interesting.

The group extension problem is all about how a subgroup sits inside a larger group. And cohomology is one tool that can be used to understand this.

In order to make further progress on group isomorphism the authors believe—I think correctly—that much deeper properties of groups must be brought to bear on . They argue that any strategy must begin to look at the so called cohomology classes and structure of group extensions. Following this strategy, they solve in time for certain important families of groups. These results uses the detailed structure of cohomology classes, as well as algorithms for equivalence, coset intersection, and determining the structure of modules over finite-dimensional algebras.

Note, the bound is still super-polynomial. The exponent still is unbounded, but as someone who has thought too often about this problem, I can aver that going from to in the exponent is quite impressive.

PIT and Polynomial Factoring

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization by Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka.

The title is direct and almost needs no comment. They prove that polynomial identity testing (PIT) is equivalent to factoring of polynomials over many variables. One fact they use is the—as they say—amazing fact that if a polynomial has an arithmetic circuit of size and degree in variables, then the irreducible factors of have arithmetic circuits of size .

They also use the famous Hilbert Irreducibility Theorem. Actually they use an effective version of it. I thought rather than outline their proof, which is so carefully explained in their paper, that I would instead say something about this theorem.

Suppose that is a polynomial with rational coefficients. Suppose further that is irreducible over the rationals. Hilbert’s question was the natural one:

Must there be a rational so that remains irreducible?

The answer is yes. And it generalizes to multiple variables and to other fields, but not all. Indeed a field with this property is called—you guessed right—a Hilbertian field. Essentially a Hilbertian field is the opposite from being algebraically closed: the complex numbers are not Hilbertian. Even further there is interest in what subsets of the rationals can be used and still leave irreducible. It is known that various subsets of the rationals have this kind of universality property, and there is continuing interest in what sets can work.

Open Problems

Some obvious questions arise in regard to each paper. Can we use the list of descriptions of a string to solve some interesting question? It seems like a powerful idea that should help solve some problems. Also lets finally solve the group isomorphism problem. And accessible problems about PIT too.