A Free Lunch Theorem For Circuit Complexity

A guest post from Dieter van Melkebeek

This week, about 50 computer scientists gather at Schloss Dagstuhl for a seminar on "Complexity of Boolean Functions." The setup follows a long tradition that started back in 1944 at Dagstuhl's mathematical sister institution in Oberwolfach: a flexible program of talks, ample time for discussion, and Deutsche Gruendlichkeit in a wonderful setting.

I'll highlight an aspect of roughly one talk per day. Given the wide variety of topics, the selection is idiosyncratic rather than representative. For a full list of the talks, check out the seminar web page.

On Monday, Philipp Woelfel discussed time-space tradeoffs for integer multiplication. Every program computing the product of two n-bit integers in time T and space S has to satisfy TS = Ω(n²), and this lower bound is tight. One may expect that the same time-space tradeoff holds if we're only interested in the i-th bit of the product, where i is part of the input. However, Philipp showed a randomized program (with polynomially small error) that does the job using only O(n log n) time and O(log n) space, for a product TS of O(n log² n). It remains open whether the TS = Ω(n²) lower bound for the simpler problem holds in the deterministic setting.

I stole the title for this weblog entry from Peter Bro Miltersen. Right before lunch on Monday, he presented his "free lunch theorem": Lower bounds for circuits that consist of a gate C applied to symmetric functions of ANDs (type I) imply lower bounds for circuits that consist of a gate C applied to symmetric functions of AC⁰ functions (type II). The proof outline goes as follows. Consider a circuit of type II. By the switching lemma, hitting it with a random restriction transforms each of the AC⁰ functions into small decision trees, each of which can be written as a small OR of small ANDs. For any given decision tree, at most one of its ANDs can be true. It follows that a symmetric function of decision trees is a symmetric function of all the ANDs involved in these decision trees. This transformation gives us a circuit of type I that isn't much larger than the original circuit.

Part of Tuesday was devoted to quantum computing. Andy Yao presented an approach to unify and generalize the known quantum lower bounds for (i) locating an item in a sorted list of n elements and (ii) sorting a list of n elements. Both in the classical and in the quantum setting, we know that (i) takes Ω(log n) comparisons and (ii) takes Ω(n log n) comparisons. Problems (i) and (ii) are instantiations of the following more general problem, which is parameterized by a partial order P on n elements: Using comparisions only, determine an unknown linear order of n elements that is guaranteed to be consistent with P. We obtain problem (i) by setting P to be a linear order on all but one element, and (ii) by making P empty. If we denote by e(P) the number of linear extensions of P, we have that e(P) = n in case (i) and e(P) = n! in case (ii). Since there are e(P) different outcomes and each classical comparison gives us at most one bit of information, we need at least log e(P) such comparisons. Thus, one obtains the classical lower bounds for (i) and (ii) in a uniform way. The simple information theoretic argument breaks down in the quantum setting. Nevertheless, using the notion of graph entropy, Andy proved a lower bound of Ω(e(P)) - O(n) for the number of comparisons in the quantum setting. He conjectured that the O(n) term can be dropped, which would yield a uniform proof of the quantum lower bounds for (i) and (ii).

On Wednesday morning, Omer Reingold talked about recent progress towards a simpler or more combinatorial proof of the PCP Theorem. In particular, he presented a more modular way of composing proof systems, a crucial step in the known proofs of the PCP Theorem. Wednesday afternoon was kept free for a hike in the woods - one of the nice traditions at Dagstuhl.

Changes in Introductory Theory

Comments to my last post basically ask how has the introductory courses in theory has changed over the years. My first reaction: remarkably little. Theoretical models of computation do not depend on the current hot technology, particularly at the undergraduate level. Many of the basic results we teach today were also taught say 25 years ago. But without doubt theory courses have changed their emphasis on various topics over the years.

Every professor teaches a theory course differently so there is no fixed answer to what has changed. But here are some trends that I have seen (from a distinctly American point of view):

• Less emphasis on automata theory, particularly for context-free languages. Many schools do away with automata theory all together.
• Less depth in computability theory. Most courses will cover undecidability but you'll less often see the recursion theory or even Rice's theorem taught.
• Does anybody still teach the Gap, Union and Speed-Up Theorems and Blum complexity measures anymore?
• Only one new theorem since the mid-70's has become a fundamental part of an undergraduate complexity course: The 1988 Immerman-Szelepcsényi Theorem stating that nondeterministic space is closed under complement.
• There has been a trend in adding some recent research in complexity as the end of a course based on the interests of the instructor: Randomized computation (though recent algorithms for primality might change how it gets taught), cryptography, interactive proofs, PCPs and approximation, quantum computing for example. Parallel computation has come and gone.

