Full Derandomization

What does the complexity world look like if we have hard functions that let us efficiently derandomize? All of the results in this post follow from the following open but reasonable hardness assumption.

There is some language L computable in time 2^O(n) such that for some ε>0, every algorithm A computing L uses 2^εn space for sufficiently large n.

First are the complexity class collapses. As always see the Zoo if some class does not look familiar.

• ZPP = RP = BPP = P
• MA = AM = NP. In particular Graph Isomorphism and all of statistical zero-knowledge lie in NP∩co-NP.
• S₂P = ZPP^NP = BPP^NP = P^NP
• The polynomial-time hierarchy lies in SPP. As a corollary PH ⊆ ⊕P ∩ Mod_kP ∩ C₌P ∩ PP ∩ AWPP

One can also derandomize Valiant-Vazirani. There is a polynomial time procedure that maps a CNF formula φ to a polynomial list of formula ψ_i such that

1. If φ is not satisfiable then all of the ψ_i are not satisfiable.
2. If φ is satisfiable then some ψ_i has exactly one satisfying assignment.

Beyond complexity classes we also get some randomized constructions such as creating Ramsey graphs. In polynomial in n time, we can generate a polynomial list of graphs on n vertices, most of which have no clique or independent set of size 2 log n.

This gives a short list containing many Ramsey graphs. We don't know how to verify a Ramsey graph efficiently so even though we have the short list we don't know how to create a single one. Contrast this to the best known deterministic construction that creates a graph with no clique or independent set of size 2^{(log n)o(1)}.

We also get essentially optimal extractors. Given an distribution D on strings of length n where every string has probability at most 2^-k and O(log n) additional truly random coins we can output a distribution on length k strings very close to uniform. The truly random coins are used both for the seed of the pseudorandom generator to create the extractor and in applying the extractor itself.

One also gets polynomial-time computable universal traversal sequences, a path that hits every vertex on any undirected graph on n nodes. The generator will give a polynomial list of sequences but one can just concatenate those sequences. The hardness assumption above won't put the sequence in log space, though we do believe such log-space computable sequences exist. Reingold's proof that we can decide undirected connectivity in logarithm space does not produce a universal traversal sequence though it does give a related exploration sequence.

There are many more implications of full derandomization including other complexity class inclusions, combinatorial constructions and some applications for resource-bounded Kolmogorov complexity.

On Being Color Blind

In the back of my high school Biology book had a big circle with many smaller circles and I clearly made out the word "color". That was easy I thought until I read the caption

If you see the word "onion" you have normal color vision. If you the word "color" you are red-green color blind.

Being color blind is like living in flatland. You miss a dimension and never notice until someone points it out to you. I grew up making the occasional color mistake but just believing everybody saw green and brown as different shades of the same color.

I have had more official tests that show me fully red-green color blind. I don't see the world in black and white; I don't even have trouble distinguishing red and green. I do see certain color pairs as different shades of the same color: green-brown, blue-purple, red-pink and yellow-orange.

As an undergrad I took a course in computer graphics and they did a demonstration where they showed a colorful picture and then showed three variations where they would turn off one color in each. The instructor said that the original and one of the variations would look the same to a red-green color blind person. Everyone laughed but I went up closely and couldn't tell the two apart.

One day shopping with my wife, she held up two shirts and asked me which one I liked better. They looked identical to me. I claimed she was playing games with me. Now with my knowledge of interactive proofs, I could have tested her: Mix up the shirts behind my back and make her tell me which was which.

My father-in-law is also red-green color blind which means my daughters had a 50% chance of being color blind, a rarity for females. We've tested them and neither is color blind, at least not to the extent that I am.

While color blindness has no cure or fix, it is one of the easiest disabilities to live with. My wife and daughters make sure my clothes match. I have trouble when people give color-coded talks but that doesn't happen often in theoretical computer science. I try to keep colors simple on my own talks and webpages. The Red-Green 3-D glasses don't work for me at all, though the newer polarized 3-D glasses work just fine. I don't usually have trouble at traffic lights but I do have trouble telling blinking red from blinking yellow. If I can't tell from context I just stop, sometimes to the chagrin of the car behind me.

