CCC 2012- Post 3 of probably 4

Post 3 of n on CCC 2012. I still don't know what n is.
I summarize the third and fourth day of the conference.
(The fourth day was only a half-day).

Thursday June 27 Morning Session:

1. Matrix Lie Algebra Isomorphism by Grochow. This paper was called (and the link above still uses the old name) Lie Algebra conjugacy. Some Isom problems for Lie Algebras are equivalent to Graph Isomorphism. In general Harder Math does not mean Harder Computationally.
   
2. On Sunflowers and Matrix Multiplication by Alon, Shpilka, Umans. Erdos-Rado made a conjectures about sunflowers. Coppersmith and Winograd made a conjecture in combinatorics which would, if true, yield a better Matrix Mult Alg. This paper shows (roughly) that if the ER-conj is true then the CW-conj is false. Neither conj sounds that intuitive to me so I don't know what to make of this.
   
3. Algebras of minimal multiplicative complexity by Blaser and Chokaev. I couldn't find a link- if you know one email it to me.
   
4. Invited Talk Prospects for Geometric Complexity Theory by Peter Burgisser. So what are the prospects? Mixed. I was happy to hear that there are people working on this, but the talk was not that optimistic.
   

Thursday June 27 Afternoon Session:

1. A Strong Direct Product Theorem for Quantum Query Complexity by Lee and Roland. Direct Product Conjectures say (roughly) that if a problem takes T blahs to do then doing k of them given to you all at once takes kT blahs to do. There are many of these depending on your interest. This paper shows shows something stronger: If you want to computer just the XOR of the k instances it will take roughly kT quantum queries. (That is not quite right- there are a lot of details I left out.)
   
2. A Strong Parallel Repetition Theorem for Projection Games on Expanders by Raz and Rosen. A parallel repetition theorem usually says that if the prob of (say) winning one game is p, then the prob of winning n games is pⁿ (That can't be quite right but that's the idea). The real question is how fast does the prob go down. This paper adds to our knowledge on this.
   
3. Share Conversion and Private Information Retrieval by Beimel, Ishai, Kushilevitz. I couldn't find an online version. If you know of one email the link please. The paper claims to unify and simplify PIR protocols!
   
4. Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Game by Aydinlioglu and van Melkebeek. There have been theorems along the lines of Lower bounds imply Derand. There have also been some (and this is one of them) along the lines of Derand implies Lower Bounds. As the author points out, when you first hear the result you may think one of two things: (1) GOOD NEWS- to get lower bounds, all I have to do is Derandomize! (2) BAD NEWS- to derandomize I HAVE to prove lower bounds, which are hard to prove. He claims a third interpretation of his paper- if you can derandomize then you can do so in a nice way
   
5. Hitting Set Generators for Sparse Polynomials over any Finite Fields by Lu. I could not find a link- if you know one email it to me.
   
6. Pseudorandom Generators for Read-Once ACC0 by Gavinsky, Lovett, and Srinivasan. Or see the talk on video from IAS.
   

Friday June 28 Morning Session

1. Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification by Cohen, Raz, and Segev. An extractor (informally) takes two strings and outputs a string that looks random. Strong Extractors and non-malleable extractors are stronger notions. Non-malleable extractors produce strings that look random, even to an adversary who is trying to make trouble. Hence they are good for Privacy Amplification. This paper has unconditional constructions of them!
   
2. Better Condensers and new extractors from Paravaresh-Vardy Codes by Ta-Shma and Umans I lose track of condensers vs extractors vs expanders vs dispersers.
   
3. List Decoding Barnes-Wall Lattices by Grigorescu and Peikert List decoding is when, instead of finding what a string decodes to, you find a small set of candidates, one of which is correct. What is a Barnes-Wall lattice? The paper does a good job on this. I wonder if the original paper by Barnes and Wall does as good a job?
   
4. Space-efficient algorithms for reachability in surface-embedded graph by Stolee and Vinodchandran. One of the consequences of there results is log-space algorithms for some graph-reachability problems. Maybe L=NL!
   
5. Space Complexity in Polynomial Calculus by Filmus, Lauria, Nordstrom , Thapen, Zewi. Proof complexity. While lower bounds on Resolution are well understood, what about more powerful proof systems? This paper is a good start on that.
   
6. Combinatorial PCPs with Short Proofs by Or Meir.
   I wish the PCP theorem itself had a short proof. Perhaps you can prove that it does.