But remember these are exceptions. Basic topics like Turing machines, undecidability, NP-completeness, Savitch's theorem and time and space hierarchies still get taught much the way they were taught in the 70's.

Opening Day

Today starts the spring quarter at the University of Chicago and I start teaching undergraduate complexity. Many of the most beautiful concepts in theory get taught in the course: The Church-Turing thesis, universal Turing machines and undecidability, the P versus NP problem and much more.

Today's students have an understanding of computers that come from exposure at an early age that I cannot imagine. Still you cannot truly view computer science as a science until you learn its mathematical foundations. This course gives that foundation and uses it to pose (and sometimes answer) many basic questions: What is a computer? What can we compute? What can we compute quickly?

As computers become more and more part of our daily lives, these basic questions take on greater importance and I'm excited, as always, to tackle them with a new group of students.

Teaching High School Physics

In a comment on my last post, Suresh Venkat said "On the other hand, we teach school-age children Newtonian physics without laying out a careful argument why the thesis must hold."

This caught me as strange so I asked one of our Indian graduate students how he learned physics in school. He said they were given the appropriate theory and formulas. I asked if they did experiments. He said they were given descriptions of experiments on exams and had to predict the outcome but they never actually performed any experiments.

This is in sharp contrast to my high school physics class in New Jersey. We did many experiments in small groups as well as some class demonstrations to show that the predictions of the theory roughly corresponded to reality. My favorite demonstration simulated the following thought experiment: If a person aims a gun directly at a monkey in a tree and the monkey, scared of the sight of the gun, falls out of the tree at exactly the time the gun was shot, the bullet will hit the monkey since gravity affects the horizontally moving bullet and the vertically moving monkey exactly the same.

My physics teacher attached a stuffed monkey to the ceiling via an electromagnet. He had a device that fired a metal ball at the monkey that was rigged so the magnet would cut out and the monkey would fall at the same time as the ball was fired. True to the theory, the ball hit the monkey in mid-air. Of course there was that hole in the blackboard from the one year the monkey didn't fall.

Which teaching method is superior? In India they can go into more depth in the theory since they don't spend time on experiments. However I don't think you truly get an understanding for a scientific principle without getting your hands dirty.

Update: Venkat responds on his weblog. Perhaps I shouldn't have generalized Indian education from one data point.

Evolution

Should public schools in the US teach creationism in addition to or in place of evolution? As a scientist I have to say "no," though I'm preaching to the choir in this weblog.

Often in the news we hear of states and school districts that try to pass laws to teach creationism in schools? We should fight these attempts but we need to do so in a careful manner. Scientists should not impose the truth on school-age children, that will make us no better than the creationists who wish to impose their version of the truth. Instead we need to explain the reasoning behind evolution, the same holds for any scientific principle we teach. For example, I can't expect students to trust me when it comes to the Church-Turing thesis but instead I need to lay out a careful argument why the thesis must hold.

One should not force students to accept evolution, rather lay out the arguments and let the students learn to believe evolution on their own. Only then will they become true believers.

Is Satisfiability Checkable?

Time for another of my favorite open questions: Is Boolean Formula Satisfiability (SAT) checkable?

The best notion of program checking comes from a paper by Manuel Blum and Sampath Kannan. Let P be a program claiming to compute a language L. A program checker M for L is a probabilistic polynomial-time Turing machine with access to P as an oracle that outputs either "P(x)=L(X)" or "P incorrectly computes x on some input."

We say L is checkable if for all oracle P and inputs x,

1. If P(x)≠L(x) then with high probability M^P(x) outputs "P incorrectly computes x on some input", and
2. If P=L then with high probability M^P(x) outputs "P(x)=L(x)".

If P is correct on x and incorrect somewhere else, M^P(x) can output either answer.

Blum and Kannan show a nice connection to interactive proofs. We say a language L has a function-restricted interactive proof (FRIP) if there is a PCP for L where the proof for x in L is computable with an oracle for L. We have the following equivalence for all languages L

1. L is checkable.
2. Both L and L have FRIPs.

Checkable languages include Graph Isomorphism, the Permanent and all of the PSPACE-complete and EXP-complete sets.

Back to whether SAT is checkable. SAT has a FRIP by using self-reduction. So whether SAT is checkable is equivalent to whether SAT has a FRIP.

All of the known PCPs for SAT seem to require counting, a prover hard for #P or at least Mod_kP for some k. Whether one can find a PCP for SAT that is even in the polynomial-time hierarchy remains open.