But when I look at art or nature I see one less dimension of colors than most everyone else. I will never know what I am missing.

The Collected Works of Lance Fortnow

In the ancient days of the early '80s when you wanted a copy of a research paper and didn't have it in your library, you sent a stamped self-addressed envelope to one of the authors who would send the paper back to you.

I started graduate school in 1985 as a member of that new-fangled email generation. When I got an email request for a paper, I tried sending a LaTeX file, sometimes getting the response "What am I supposed to do with this? Can't you just send me the paper in the mail?"

But as people became more comfortable with email I got many more email requests for papers, and responding to those requests took some time. When the the web started in the early '90s I set up a page for people to download the papers. I would still get email requests for a while, responding to the request but with a reminder that they could download my papers online. Around 1994, there was a phase shift and I nearly stopped getting any email requests, everyone knew to look for downloads first. Now most researchers put copies of their papers online and shame on those that don't.

I use a now ancient version of bib2html to generate the publications page. It makes for a functional but not very pretty page. I use the same bib file to generate both the webpage and the papers list in my CV.

I tell this story because I made the first major change on my publications page in about ten years. It looks pretty much the same, but I added links in the titles to the official publisher's page for the paper. These pages often give an abstract and if you have permission you can download the "official" version of a paper. If you don't have permission you can still download the unofficial version from my page. The publisher's page also gives you a way to link to an official description of the paper without linking directly to a file, something I like to do when I link to papers in this weblog.

I tried to use DOIs when possible or other permanent links so the links shouldn't go bad. The IEEE and the IEEE Computer Society (publishers of the FOCS and Complexity proceedings) maintain two separate digital libraries with some overlap. When I had the choice I linked to the IEEE-CS version because at the University of Chicago we have access to the IEEE-CS downloads but not the general IEEE.

Many other researchers, for example Salil Vadhan, do far better than me, maintaining their own separate page for each paper and sorting their papers by research area. Those young scientists always showing up their elders.

A Metapost

A German student came up to me during the Complexity conference last week. "The Czechs beat the US in the World Cup"

That game happened a month before. "And the Italians beat the Germans. What is your point?"

"You had said in your weblog that the game would long be forgotten before you came to Prague and I wanted to prove you wrong."

I try to keep my blogger persona separate from my real persona and not talk about the weblog when I have conversations with my colleagues. Occasionally I would start to write something down, "Weblog Fodder" I'd say.

Still others bring up the weblog, usually asking the question about how much time it takes (as opposed to say any comments about the content of the weblog). So people will stop asking me, a typical non-technical post takes me about 15 minutes. The key is to not worry about perfection; people forget the silly or sloppy posts and will be very happy to point out any mistakes I make.

Then there are those who want to watch what they say to me because it might show up in the weblog. I try not to embarrass anyone or reveal personal information, but I do get most of my ideas from regular conversations with people. Anything you say to me is fair game.

Favorite Theorems: The Permanent

June Edition

The permanent of a matrix has a simple form

Perm(A)=Σ_σ a_1&sigma(1)a_2&sigma(2)···a_n&sigma(n)

where A is an n×n matrix, a_ij is the element in the ith row and jth column and the sum is taken over all permutations σ of {1,…,n}.

Very similar to the determinant except without the negations and a 0-1 permanent counts the number of perfect matchings on a bipartite graph. But while we can compute the determinant quickly and easily check if a graph has a perfect matching the permanent turns out to have an apparently much higher complexity.

Leslie Valiant, The Complexity of Computing the Permanent, TCS 1979.

Valiant shows that computing the permanent, even for 0-1 matrices, is #P-complete, i.e., as hard as counting the number of solutions for NP problems.

