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!

MikeFest

I rarely highlight individual events on the blog, but one's advisor only turns sixty once. We will honor Michael Sipser at MIT on Sunday, October 26 with a one-day symposium full of great speakers in complexity. As one of Sipser's PhD students, I'm helping to organize the event and serving as emcee for the dinner speeches. Please send me any funny or embarrassing stories or pictures of Sipser through the decades.

Many of you know Sipser from his popular textbook Introduction to the Theory of Computation. Sipser was one of the driving forces in complexity in the 70's and 80's. Sipser initiated the program of using circuit complexity to separate complexity classes and, with Merrick Furst and James Saxe, showed parity could not be computed by poly-size constant-depth circuits. His research includes how to simulate randomness by alternation, was the first to explore hardness vs randomness, made great advances in the complexity of interactive proofs, and much more. Sipser led the MIT Mathematics department for the last ten years and was recently appointed Dean of Science.

Join us in Cambridge for this great day to celebrate an extraordinary man.

---------------

P.S. STOC call posted, Deadline November 4

Typecasting in Dagstuhl

After this pre-recorded typecast, we learned of the tragic death of Alexey Chervonenkis, the C of VC dimension, a huge loss to the learning community. We’ll have a proper obit soon. Now onto the typecast.

Lance: Hello and welcome to Dagstuhl for our first typecast since the 2014 Complexity Conference. Howdy Bill.

Bill: Hi Lance. Are you enjoying Dagstuhl?

Lance: I always have fun at Dagstuhl especially when you are here Bill.

Bill: I have not seen you at many talks.

Lance: So maybe you should go to more talks Bill.

Bill: Never mind. As you told me Scott is writing a blog book. Should we too?

Lance: Something we discussed many times.

Bill: How about a slightly different idea? At the end of this year you will have had FIVE lists of TEN best theorems. (Doing math in his head) That’s FIFTY theorems. There’s a book with a unified theme.

Lance: And I’m glad you’re going to write it.

Bill: That’s not exactly what I had in mind. But I’m happy to help you write it?

Lance: Do you think there are people who would want to buy this book?

Bill: I need your help BLOG AUDIENCE. Leave a comment to say if you would read this book. Would you read the book if you have to pay for it?

Lance: I certainly wouldn’t.

Bill: You don’t count. But they (points to the audience) do. [Bill leaves to get ice cream and comes back] I’m sure it will sell well in Silicon Valley.

Lance: Speaking of Silicon Valley, that was one tough post to write on MSR-SVC, basically an obituary post for a research lab.

Bill: Isn’t rather grim calling it an obituary?

Lance: Exactly.

Bill: Do you always give one word answers?

Lance: No.

Bill: You are man of few words.

Lance: You are a man of a few words too many.

Bill: Yes, I like to keep conversations flowing.

Lance: Indeed you are of the few extroverts in complexity. Introverts like me think deeply of what to say before we say it.

Bill: Did you just insult me? How did an introvert like you become a department chair?

Lance: I fake it well. [Quickly changing topic] I hear there’s exciting news out of Maryland. And I’m not talking about the Orioles.

Bill: We’re getting a new building, The Brendan Iribe Center for Computer Science and Innovation.

Lance: Because there’s no innovation in computer science. Brendan who?

Bill: He co-founded Oculus which was sold to Facebook for Ackerman of O(1) dollars.

Lance: Sounds exciting. It is one pretty ugly building you are in now.

Bill: Moving on, how the Complexity Conference in Vancouver?

Lance: You didn’t read my blog post?

Bill: [Reading blog post] Wow, no best paper and only 66 participants. Seems a bit lower than last year.

Lance: We were correlated with STOC last year and next year at FCRC as well. Though not with the IEEE anymore.

Bill: Is complexity theory dying?

Lance: The talks at this Dagstuhl alone prove otherwise.