Perhaps one can show some consequence of the checkability of SAT perhaps that the polynomial-time hierarchy collapses. Bogdanov and Trevisan have the best result in this direction; they show that if SAT has a non-adaptive self-corrector then PH collapses to third level. Though many checking results use self-correction there still could be some completely different way to show SAT is checkable.

AT&T Research

The Newark Star-Ledger has an article about the downfall of AT&T research. Quantum Algorithms has some follow-up quotes by Bjarne Stoustrup.

No doubt that these industrial research labs can produce great ideas and results especially at the scale of AT&T or Bell Labs before the split. But the business model doesn't work; AT&T failed to capitalize on most of the innovations of its labs nor has any corporate labs with an open and unfettered research staff produced valuable intellectual property for that company. If a corporation tries to limit an open and unfettered environment, the best scientists will often leave for other labs or academia.

Bell Labs/AT&T had a lengthy history helped along by a telephone monopoly. But until someone finds the right business model, we will never see a truly self-sustaining industrial basic research lab.

Computer Science Unplugged

Can you teach basic computer science concepts to children? Without a computer?

Computer Science Unplugged by Tim Bell, Ian Witten and Mike Fellows has a wonderful collection of games and activities designed to teach young people about basic CS ideas like binary numbers, searching algorithms, text compression, information theory and much more. Some of the activities are available online. My favorite: Sorting Networks that kids can run through and find themselves ordered.

An Unnatural Post

When we see "natural" in a computer science papers it usually reflects an informal idea of realism, i.e., Clique is a natural NP-complete problem while 1-in-3 SAT is not. Sometimes though researchers use "natural" in a defined term. Generally this should be avoided--no definition can prevent artificial examples but more importantly perfectly reasonable notions that do not fit the rule are, by definition, not natural.

I work with bits and usually take my logarithms base 2, an unnatural logarithm. I use diagonalization to prove lower bounds on Turing machines, an unnatural proof technique applied to an unnatural computing model. I have even been known to use unnatural numbers, like 1/2.

What do you expect since I study an unnatural science?

Favorite Theorems: Derandomization

As I had mentioned earlier, this year I plan to write My Favorite Ten Complexity Theorems of the Past Decade II. I decided to reveal the choices one per month through the end of 2004.

For March I will go with derandomization, an area where we have seen amazing progress in recent years. My favorite derandomization result in the past decade is

P=BPP unless E has subexponential circuits: Derandomizing the XOR Lemma
by Russell Impagliazzo and Avi Wigderson, STOC 1997

The title both describes the main result and the technique use to prove it. Informally this result says that under a believable hardness assumption one can get full derandomization. Formally, if there exists a language L computable in DTIME(2^O(n)) such that there exists an ε>0 such that for all n, there are no circuits of size 2^εn that compute L on inputs on length n then pseudorandom generators exist and P=BPP.

This paper marks the culmination of a series of papers to derandomize BPP. We have also seen many papers since giving connections between derandomization and other recent areas in complexity like extractors and error-correcting codes as well as other applications for derandomization. I can't mention all of these results in this post but I recommend the survey of Valentine Kabanets and the book chapter of Peter Bro Miltersen for a broader background on derandomization.

March Madness

America's Favorite Binary Tree, the 2004 College Basketball Brackets have been released. This week last year had several posts related to the brackets intermingled with ICALP and a war.

Publishing Papers from Iran

A Chicago Tribune editorial describes an incredibly bad restriction on publishing from Iran. The U.S. Treasury Department's Office of Foreign Assets Control (OFAC) is warning publishers that they may face serious legal repercussions for editing books, papers or manuscripts from Iran or any other country that is under economic sanctions, on the grounds that such editing amounts to trading with the enemy.

Academics have always led the way in establishing relationships between politically antagonistic countries. Scientists often have the same research goals even if their politics or the politics of their countries differ. Preventing publication of their work (or in this case editing of their work) will unnecessarily restrict the communication between scientists and make opening these doors between countries harder.

More from the IEEE Spectrum.

Outsourcing and the Future of Computer Science

How will the trend in outsourcing programming work affect computer science departments in America? In the short term not good. A lesser need for programmers and continued slow growth in the technology sector will keep undergraduate enrollments down and CS departments will have less expansion. We are still a decade or two away from large retirements of the first wave of computer scientists so for the most part new faculty get hired mostly on CS department expansion.

