Logic Meets Complexity Theory
A summary of the 2010 ASL conference
Bob Coecke is a lecturer from Oxford, who gave a series of three invited talks on quantum information theory at the 2010 ASL meeting. He is a terrific speaker, and has a way of using pictures to give the best explanations I have ever seen—or heard—of complex quantum concepts such as teleportation.
Today I will talk about his presentations, Alexander Razborov’s award talk, and our complexity session given in Razborov’s honor at the ASL conference. ASL is the Association for Symbolic Logic.
The ASL meeting was quite enjoyable—being in Washington D.C. during several days of beautiful weather did not hurt either. ASL is a relatively small meeting, but has a strong energy and excitement about it. I would definitely plan on going again, and anyone interested in hearing very strong talks on foundational issues should go to one of their meetings.
The ASL group does some things a bit differently from STOC and FOCS and other theory meetings. Their meeting has several invited and special one hour talks, as well as shorter 30 minute contributed talks. The latter are arranged in parallel sessions, but these sessions are very inclusive and essentially all get a chance to speak. ASL also does an interesting “trick” with their tutorials: the tutorial was broken into three one hour talks given over three consecutive days. I liked this approach very much.
A Picture is Worth a Thousand Qubits
Coecke uses pictures of a special kind to explain quantum information processing. This, in his hands, is in my opinion extremely insightful, and helped me really “get it.” I thought I would try to give an over view of what he does with his wonderful pictures. If you want to see the real thing go here for the full story. He uses pictures like these to explain quantum teleportation and other operations:
The intuition is each diagram represents a physical experiment. He has a small set of simple rules: diagrams can be changed into other ones by applying a rule. In this was he can show how a complex looking quantum setup is really equivalent to something often much simpler. This allows insight into why things work the way they do. The figure above starts out with a complex entanglement, and finally gets a simple transfer of bits. Very neat.
The Gödel Lecture
Alexander Razborov was the Gödel Speaker at this ASL meeting. He has won so many honors already, but it is quite fitting he was selected to be the 2010 Gödel Lecturer. The past lecturers include: Per Martin-Löf, Michael O. Rabin, and Harvey Friedman. Alexander was a wonderful choice for this year.
His talk was on the complexity of proof systems—one of his main loves—as he stated. Interestingly, he started by showing the original Gödel Lost Letter, in German. And he asked,
“Is it big enough? Can everyone read it? Let me make it bigger.”
Then, he showed an English version. After a good laugh, he went over the letter in some detail. He pointed out Gödel was interested in the difficulty of finding proofs in the predicate calculus, not in propositional calculus.
Next Alexander spoke about Sam Buss’s work on a logical theory that captures polynomial time. The theory is named : Alexander said he would explain the name if anyone wished to hear, but there were no takers. I know a bit about this part of logic, and in my opinion it would be well served if it used better names for what are essentially subtheories of Peano Arithmetic. Cryptography picks such great names for its concepts, complexity theory does a good job with names, but the study of weak fragments of arithmetic does not.
Buss’s logic is essentially Peano Arithmetic with a weaker induction principle:
In this system a proof of any formula of
implies there is a polynomial time computable function so
is also provable. The intuition you should have is that the correctness of depends on the correctness of and this depends on This fast decreasing sequence is the reason the logic is weaker than Peano—to prove this is hard, but this is intuitively why the induction is weaker.
Alexander pointed out if this theory could prove Fermat’s Little theorem, then there would be a factoring algorithm. I raised my hand and after being called on, asked Alexander one of those questions—a question you think you know the answer but want to check—could Sam’s theory prove there are an infinite number of primes? There was some discussion with Alex Wilkie, the session chair and the conclusion was it was not known. My question was motivated by a recent one of Ryan Williams: is there a deterministic polynomial time procedure to find a prime greater than ? If Sam’s theory could prove there are an infinite number of primes, I believe there would be such a deterministic function. Razborov then switched to talk about what he called the “golden age” of progress on lower bounds for circuits and proof systems—the 1980’s. As you might expect he then outlined his famous work on Natural proofs with Steven Rudich.
He then ended with an appeal for others to work on these foundational issues, and quite kindly offered to answer questions from anyone in the future. It is clear he is really dedicated to eventually understanding the great mystery of why proving tautologies is hard. A wonderful talk, filled with ideas, his personal insights, and hope for the future of the field.
Our Complexity Session
Our session was four 30 minute talks, each speaker could easily have used an hour to explain the details of their area. I will probably discuss several, if not all, of the talks in the future.
Jin-Yi Cai gave a talk on his beautiful theorem on characterizing the power of graph homomorphism. I will not define what they are, but will say such homomorphism can be used to capture many properties of graphs: for example 3-coloring. The area was started in 1967 by László Lovász, and is a natural idea: in many aspects of mathematics the right thing to study is not the “objects” but the mappings between the objects. Cai’s work is in this spirit and he has proved a kind of gap theorem:
Theorem: For every property of a certain type, either counting the number of configurations with the property is in polynomial time or is P hard.
I am not getting the statement exactly right, so look here for more details.
Ken Regan gave a highly speculative view of some new ideas he is working on in the area of arithmetic circuit lower bounds. Ken is an expert in this area and his idea is to add the function to arithmetic circuits for unit cost. His hope is allowing this powerful operation could shed new light on old lower bounds, and perhaps yield new results. The work is just starting and it could be quite fruitful, especially since his method appears to avoid the usual major barriers to lower bounds.
Ryan Williams gave a beautiful summary of the known lower bounds on SAT. The results he considered are all of the form: a Turing Machine for SAT that uses space requires at least time. There have been a series of results, but he has the best with .
Lately Ryan has been working with Buss, the same Buss, on extending the value of beyond . Hopefully they will have some results soon. As someone who proved some of the earlier results, I always thought one day we might at least get . But, who knows.
Nisheeth Vishnoi gave a masterful view of approximation theory. At the 50,000 ft level, perhaps really the 50,000 mile level, I believe this is his key insight: there is a natural way to unify approximation upper and lower bounds into one coherent technology.
I will try to explain the most high level view of what he is doing. I definitely plan to discuss in much more detail in the near future. My first version was more like at the 50,000 million level—it was also wrong—so I will quote Nisheeth:
For a problem and an instance for it, let and be two ways to measure cost of . For instance, could be the LP value of , and could be the cost of an integral assignment obtained from a particular way to round the LP solution of .
Then, often, it can be shown that assuming the UGC (Unique Games Conjecture), one can construct a reduction based on from Unique Games to which outputs instances of such that it is hard to decide between:
Note that is the instance output by the reduction and is the starting instance on which the reduction is based.
[Fixed this section.]
One open problem is to try and use Sam’s logic to solve the prime finding problem. Another is to try and improve the bound on SAT of Ryan. These lower bounds are quite weak: the algorithms do not even have enough memory to write down one potential assignment to the variables. Yet it is the best we can do.