While an important hardness result in its own right, Valiant's theorem becomes even more important with later work. Toda's theorem implies the permanent is hard for the entire polynomial-time hierarchy. The permanent also has two very important properties:

1. The permanent on n×n matrices is easily reducible to solving the permanent on (n-1)×(n-1) matrices.
2. The permanent is a multilinear polynomial on the entries of A.

Those two facts, combined with Valiant's and Toda's theorems, helped the permanent play a critical role in the development of interactive proofs and in some derandomization results, most notably Impagliazzo-Wigderson and Impagliazzo-Kabanets.

The Science and Art of Computation

Amir Michail writes

I was wondering if you might comment on the history behind the formation of computer science, and in particular, on the subsequent overwhelming emphasis on implementation (studied via science/math), rather than specification (perhaps better studied as an art?).

One might argue that two fields should have formed, analogous to architecture and engineering say.

Sure, the implementation part is important (e.g., efficiency), but what to implement should be equally important.

Sure, there are a few subfields of computer science where people try to come up with new sorts of applications, but I think this is worthy of much greater emphasis, a different undergraduate program, a different research methodology (perhaps not so "scientific," but more like "art"). Moreover, I suspect that completely different sorts of people would be attracted to this field.

The MIT Media Lab is perhaps the best example of what such a field would look like.

Would you make the same arguments about physics or biology? Computer science is foremost a science and trying to understand the nature of computation has its own beauty just like trying to understand the fundamental building blocks of the universe.

Can one teach "what to implement" any more than an art class can teach "what to paint"? Best for us to teach the theory and tools of computation and then let the world find neat ways to use computers as they already have in countless ways.

Going Home

Today I fly back to Chicago ending my three country European tour. During this Complexity Conference I stepped down from my role as chair of the conference (organizing) committee and leave the conference in the very capable hands of Pierre McKenzie. I truly enjoyed running the conference over the past six years, particularly in working with different program committee and local arrangement chairs each year. It is time for another leader, but I will miss this role in the conference that has been so central in my academic career.

Other notes from the business meeting:

Pavel Pudlak and Eric Allender are the new members of the conference committee taking over for Harry Buhrman and Avi Wigderson ending their three-year terms.

This year we decided to discontinue the Complexity Abstract program. The abstract program let people write up a one page abstract on any of their papers and Bill Gasarch (later Steve Fenner) would collect and distribute electronically before the conference. The conference started program back in the 80's when people who didn't have their papers in the conference wanted a forum to announce their results. But now with the ECCC and the arXiv, we no longer need this program.

The 2007 Meeting will be June 13-16 at FCRC with STOC and other conferences. Peter Bro Miltersen will be PC chair. There will not be a joint session with STOC as we had at previous FCRCs though there will be some coordination in scheduling the talks during both conferences. The 2008 meeting will be at the University of Maryland.

Complexity Day 1

The Complexity Conference got underway yesterday with an invited talk by Pavel Pudlak on the connections of Gödel's work and computational complexity. Kurt Gödel was in 1906 is what is now Brno in the Czech Republic.

The next talk "Polynomial Identity Testing For Depth 3 Circuits" by Neeraj Kayal and Nitin Saxena is the first paper in Complexity history to win both the best paper and best student paper awards. The main result showed how to deterministically check whether an algebraic circuit was identically zero when the circuit has depth 3 with bounded fan-in on the top gate. Their advisor Manindra Agrawal was program committee chair but he did take the proper precautions in the discussions of the awards.

We had a reception last night at the Michna Palace in Prague. One young student remarked how one must be the smartest person in the world to prove new theorems. Not at all true. We have different backgrounds, different strengths, different experiences, different views on complexity that sets a situation where I can prove something that someone else would struggle with while they can prove something I would never find. Even if you have a similar background to someone "smarter than you", they don't have time to work on every problem so you can find good ones to work on your own.