In the long term outsourcing will lead to much stronger computer science departments. Programming skills alone will not necessarily lead to success and technology professionals will need a deeper and broader view of the tools and ideas in computer science. CS departments will have to provide courses that cover these concepts requiring a faculty that covers many areas and knows them well. Departments will have to expand to meet these growing needs with active researchers in a broad range of expertise. As a result we will see many more universities with a strong and vibrant research-oriented CS department.

Seeing the Same People in Different Places

This week I'm visiting the University of Calgary and although I have never been here before it seems like a homecoming. They have a strong quantum computing group with several people out of my past.

• Richard Cleve - I first got interested in quantum computing when Cleve had a short visit to CWI in Amsterdam during my sabbatical there in 1997. But our true bond comes from being stranded together in Tokyo after 9/11.
• John Watrous - The reason I drink my coffee black.
• Peter Høyer - Cleve and I were the foreign committee members at Høyer's Ph.D. defense in Denmark.
• Hartmut Klauck - Klauck had a postdoc at IAS while I was at NEC nearby.
• Hein Röhrig - A new postdoc in Calgary fresh from his defense in Amsterdam. Röhrig also was a summer intern at NEC.

Seeing the same faces in different places. Yet another oddity of the academic life.

SIGACT News

The first issue of 2004 of SIGACT News is out. The complexity column has part 2 of last issues' article on constraint satisfaction problems. More exciting is the list of upcoming columns: Ambainis on quantum, Guruswami on codes and Hitchcock, Lutz and Mayordomo on dimension.

Some interesting pieces in the back of the issue including information on the recent move of the editorial board of Elsevier's Journal of Algorithms to the new ACM Transactions on Algorithms and David Johnson announcing the revival of his NP-completeness column.

Right before that is a cute paper on the complexity of the peg hopping game found at Cracker Barrel (restaurant chain that serves fine American comfort food).

Remember that you can join SIGACT, support theory and get SIGACT news even if you don't belong to ACM for only $18, $9 for students.

On a different topic, the number of comments on my posts have gone up dramatically. I'm not sure why but I appreciate your feedback. I read every comment though usually restrain from responding unless specifically asked a question. I've had my say and you have your say and let's leave it at that. Often I learn something new from your comments like the Stern-Brocot tree. Keep those comments coming.

Persi Diaconis

Persi Diaconis once again shatters our belief in generating randomness; this time showing, with Susan Holmes and Richard Montgomery, that flipping coins does not usually produce uniformly random bits.

Diaconis has an impressive resume of magic, mathematics and psychic debunking. Around 1990 he visited Chicago and taught a course on Markov chain analysis spending the first half of the course on the following problem: Given n cards, pick two at random and swap them. Repeat. How many swaps do you need to get a nearly randomly shuffled deck? Answer: About n log n. The upper bound used representation theory and took several weeks to prove.

During that year, a Chicago Tribune editorial mentioned another Diaconis result showing that one needs seven standard shuffles to get a deck of cards close to random. I found the beginning of the editorial online:

And you always thought mathematicians were serious people. Especially those at Ivy League universities like Harvard and Columbia. Well ...

Dr. Persi Diaconis and Dr. Dave Bayer have just come out with a study that may give you pause. They have found, after no end of riffling and counting, that it takes exactly seven ordinary, careless shuffles to give a totally random mix to ...

Getting back to coin flipping, you can always use the von Neumann coin-flipping trick to correct for the unknown bias.

Counting the Rationals Quickly

In the November 1989 issue of American Mathematical Monthly Yoram Sagher presented a note "Counting the Rationals" giving a simple 1-1 mapping from the positive rationals onto the positive integers. Let m/n be a rational with gcd(m,n)=1. Let q₁, ..., q_k be the prime factors of n. Sagher defined his 1-1 mapping as f(m/n) = m²n²/ (q₁q₂··· q_k) With this mapping, Sagher notes you can easily determine the 10¹⁵th positive rational as 10^-8.

Unfortunately inverting Sagher's function appears to require factoring. Can one find a 1-1 mapping from the positive integers onto the positive rationals that is easy to compute in both directions? Think about it or keep reading for my solution.

Let p(i,j) = i + j(j-1)/2. The function p is an easily computable and invertible bijection from pairs (i,j) with 1≤i≤j to the positive integers. We define our 1-1 mapping from the positive integers to the positive rationals by the following algorithm.

1. Input: n
2. Find i and j such that n = p(i,j).
3. Let g = gcd(i,j) (easily computable via Euclid's algorithm)
4. Let u = i/g and v=j/g.
5. Output: g-1+u/v

Since 1≤i≤j we have 1≤u≤v making the output unique and the function easily invertible.