Dagstuhl on Algebra in Computational Complexity

(Reminder- Theory day at UMCP: here is the link. )

There was a Dagstuhl on Algebra in Computational Complexity Sept 22-26.
I learned stuff in the talks, over meals, and even in my room alone at night.

1) Recall that a while back Ryan Williams (the theorist, not the American-Football player) showed that NEXP is not in ACC. His proof involved MANY things but one of the core things was an ALGORITHM for a version of  SAT (I think Succinct-SAT) that was ever-so-slightly better than brute force. So one lesson is that people in complexity theory should know some algorithms. At Dagstuhl Ryan presented work that shows that people in algorithms should know complexity. He used some old results about circuits to obtain  algorithm for all-pairs shortest path that has complexity n^3/X where X=2^{\Omega(log n)^{1/2}. The ultimate goal is to either prove or disproof that all-pairs... has n^{3-ep} algorithms or not. On the NOT side he has (with other people, including Virginia Williams) a large class of problems , including APSP, that either all have n^{3=ep} or none of them do.

2)  There were two (possibly three) talks on VP and VNP. Both are circuit classes defined by Valiant. Meena Mahajan has some natural problems that are complete for VNP (if you consider looking at Homomorphic polynomials natural) and Eric Allennder had a dual notion to VP and VNP. A sequence of polynomials is in VP  if there is an arithmetic circuit  family of polynomial bounded size and degree that computes the sequence. (Circuit C_n computes poly f_n). VNP is if there is a sequence C_n of poly bounded size and degree such that f_n(x) = sum as y\in {0,1}^p(n) C_n(x,y).

This is usually discussed over a finite field. Eric's result depended on which field it was.

3)  Stephen Fenner talked about some combinatorial games that were PSPACE complete. The black-white-poset-game is as follows: there is a poset where every node is colored white or black. One player is called black, the other is called white. Players alternate removing nodes of their color, and if they remove a node they remove all nodes above it. Either player can go first, so you may have a game where if B goes first he wins, but if he goes second he does not. Fenner and his co-authors have shown that the general problem of, given a Black-whie Poset and who goes first, determining who wins, is PSPACE complete. They showed that other versions are in P.

4)  In the 1990's Karchmar and Wigderson had an approach to NC^1 vs NC^2 and P vs NC^1 that looked promising--- they defined problems in communication complexity (where we actually DO have results!) that would imply some separations. This lead to monotone circuit results, but not to real circuit results. Or Meir spoke on some problems in that realm which can now be approaced with information complexity. Are we closer to a true separation? Next Dagstuhl!

5)  David Zuckerman gave a nice talk on Malleable codes. I was intrigued by some of the math that he did. The Sum-Product theorems are along the lines of: If A, B are large sets of reals (or other domains) then either A+A or AA is large. Or one could say that if A,B,C are all large than AB+C is large. David used an entropy version of this--- if A,B,C have large min-entropy, then so does AB+C.

6)  Kopparty showed that Polynomial Id Testing and Polynomail Factoring are related and may be equivalent.

7)  Over Lunch Jacobo Toran told me the following rather odd result.

a) Imagine the following GI algorithm: given two graphs look at the degree sequence, then the degrees of the degress, then... (this goes on n times). Two graphs are isom if they are never found to be non-isom. DOESN"T WORK-  Cai-First-Immerman showed that. Even so, we'll call that FOCSI-isom. Note that FOCS-isom is in P.

b) Recall that G (as a matrix) and H (as a matrix) are isom if there exists a Perm Matrix P such that GP = PH. We can expand what P can be- say to doubly-stocastic (every row and every column adds to 1) We call two graphs G,H STOC-isom if there exists a Double stocastic matrix P such that GP=PH. This is in Poly Time by Linera Programming.

c) FOCS-isom and STOC-isom are the same! Too bad, I thought that STOC-isom might be a way to get GI in P.

8) Sometimes at a conference I find a book in the library and read it at night and learn something out of nowhere. This happened with Mitzenmacher-Upfal book on Prob. and Computing (It could be called ``The Alice book'' as there is a picture of Alice from Alice in Wonderland on the cover. For the longest time a famous compiler book was called The Dragon Book). I read parts of it and even made up notes that I may use in an ugrad course:  the coupon collector problem: A cereal company puts coupons labeled 1,2,...,n at random in boxes. If you mail in one of each you get a free box of cereal. You are DETERMINED to get that box of cereal. What is the expected number of boxes of cereal you must buy? It turns out to be nln(n), and is very tight around that.

9) I learned more from the talks, more from the meals, and more from my own alone time, but what is above is a good sampling.

10) More chalk-talks then I would have thought. Either chalk or slides can be done well or poorly.

11) Looking forward to the next Dagstuhl!