Bill: I particularly liked David Zuckerman’s talk about using statistical sum-product theorems to create non-malleable codes. Why is it so empty in here?

Lance: It’s a rare sunny day at Dagstuhl and we’re inside doing this typecast. What other topics are exciting you at Dagstuhl?

Bill: There’s a resurgence of interest in VP and VNP, Valiant’s algebraic analogues of P and NP and genuine optimism that VP <> VNP might be provable in the near future.

Lance: There is some great work there but let’s wrap this up while we have still have some daylight.

Bill: You know what to say Lance.

Lance: In a complex world, best to keep it simple.

Goodbye MSR-SVC

This week I'm back at Dagstuhl for the Workshop on Algebra in Complexity Theory. Bill is here as well and we hope to have a typecast for you later this week.

The big discussion is the closing of Microsoft Research in Silicon Valley last week. The 50 researchers at MSR-SVC included 15 in a strong theory group. Luckily I captured the page last night as Microsoft has eliminated all mention of the lab from its web site. Just like the novel 1984: Microsoft doesn't have a research lab in Silicon Valley. Microsoft never had a research lab in Silicon Valley.

I visited MSR-SVC a couple of times, once inspiring a 2005 blog post on The New Research Labs. Cynthia Dwork was just starting to think about differential privacy. Jason Hartline, then a researcher at SVC, would later help me grow theory at Northwestern. In 2008 I took a trip there with Northwestern economist Mark Satterthwaite talking on how to connect CS and economics.

Omer Reingold, a favorite theorem author, writes his farewell to MSR. Sergey Yekhanin was supposed to be at Dagstuhl this week but unfortunately cancelled after getting the news. There have been rumors of changes in Microsoft Research since Satya Nadella took over as CEO but the suddenness of the closure of MSR-SVC took everyone by surprise. Computer scientists sent out on the streets well-off the usual hiring cycle. Many other Bay Area institutions will try to help in the short term and I would hope these researchers will find a new permanent home by the next academic year. Luca and Michael also chime in.

Industrial labs come and go but we should remember their legacy. Even as the scientists move on, the research they produce always remain part of our discipline.

Gentry and Lurie and Zhang can say they are geniuses without bragin'- MacArthur Geniuses