Most of all my advice is to not worry about others and just work on your own. Be sure to have fun doing your research because if you are not having fun you won't be successful and you can likely make more money doing something else that isn't fun.

Complexity in Prague

I have arrived in Prague for the Conference on Computational Complexity, my favorite conference as you might guess from the name of the weblog. STOC and FOCS get a broader crowd but many of my fellow researchers from the past two decades come to this conference most years and I enjoy talking with them, catching up with research and with life. Just last night I had dinner with Lisa Hellerstein (a COLT person crashing our conference) and Manindra Agrawal, fresh from receiving his Gödel Prize last week at ICALP in Venice.

Blogging will likely be light this week as the conference keeps me busy and I once again have limited Internet access.

One of the students in Chicago had planned to go yesterday to Israel to work for a month with Eldar Fischer at the Technion in Haifa. He postponed his trip, no so much because of the danger, but because getting to Haifa has become very difficult and the University has temporarily closed. The Technion, aka The Israel Institute of Technology, has by far the largest collection of theoretical computer scientists at any single university. Haifa University also has a nice theory group. We sincerely hope the situation resolves itself quickly and they can return to a sense of normalcy, as normal as one gets in that region.

Principles of Problem Solving: A TCS Response

Peter Wegner and Dina Goldin are at it again. The following is from their Viewpoint article Principles of Problem Solving in the July CACM.

Theoretical computer science (TCS) asserted in the 1960s that Turing machines (TMs)—introduced by Turing to help show the limitations of mathematical problem solving—provide a complete model of computer problem solving by negating Turing's claim that TMs could solve only functional, algorithmic problems. The TCS view ignored Turing's assertion that TMs have limited power and that choice machines, which extend TMs to interactive computation, represent a distinct form of computing not modeled by TMs.

In the 1960s theorists (such as Martin Davis of New York University) adopted the inaccurate assumptions that "TMs completely express computer problem solving" as a theoretical (mathematical) foundation of the computing discipline. The TCS model is inaccurate because TMs express only closed-box functional transformation of input to output. Computation is not entirely mathematical, since broader models of thinking and research are needed to express all possible scientific and engineering questions. Computational problem solving requires open testing of assertions about engineering problems beyond closed-box mathematical function evaluation.

The "Choice Machines" from Turing's paper are just what we now call nondeterministic Turing machines. In Endnote 8 of his paper, Turing showed that the choice machines can be simulated by traditional Turing machines, contradicting Wegner and Goldin's claim that Turing asserted his machines have limited power.

But more importantly Wegner and Goldin misinterpret the Church-Turing thesis. It doesn't try to explain how computation can happen, just that when computation happens it must happen in a way computable by a Turing machine.

I admit the original single-tape Turing machine does not model interaction as Wegner and Goldin state. Nor does the Turing machine model random-access memory, machines that alter their own programs, multiple processors, nondeterministic, probabilistic or quantum computation. But what that single-tape Turing machine can do is simulate the computational processes of all of the above. Everything computable by these and other seemingly more powerful models can also be computed by the lowly one-tape Turing machine. That is the beauty of the Church-Turing thesis.

The ongoing support for rationalist over empiricist modes of thought (despite repeated questioning by some philosophers) suggests that human thinking is inherently more concerned with the rationality of human desires than with the empirical truth of human reasoning. Our empirical analysis of interactive problem solving continues to be criticized by incorrect rationalist arguments about the strong problem-solving power of TMs, which are accepted as the proper form of valid reasoning, even though they were contradicted in 1936 by Turing himself.

We hope you accept that empirical (open) reasoning is often more correct than rationalist (closed) arguments, and that modes of thought about truth and problem solving should promote empiricist over rationalist reasoning, as well as definitive truth over questionable a priori value judgments.

Call me a rationalist then as I continue to hold the belief that no matter how complicated the computational model, we can still use the simple Turing machine to capture its power.

Bouncing a Little French Girl

Those who know me well know my addiction to junk food, often referred to as "Lance Food" during my graduate school days. America has its great variety of such culinary delights like Cheesesteaks and Buffalo Chicken Wings but Europeans do very well on their own going well beyond the omnipresent American chains.
 
In Amsterdam I always go for the Uitsmijter (literally "Bouncer", like at a club), basically an open-faced sandwich with fried eggs on top. I usually go for the Rostbief Uitsmijter and the Ham-Kaas version (Ham and Cheese and the Eggs) can really clog those arteries.
But the Uitsmijter is downright healthy compared to the Porto delicacy Francesinha ("Little French Girl"). One starts with a thick slice of bread then add layers of ham, steak and sausage. Cover with another slice of bread and pour melted cheese on top. Then add the fried egg and smother the whole thing in gravy. Right now Porto is having their Festa da Francesinha by the river where restaurants from all over the city come to offer their versions of the Francesinha.
Luis Antunes says "A little bad food is good for stomach every now and then." After eating a Francesinha at lunch today I'm not sure my stomach agrees.

Useful Information

In our sixth Complexitycast live from Portugal, Luis Antunes talks about the Portugal view of theory, research and of course the World Cup. MP3 (13:26, 2.3MB)

Naming Complexity Classes

How do complexity classes get named? A proposal gets submitted to the Complexity Class Naming Commission (CCNC) which makes sure the class was not already named and the name has not been used before. The CCNC then puts out a Request for Comments to the community. Once the community responds, sometimes giving other suggestions for the name, the CCNC makes a formal recommendation to the Complexity Governing Council. The Council takes a final vote on the name.

If only we were so organized. Complexity classes get their name usually from the authors who invent them or occasionally by a later paper if the first paper didn't name the class or gave it an unmemorable name. Too often researchers will give a temporary name so they can work with a class and then keep that name out of laziness. Maybe I've been guilty of this a few times myself.

I could write several posts on badly named complexity classes. For now let me mention two important ones.

• NP for Nondeterministic Polynomial Time. But "nondeterministic" is not very descriptive. Logically ∃P would be better or PV for Polynomially Verifiable.
• PP for Probabilistic Polynomial Time. Since the error is not bounded away from one-half, the class is not a useful characterization of probabilistic computation. A better name would be Majority-P or just MP. BPP would then get the proper name PP and BQP would be just QP.

Someone asked me how to get their class into the Complexity Zoo. You can submit a proposal to the CCNC or just realize the Zoo is now a wiki and edit it yourself.

Definitions of Advice

When Karp and Lipton showed that if NP had polynomial-size circuits the polynomial-time hierarchy collapses, they also give a general definition of nonuniform complexity.

Let C be a class of languages and F be a set of functions. The class C/F is the set of all languages L such that there exists an A in C and an arbitrary f that maps n to strings with |f(n)| in F such that x is in L ⇔ (x,f(|x|)) is in A

Seems natural but this definition has given complexity theorists headaches for many years. The definition works fine for the applications in the Karp-Lipton paper, but it loses the semantic meaning of complexity classes in general.

In particular consider (NP∩co-NP)/poly. We need an A in NP∩co-NP for the definition above, but note that means we need two NP machines that accept complementary languages even for all possible advice strings, not just the correct one. In our toolkit paper we give a relativized world where NP/1∩co-NP/1 is not contained in (NP∩co-NP)/poly. We don't even know if (NP/poly)∩co-NP is contained in (NP∩co-NP)/poly.