(If I mispell anything in this post, well, that"s why I'm not a MacArthur Genius, or any other kind of Genius.)

Craig Gentry, of homomorphic encryption fame, won a 2014 MacArthur Genius award.  here is an article about it and a description of his work, which is understandable to most non-genius's.  It is great work and I am glad to see the work and him honored.

Have other computer scientists won it? Yes. Have other CS theorists won it? Yes. Here is a list, though it may be incomplete: Peter Shor (1999), Erik Demaine (2003), Jon Kleinberg (2005), Daniel Spielman (2012).

Jacob Lurie who does very abstract mathematics, also won a 2014 MacArthur genius award. He won the Breakthrough prize earlier (3 million dollars) and the MacArthur (650,000) so he owes me 3650 lunches (I mentored him in HS and hence get a free lunch for every 1000 he wins). Here is an article about it and a description of his work which is not understandable even to most math genius's. Its not the articles fault- its just very hard to describe very hard and deep mathematics unless you can relate it to a very concrete thing like crypto (or other applications) or some things in number theory- you can at least tell someone the statement of Fermat's last theorem. I am sure its great work--- he seems to be generalizing math to an unprecedented degree. Note that the generality does pay off to solve real problems, for example this paper.

Yitang Zhang, who proved that there is a constant c such that infinitely  often there are primes that are c apart (he proved c ≤ 70,000,000 but its been gotten down to 246 - see here)  also won the 2014 MacArthur genius award. While the proof is hard the result can be explained to anyone. See here for an article about his prize and his result.

Have other mathematicans won it? Yes, around 31 total including the two this year.Two that I will note- Terry Tao and Andrew Wiles.

Maryland Theory Day October 10!

Univ of Maryland at College Park is having a Theory Day
Friday October 10.

Free Registration and Free Lunch! (there are no economists coming to tell us there is no such thing).

For Information and Registration goto here

A good way to learn lots of current theory in a short time.

Schedule:

8:30-9:00 Light Breakfast and Intro Remarks

9:00-9:20  Gasarch, UMCP
NIM with Cash

9:25-9:45  Mount, UMCP
A New Algorithm for Approximating the Euclidean Minimum Spanning Tree

9:50-10:10 Samir, UMCP:
To do or not to do: scheduling to minimize energy

10:20-11:00 Coffee Break

11:00-12:00 Distinguished Invited Speaker Avrim Blum, CMU
Reconstructing preferences and priorities from opaque transactions

12:00-1:00 Catered Lunch

1:00-2:00 Distinguished Invited Speaker Sanjeev Arora, Princeton
Overcoming the intractability bottleneck in unsupervised learning.

2:00-2:30 Coffee Break

2:30-2:50 Elaine Shi, UMCP
Circuit ORAM and Tightness of the Goldreich-Ostrovksy bound

2:55-3:15 David Harris, UMCP
The Moser-Tardos Framework with Partial Resampling

3:20-3:40 Mohammad Hajiaghayi, UMCP
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond

3:45-4:05 Michael Dinitz, JHU
Explicit Expanding Expanders

4:10-5:00 Poster Session in 2120 (Grad Students)

Richard Lipton Wins Knuth Prize

Georgia Tech professor and fellow blogger Richard Lipton will receive the 2014 Knuth Prize at the upcoming FOCS conference in Philadelphia. The Knuth Prize is given jointly by the ACM SIGACT and the IEEE TC-MFCS for major research accomplishments and contributions to the foundations of computer science over an extended period of time.

Lipton's research has major results across a large spectrum of theoretical computer science from probabilistic algorithms to DNA computing to communication complexity. I'd like to highlight a couple of his papers in computational complexity hugely influential, including much of my own research.

Richard Karp and Lipton showed that if NP has non-uniform polynomial-size circuits then the polynomial-time hierarchy collapses. The result, and its successors, are a powerful tool, used to show a number of interesting hypotheses are not likely to happen, and plays an important role itself in circuit lower bounds and pseudorandomness. Most importantly Karp-Lipton showed gave the strongest evidence that NP does not have small circuits, justifying the circuit lower bound approach to separating complexity classes.

In lesser known but perhaps even more influential work, Lipton developed a notion of program testing and showed how to test the permanent function, a result that directly led to the surprising power of interactive proofs. This algebraic characterization of hard problems led us to IP = PSPACE, MIP = NEXP and the PCP theorem.

Again this just covers a sliver of his impressive canon of research. Congrats Dick!

Beyond the Commodity

Back in 2005 I lamented the fact that students viewed computers as a commodity, a tool they use, like an automobile, but have no reason to understand how or why it works. In 2011 I noticed a change, that computers like IBM's Watson were starting to make computer science cool again.

Now we are in the midst of yet another major change, reflected in refound interest in high school computer science, and the huge enrollment growth in universities, particularly in non-majors taking upper-level CS courses. Jobs certainly drive much of this enrollment but for an important reason. Basic computer science principles and reasoning have become a critical tool in almost any business. Every large company tries to glean knowledge from data, deal with security and privacy challenges, and solves big optimization questions in an ever complex environment. I've been told that car companies will take as many Mechanical Engineering major with CS minors as Georgia Tech can produce. For what are cars today but computers on wheels.

We've been down this path before, and trends that seem to be with us forever die out leading to computer science disillusionment. Somehow this seems different, but we'll just have to wait and see.

A Statistical oddity ?

 I keep a list of people that are famous-to-me  that are old so that if someone dies I won't be surprised. When Lauren Bacall died  recently I  (1) knew who she was, AND (2) knew she wasn't  already dead. I DO NOT look at lists of celebs. My  list is organic- if I think of someone  who seems old (`GEE, I wonder if that famous probabilist Monty Hall is still alive? He is! He's 92.) I look it up and if they are over 80, they go on the list. Most people are surprised to know that Dorris Day is still alive.


Okay, so what of it? Bill has  another weird hobby. (Add this to collecting satires,  collecting papers that apply Ramsey Theory, and writing a  satire of papers that apply Ramsey theory).

 I decided to see how many people on my list had the same birthday and see if it was reasonable with regard to probability (the birthday paradox and all that). The list currently has 70 people.

What I found was probably reasonable in one respect and odd in another.

REASONABLE: Nine pairs had the same birthday. One triple had the same birthday.

ODD: There were NO pairs or triples of same birthdays in July,  September, October, November, or December.

I leave as an exercise: How reasonable is what I called reasonable and how odd is what I called odd?

Favorite Theorems: Quantum Interactive Proofs

Practical quantum computing still has many hurdles to jump through, but the quantum computing model does generate great complexity questions and often surprising answers.

QIP = PSPACE by Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous. 

QIP is the quantum analogue of interactive proof systems. Since IP = PSPACE we get the consequence QIP = IP, that quantum doesn't give an advantage over classical randomness in the interactive proof model. I wouldn't read too much into that interpretation, more that we have a strange situation where IP is far more powerful than we initially suspected and that QIP is weaker than expected and so we get the collision at PSPACE.

QIP ⊇ PSPACE follows from IP = PSPACE. In an earlier paper, Kitaev and Watrous show QIP ⊆ EXP by reducing QIP to an exponential-sized semi-definite program. This papers applies a clever matrix multiplicative weight algorithm to approximate a subclass of SDPs to achieve QIP ⊆ PSPACE.

We've also seen progress on QMIP, quantum interactive proof with multiple entangled provers who cannot otherwise communicate. QMIP containing MIP=NEXP remained open for a long time because the provers might use entanglement to cheat. Ito and Vidick show that entangled provers can't get an advantage on the multilinear test used in the original MIP=NEXP paper, and thus QMIP does contain NEXP. QMIP contained in NEXP remains open.

How hard is changing fields? Ask Sheldon!

In the last season of  The Big Band Theory Sheldon wants to change field from String theory to something else (I don't recall if he settled on what it would be, though Standard Model Physics, Quantum Loop Gravity, Calculation of nuclear matrix elements, were mentioned negatively, and Geology is, according to Sheldon, not a real science.)

Sheldon faced opposition from his department. And since Physics is... hard... changing fields seems hard.
How hard is it to change fields, both intellectually and in terms of your dept?

1. If you are hired as a string theorist and you are one of the only ones in your dept, your dept may quite reasonably ask you to still teach string theory. I think this is fine.
2. Math and Physics are far older than CS so to change fields requires learning more background knowledge. In CS it was easier about 20 years ago, but CS has grown so much that I suspect it would be harder now.
3. There may be a time when you have less papers and grants as you are making the transition. Hence it may be unwise to do this before you get Tenure.
4. If your dept hired you to do String Theory and you change to Calculation of nuclear Matrix elements should they mind that? I would think that as long as it's still good work they wouldn't. And they should give you enough time to get grants and papers in it. If you change to a field they don't care about, or change to a field not in the area they might not like that. If Sheldon went into Computational Complexity then would his dept (physics) be justified in not liking that?  If he solved P vs NP then all would be forgiven.
5. Perhaps the further away you change from your field the better your work has to be before your dept doesn't mind. This could be modelled by a formula. Maybe Sheldon will change to computational dept dynamics and derive it for us.
6. The obvious thing to say is Depts should allow their professors to wander free as a bird and not erect arbitrary walls since the best work comes from people not being constrained. I would like to think this is true but I wonder--- how many people have changed fields and ended up doing great work? good work? totally failed?