At least we can use the terminology NP/poly∩co-NP/poly to nicely capture the class we want. For other classes like BPP/log we have no such clean notation. Once could make some new notation (someone suggested C//F) but instead we usually just state early on that we are not using the official Karp-Lipton terminology and only require the BPP behavior for correct advice.

Karp and Lipton did nothing wrong. They use a very natural definition that works for their purposes. Unfortunately the natural definition does not match the natural interpretation for all classes and will continue to confuse inexperienced complexity theorists for years to come.

On to Portugal

At noon today, as I was checking into my flight to Porto, Heathrow Airport went quiet, part of a nationwide two-minute memorial for the London bombing victims of a year ago. Machines were turned off and everyone stopped talking and just contemplated. The silence was deafening.

So starts the second leg of my journey, a visit to colleague Luis Antunes. As a commenter mentioned I am in Europe but not going to ICALP next week in Venice despite having a paper there. I greatly enjoy going to conferences and workshops but find them quite exhausting and going to three meetings in a row is more, especially with the large and broad ICALP in the middle is more than I can handle. For those in Venice, enjoy the conference and good luck to Italy in the WC final. Afterwards, come on up to Prague for Complexity.

At the workshop in Bristol, the projector was a bit dim and we had some problems reading some colors, green on the white background and red on a black background. This led to a heated discussion on what backgrounds to use. Harry Buhrman argues for white, as one can see the text best. Any background color can work, as long as you don't use too many different colors for text and carefully choose contrasting colors. Though I find any plain color, especially white, a bit boring. I typically use one of the Powerpoint defaults, which Microsoft has designed to both look pleasant and have good readability.

Complexity and Randomness

The Complexity and Randomness workshop in Bristol has an unusual mix of researchers in random graphs and mixing (the British) and complexity (the rest of us). For example Colin McDiarmid talked about the maximum degree of a random planar graph (Θ(log n)) and Mark Jerrum on Monte Carlo mixing methods, in addition to Irit Dinur on her PCP proof, Oded Goldreich on pseudorandomness and coming up Luca Trevisan on Gowers uniformity and Vijay Vazirani on markets.

I don't go to England much because they don't have many researchers in computational complexity, so I get a rare chance to talk to many of the researchers in this area. These workshops give us a chance for us to tell them about the latest in complexity and I can learn about areas I don't keep up with as much as I should.

Leslie Ann Goldberg gave a neat talk on the hardness of estimating the Tutte polynomial of graphs on a variety of points. I never really learned about the Tutte polynomial; it has some cool properties that for various parameters can count properties of graphs such as number of connected components. Goldberg and Mark Jerrum showed some of the approximations are #P-hard, that is hard for counting solutions of NP problems. We rarely see #P-hardness for approximating as all #P problems can be approximated probabilistically with an NP oracle. The Tutte polynomial is harder to approximate on some negative values because of the cancellations given by negative terms.

England on the 4th of July

I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portugal and ending up at the Computational Complexity conference in Prague.

I will celebrate American Independence Day in the country we declared independence from, and not for the first time. You see many European conferences and workshops around this time. You don't notice Independence Day at all in England, the English being more upset at their lost in Portugal in the World Cup then their loss in an 18th century war.

I'm rooting for Portugal to win against France in the semifinals, since I'll be in Portugal for the final game and also because they are playing the French.

Blogging will be light this week as Internet access is not that easy; the Marriott here charges 15 Pounds/day for wireless access, shame on them.

If you don't normally read comments, the recent post on FOCS accepts has generated a record number of comments for this weblog. Check it out and join in the discussion. Nothing gets the emotions up more than discussing the importance of various conferences.

England on the 4th of July

I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portugal and ending up at the Computational Complexity conference in Prague.

I will celebrate American Independence Day in the country we declared independence from, and not for the first time. You see many European conferences and workshops around this time. You don't notice Independence Day at all in England, the English being more upset at their lost in Portugal in the World Cup then their loss in an 18th century war.

I'm rooting for Portugal to win against France in the semifinals, since I'll be in Portugal for the final game and also because they are playing the French.

Blogging will be light this week as Internet access is not that easy; the Marriott here charges 15 Pounds/day for wireless access, shame on them.

If you don't normally read comments, the recent post on FOCS accepts has generated a record number of comments for this weblog. Check it out and join in the discussion. Nothing gets the emotions up more than discussing the importance of various conferences.