Do Wikis Work?

John Stockton put a wiki version of the Complexity Zoo on the Quantum physics Qwiki. For those not up on the nomenclature, a wiki is a specially designed web page that anyone can change usually with mechanisms for tracking and undoing those changes if necessary. Ideally a wiki will allow the zoo to remain up-to-date without continual intervention from Scott. But will it work?

The Wikipedia has a number of entries for various complexity classes. I generally find them for the most part accurate but not complete. Take for example the NL entry which doesn't note that NL is closed under complement but instead has the misleading result that RL=NL (where one allows the randomized machine to have infinite computation paths). Sure I could fix the entry in wikipedia but there are at least two problems:

• There aren't enough people in the field who have the time and patience to go through all the entries and update them.
• I firmly believe RL should be what Wikipedia calls RLP. But what right do I have to impose my naming conventions on the whole wikipedia universe.

Sanjeev Arora and Boaz Barak set up Theory Matters as one big wiki. Boaz once said the following in a weblog comment.

Don't give "theorymatters.org" as an example to a place that ignores area X. It's a Wiki - if you don't add the material yourself no one will do it for you.

But people are reluctant, for whatever the reason, to edit the wiki. Outside of the "Survey Collection" you can nearly count the number of contributors to the wiki on one hand.

In short wikis, like anything else on the web, can be a good source of information but are often incomplete sometimes in important ways. Just because anyone can edit a wiki doesn't mean that they do.

P/poly

A student asked me why P/poly was an interesting class? A very interesting class with a funny name. It combines time and program-size complexity, and characterizes non-uniform efficient time and languages with small circuit complexity.

Here are two equivalent definitions of P/poly.

• A language L is in P/poly if there is a language A in P and a set of advice strings {a₀,a₁,…} such that |a_n|≤n^O(1) and x is in L if and only if (x,a_|x|) is in A.
• There is a family of circuits {C₀,C₁,…} such that |C_n|≤n^O(1) and for all n and all x=x₁…x_n, x is in L if and only if C_n(x₁,…,x_n) accepts.

The equivalence comes from Ladner's proof that the circuit value problem is P-complete. Some argue that P/poly is a better notion of efficient computation than P since we allow the program size as well as the time to grow as the input grows. Techniques from Adleman show that BPP is contained in P/poly. However P/poly contains noncomputable and in fact an uncountable number of languages

Here are just a few areas where P/poly plays a crucial role.

• Combinatorial Approach to P versus NP: Karp and Lipton show that if NP is in P/poly then the polynomial-time hierarchy collapses. So one approach popular in the 80's to show P≠NP tried to show an NP problem did not have polynomial-size circuits. Razborov shows the clique problem did not have polynomial-size monotone circuits.
• Derandomization: Nisan and Wigderson show that hardness against nonuniform classes can give us pseudorandom-number generators. Building on their work, Babai, Fortnow, Nisan and Wigderson show that if EXP is not in P/poly then BPP can be simulated in subexponential time on infinitely many input lengths.
• Cryptography: Often security is defined against P/poly adversaries to capture extraneous information in the system.
• Learning Theory: Learning polynomial circuits would be the Mecca of learning theory. Can't be done in the usual models unless factoring is easy. Bshouty et. al. show we can learn circuits probabilistically with an NP-oracle and hypothesis queries.

FOCS

From Anupam Gupta

A favor: the FOCS conference registration site is open; could you put up a small post on your blogs letting people know this, along with the fact that the advance registration deadline is September 23rd?

I did send mail to theorynet and dmanet, but clearly blogs are where the action really is.... :) thanks a ton, gents!

Done but my readers shouldn't count on the weblogs to tell them when to register or submit papers. Subscribe to DMANET or Theorynet, check the Theory Calendar or, most reliably, Google the conference to find out the appropriate deadlines.

SODA Rising

As theoretical computer science grew during the past twenty years, the general theory conferences STOC and FOCS could no longer present all of the good papers in theoretical computer science and a number of smaller specialized conferences arose, for example Computational Complexity, Learning Theory (COLT), Computational Geometry (SoCG) and many others. But one of these specialized conferences, the Symposium on Discrete Algorithms (SODA) has grown larger than STOC and FOCS both in submissions and attendance. Perhaps this should not be too surprising in that algorithms is a broad area and there is only one SODA each year and two STOC/FOCS conferences.

Recently though I've seen a few circumstances where SODA gets mentioned in the same breath as STOC and FOCS as an equal. For example, the SIGACT Home Page lists the upcoming FOCS, STOC and SODA conferences. OK, SIGACT co-sponsors SODA but the bottom of the upcoming FOCS Home Page (side note: Early Registration Deadline Sept. 23) list the previous FOCS, STOC and SODA pages. FOCS is an IEEE conference with no official connection to SODA. Finally Cathy McGeoch is trying to set up a hockey game at an upcoming FOCS, STOC or SODA conference. Can you have a true TCS World Cup with just algorithms people?

Are SODA papers getting the same prestige as STOC and FOCS papers? Not yet but we are heading that way. Is it truly a good thing to move from a STOC/FOCS/specialized conferences system towards a STOC/FOCS/SODA/other specialized conferences system?

Questions About Crypto

Bill Gasarch wants your help to judge a new book.

I am reviewing Encyclopedia of Cryptography and Security for a future SIGACT NEWS book review column. I will review it by asking various people for THINGS THEY WANT TO KNOW ABOUT from such a book, then I look them up, and see how the book does. (ease of finding it, value of information, etc.)

So, I request that you EMAIL me (gasarch@cs.umd.edu) a question that you would like to see in an encyclopedia of Crypto and Security.

If you know someone who probably doesn't read this blog but has good questions (e.g., a colleague working in Systems who works on security) pass this on to them.

Hard Times for the Big Easy

I have been to New Orleans twice. First for the 1991 STOC conference which overlapped the Jazz and Heritage festival. Then again in 1994, one last fling when my wife was pregnant with our first child. We went to the French quarter for crawfish and listened to Jazz at Preservation Hall, took the trolley down St. Charles Avenue, got our baseball fix with the New Orleans Zephyrs AAA team (the major league teams were on strike) and saw the Mother's Day Parade ("Mother" being a famous New Orleans transvestite).

Now this famous city lies mostly flooded, one of the victims of Hurricane Katrina. A major city, which has hosted many Superbowls and the biggest party in America in the days before lent, lies devastated by the hurricane, not to mention the tremendous damage in other Gulf Coast communities. With the tsunami last December, nature has not been kind to us this year.

Theory Still Thrives at IBM

Ron Fagin writes in response to my post The New Research Labs.

Lance has invited us to give an update on the state of theory at the IBM Almaden Research Center, and I am happy to do so. The Theory Group at IBM Almaden has a long and distinguished history. I first formed the group in 1979. Over the years, many leading theoretical computer scientists have been members of the group, either as regular Research Staff Members or as "temporary members" (including Visiting Scientists, Postdoctoral Fellows, and Summer Interns). Former members of the theory group have held and still hold a variety of positions in premier institutions, including deanships and endowed chairs in top universities.

The primary mission of Theory Group members has always been to do first-rate research in theoretical computer science. Our primary mission remains the same today: to do world-class science. This is our raison d'etre. In addition, group members spend a portion of their time interacting with other research teams at IBM. This has led to a number of successes. Many times we have been in the happy scenario where such work has led not only to impact on IBM products, but also to exciting, leading-edge theory. This balance of activities has led to a very stable environment where Theory Group members enjoy the strong support of the organization.

Every research group, including the Theory Group, experiences turnover. In recent months, there has been more turnover than usual in the Theory Group, because of new opportunities in Silicon Valley. The Theory Group has a number of open slots to hire outstanding theoretical computer scientists, for both Research Staff Member and Postdoctoral positions. The availability of these positions is an affirmation that the Theory Group will continue its mission, and maintain its long tradition of excellence.

Back From Vacation

I am back from our family vacation to the Black Hills of South Dakota. Thanks to Ryan O'Donnell for guest blogging. I have donated $26 to hurricane relief in honor of all of the winners of Ryan's Game.

I used to keep off the internet completely over vacation but the web has become such a useful resource (for directions, hotels, site information) that we brought along my wife's laptop. All of the hotels we stayed in (as well as the highway rest areas in Iowa) have free internet so we had good access. Still I avoided checking my email and Ryan's weblog entries. I didn't want to worry about anything work related during the week. Of course that meant I came back to a mountain of email and if you had sent me some I will get back to you soon.

Some of these hotels also gave us a free USA Today which ran an article on the recent popularity of Sudoku books in the US. The article had the line "Sudoku involves no math." What did they mean? Probably Sudoku involves no arithmetic. But can you really be logical without being mathematical?

The Game -- what's left (by Ryan O'Donnell)

Looks like #5 (E), #8 (H) and #22 (V) are all that are left.

Blogger.com -- stinks (by Ryan O'Donnell)

Man, blogger.com screwed that last post up in at least 3 different ways! Or maybe it was my fault. Anyway, hopefully the rest of the pictures appear below...

PS: My PS from the last post also got cut off; it said, "PS: Thanks very much to Lance for the opportunity to guest blog; it was a lot of fun. Thanks also for all the comments from readers."

1. (Correctly identified as Dimitris Achlioptas.)

2. (Correctly identified as Joan Boyar.)

3. (Correctly identified as Artur Czumaj.)

4. 5. 6. 7. 8. 9. (Correctly identified as Pino Italiano.)

10. (Correctly identified as Mike Jordan.)

11. 12. 13. 14. 15. (Correctly identified as Tatsuaki Okamoto.)

16. (Correctly identified as Ren� Peralta.)

17. (Correctly identified as Jean-Jacques Quisqater.)

18. (Correctly identified as Eric Ruppert.)

19. (Correctly identified as Adam Smith.)

20. (Correctly identified as Adam Tauman Kalai.)

21. (Correctly identified as Alasdair Urquhart.)

22. 23. (Correctly identified as Rebecca Wright.)

24. 25. 26.

The Game (by Ryan O'Donnell)

Adam Klivans and Rocco Servedio and I used to play what we called The Game. To play The Game, you email the others a picture of a person in theoretical computer science. The others' job is to identify that person. I was reminded of The Game recently when looking at Homin Lee's look sharp, think sharp, act sharp page. No one gets any points for identifying the people on that page -- they're way too easy. (Also the pictures are links to home pages.)

For my last blog entry, I thought we could all play The Game. Lance has generously offered $26 in prizes; the first commenter to identify any given person wins a buck (you need to post non-anonymously, obviously). One rule: no poster is allowed to identify him- or herself. Hint: the number 26 has its obvious significance. Caveat: some of this was done with Google Image Search; if I got the wrong person, I apologise.

1. 2. (Person on the left. )3.4. 5. 6. (In the green sweater.)

Depth-two TC^0 (by Ryan O'Donnell)

For today's post, some hard-core, old-school, low-level structural complexity, coupled with a woe-is-me tale.

A couple of summers ago a friend and I decided to gird ourselves and take a stab at proving a circuit lower bound. To dial down the quixotism as much as possible, we picked the absolutely least ambitious circuit class we could think of to work on: depth-two TC^0.

I should clarify what I mean here: TC^0 is usually defined as being the class of poly-size constant-depth circuits with constants, negations, and unlimited fan-in majority gates. But here when I say "depth-two TC^0", I want to allow arbitrary threshold gates instead of just majority gates. By a threshold gate I mean a function, determined by integer constants a_1, ..., a_m and c, which on input (x_1, ..., x_m) outputs 1 when a_1 x_1 + a_2 x_2 + ... + a_m x_m > c, and 0 otherwise. Siu and Bruck in 1991 showed that an arbitrary threshold gate can be simulated by a poly-size depth-three majority circuit (this was improved to depth two in a very nice paper by Goldmann, H�stad and Razborov, and the construction simplified a few times, most elegantly by Hofmeister). So if you only care about constant depth and poly size, it doesn't matter what sort of threshold gates you allow for TC^0. But we were interested in depth-two arbitrary thresholds of arbitrary thresholds.

[Side note: One might try to argue that small-depth threshold circuits are interesting from a physical point of view, due to resemblance to neural nets. Since allowing arbitrary threshold gates seems a bit dubious, physically -- Circuits Of The Mind people, what do you think? -- I won't try to argue this. I'll merely say that the class of thresholds of polynomially many thresholds is a pretty natural "circuit class".]

Now when people like to exclaim over how bad we are at circuit lower bounds, the usual trope is that "As far as we know, NP might be contained in AC^0 with mod 6 gates!" (Or do they say EXP?) But you can take it one step further: correct me if I'm wrong, readers, but I think that as far as we know NP might be in depth-two TC^0. To think: solving the travelling salesperson problem, say, with a threshold of polynomially many thresholds of inputs.

Also as far as I know, there would be no amazing consequence of a lower bound against depth-two TC^0; this is one reason why friend and I tried to tackle it. The other reason was that it seems like we already practically have it:

• If you restrict the top threshold gate to be a majority, then a neat 1993 result of Hajnal, Maass, Pudl�k, Szegedy and Tur�n shows that Inner Product Mod 2 is not in the class. The proof uses the classical randomized communication complexity lower bound for IP2 by Chor and Goldreich.
• If you instead restrict the lower level thresholds to be majorities (or any gates with logarithmic deterministic communication complexity), a superb result of J�rgen Forster -- published originally in NeuroCOLT (!) 2000 -- again excludes IP2 from the class. Forster showed this by proving IP2 has linear randomized communication complexity even when the players need only succeed with any probability exceeding 50%.

So. IP2 cannot be expressed as a majority of poly many thresholds nor as a threshold of poly many majorities. You'd think it would only be a small step from there to show that it cannot be expressed as a threshold of poly many thresholds...

Long story short, after a summer of banging our heads over it, we came up with absolutely nothing to say about whether or not IP2 is in depth-two TC^0.

SAT, computable as a threshold of thresholds...? Man.

Explicit expander exaggerations (by Ryan O'Donnell)

Until pretty recently, when it came to expanders, I was a bit of a naif and -- I'll admit it -- a bit of a faker. Sure, when randomness was precious I could say, "Hey, maybe we should take a walk on an expander graph," as well as the next guy. Thing was, I was always hoping the next guy would be able to take it from there. So I finally got around to understanding them properly and I found out that one aspect of the expander story I had in my head was greatly exaggerated...

Now don't get me wrong, the Zig-Zag Product is swell, it's Annals of Math-worthy, and it's inspired a lot of recent work, both in expander constructions and elsewhere (e.g., Reingold's SL = L theorem). However, the story I sometimes heard as to why it was cool was that it was the first explicit expander construction that was actually understandable; that you didn't have to know lots of deep number theory to verify the proof; that all other previously known constructions used zaniness like Weil sums, Ramanujan conjectures, Kazhdan constants and whatnot.

But as you probably know, this is an exaggeration; it's really not so. The first explicit expander construction was given by Margulis in 1973 and its expansion was explicitly determined by Gabber and Galil, 26 FOCSes ago. Although the first proofs used some deep stuff, by STOC '85 Jimbo and Maruoka had made the proof completely elementary. Here's a simple version of the construction: Take the graph on Z_m x Z_m and connect (x,y) to (x+2y,y), (x+2y+1,y), (x,x+2y), (x,x+2y+1). Also put in the reverse edges. The degree is 8 and the second largest eigenvalue is at most 5 sqrt(2) = 7.07 < 8. You're done.

The proof? Three pages of elementary fiddling around. Zig-Zag's proof? A bit of a tricky definition followed by three pages of elementary fiddling around. (If you prefer a more leisurely treatment, both proofs take about five pages in David Xiao's senior thesis.) Zig-Zag is maybe easier to follow if you like linear algebra, Gabber-Galil if you're down with a little of Fourier analysis. The Zig-Zag construction wins out in terms of intuition -- the GG proof has a very clever trick in it that would be hard to come up with on your own. On the other hand, it's not like one should find it baffling that the Gabber-Galil construction might work -- indeed, Jin-Yi Cai shows that pretty much any similar construction on Z_m x Z_m is an expander.

Finally, the Gabber-Galil construction is hands-down better when it comes to explicitness of construction. (It takes a bit of work and thought to show that Zig-Zagging gives you good explicitness.) And GG's extreme explicitness can certainly come in handy -- just ask our old friend Lance Fortnow and former guest blogger Adam Klivans who used it (via a result of Gutfreund and Viola) to show that RL is contained in L with linear advice.

Additive combinatorics (by Ryan O'Donnell)

For a while now I've taken a dilettantish interest in the subject of Additive Combinatorics. If A is a subset of the integers {1, ..., N}, let A + A denote the set {a + b : a, b in A}. Additive Combinatorics studies such questions as, "If A + A is small compared to |A|^2, what can be said about A?" and "What is the size of the largest A that contains no nontrivial length-3 arithmetic progression?"

My interest in this topic was piqued a little over a year ago by the confluence of three events. First, the Green-Tao theorem was announced: The primes contain arbitrarily long arithmetic progressions. Second, the Barak-Impagliazzo-Wigderson paper on extracting randomness from independent sources came out, which crucially used a 2003 result from additive combinatorics by Bourgain, Katz, and Tao. Third, I was reading some of the course notes and expositional papers on Ben Green's webpage (mainly because he's a masterfully clear writer) and I realized that many of the favourite techniques used in additive combinatorics are also favourite techniques in theoretical computer science -- the probabilistic method, graph theory, discrete Fourier analysis, finite fields and low-degree polynomials therein...

So what are the applications to theoretical computer science? There are already at least a few:

• More recent work on multisource extractors; e.g., the paper of Dvir and Shpilka or the recent work of Jean Bourgain (mentioned here).
• Szemer�di's Regularity Lemma, used nonstop in the area of property testing, was developed originally for "Szemer�di's Theorem" from additive combinatorics. Ben Green also has a version of the regularity lemma for boolean functions, which I used in a paper on hardness of approximation for "Grothendieck problems".
• Tao and Vu's recent papers on the probability that a random boolean matrix has determinant zero.
• Chandra, Furst, and Lipton, inventors of the "number on the forehead" model in communication complexity, gave surprisingly efficient communication upper bounds based on arithmetic progressions in sets.
• The most-cited work in TCS history (maybe): Coppersmith and Winograd's n^{2.376} matrix multiplication algorithm. The title: Matrix multiplication via arithmetic progressions.

I like to think that many more applications and connections to TCS are on the way. Here are a few scattershot ideas... anyone want to chime in with others?

• Property Testing: Since Szemer�di's Regularity Lemma is so useful for property testing, there ought to be some use in the recently discovered hypergraph versions.
• Low-degree testing: given n-variate functions f over small fields, both communities like to look at quantities like E[f(a)f(b)f(c)f(a+b)f(a+c)f(b+c)f(a+b+c)] -- see this paper on low-degree testing by Alon, Kaufman, Krivelevich, Litsyn, and Ron but also the many works on the "Gowers norm" such as this one by Green and Tao.
• Pl�nnecke's Theorem: The proof of this theorem, which is used constantly in additive combinatorics, is pure graph theory -- the main tool is the max-flow/min-cut theorem. It'd be great to see it written in TCS language.
• Lattices: The topic is screaming out for a connection to lattice problems; see Chapter 3 of this book for some background.

For an introduction to additive combinatorics, one might look here.

More on parallel repetition (by Ryan O'Donnell)

Ryan O'Donnell here, guest blogging for Lance while he's on vacation. As a matter of fact I'm on vacation myself, in the sunny but recently tornadoed Toronto.

The parallel repetition problem has come up in this blog more than once before (perhaps because the topic of interactive proofs is near and dear to Lance's heart). I've been thinking about it lately because Venkat Guruswami and I will be teaching a course on PCPs and hardness of approximation this term.

The dirty little secret about PCP courses is that everyone always skips the proof of Ran's Parallel Repetition Theorem, even though it's an essential component of very many optimal hardness of approximation results. I used to think Dinur's new proof of the basic PCP theorem promised an opportunity to get all the way from soup to nuts in one course on PCPs and hardness of approximation. However it really only promises the following: instead of sweating for 10 lectures to get through the basic PCP theorem and then waving your hands over parallel repetition, you get to proceed happily for 3 lectures through the basic PCP theorem and then sweat over how to deal with parallel repetition.

So how to describe getting from a basic PCP with soundness, say, .9, to a PCP with soundness .0001? Here are three possible strategies I've considered:

1. Take a stab at explaining Ran's paper. This is no mean feat -- I've tried reading it maybe six times lifetime, and only on my last attempt did I make any sort of headway. That included completely disregarding the 20 pages of calculations at the end. Still, I've absorbed enough intuition from Avi Wigderson and Uri Feige (check out the latter's survey, the only explanatory writing on the theorem I've ever found) that maybe I could say something in a couple of lectures that would vaguely make sense.

2. Attempt a proof or sketch of Feige and Kilian's parallel repetition theorem. This underappreciated result is definitely easier to follow than Ran's, but it would still probably be challenging to cover in a small number of lectures. It has weaker parameters than Raz's result -- to get soundness down to epsilon you need poly(1/epsilon) parallel repetitions, rather than log(1/epsilon). But come on: if the new proof size is going to be n^{2^2^10000} anyway, does it really matter?

3. Teach the Lov�sz-Feige method of parallel repetition from STOC '92. Unless I'm mistaken, this is a neat and simple way to do a kind of parallel repetition, using multilinear extensions and a sumcheck-protocol-style analysis. The only downside: the proof gets blown up to quasipolynomial size (although, as a compensatory bonus, you get quasipolynomially small soundness). But again, does it really matter? The hypotheses NP not in P and NP not in TIME(n^{polylog(n)}) are pretty much equally good to me.

I'll probably go with either #1 or #3. Any opinions?

Conference Crashers

In a popular summer movie Wedding Crashers, two friends go to weddings and receptions uninvited for food, drink, entertainment and to pick up single women. We have a similar problem with conferences, people who come, not really for the above reasons, but to see talks, visit with their friends and avoid paying the registration fee.

While small conferences don't have the manpower to check for registered participants, the vast majority of participants do register. But as conference costs go up (for reasons like extra proceedings sales going down dramatically) and grants getting smaller and harder to get, there has been a mild increase in people skipping out on registration. If this trend continues, the problem feeds back onto itself, as those who do pay feel foolish, and we have a serious concern on our hands.

If you don't get a copy of the proceedings or eat at the conference meals you might think that you are not costing the conference anything by attending and so don't feel guilty by not paying. But conferences have some fixed expenses and most of the other expenses are cheaper per participant if there are more participants so you are costing your fellow researchers real dollars by not paying your fair share.

Sometime the registration fee can make the different in a decision on whether to attend a conference. If so talk to the conference organizers; if you explain the situation sometimes arrangements can be made. Better to attend at a reduced rate than not attend at all.

On a side note, I'm off the web next week. Microsoft postdoc Ryan O'Donnell will guest blog. Enjoy.

Research Annealing

Simulated Annealing is a heuristic technique for optimization problems. Think of an optimization problem as hills and valleys where you want to find the lowest point. First the ball starts "hot" and bounces around randomly. As you start to cool the ball down, it doesn't bounce as much as gravity will cause it to go down more often than up. When it cools completely it falls into a local minima. Hopefully you've reduced the temperature at such a rate that the local minima the ball finds is close to the true minimum. Simulated annealing doesn't solve NP-complete problems quickly in general, but it some cases it does reasonably well in practice.

I used an analogy of simulated annealing to describe to a student how one chooses a research area. First you bounce around for a while looking at many topics through talks, classes and reading some broad papers finding the right fit for your strengths and interests. Then you start to focus, reading more specific papers until you find the right place to start drilling for results.

One you start drilling you will hopefully find some oil but eventually the well will just output sludge. At this point you should start bouncing around again, slowly at first, to find a new topic. The trick is to know when to start bouncing again. Leave too early and you might miss a new oil supply right under the old one. Leave too late and you will find yourself knee-deep in sludge, forgotten and unable to escape.

US Visa Limit Reached

The US has reached its limit for H1-B visas not just for this fiscal year but for the next. A foreign technical worker wanting to work in the US wouldn't be able to start until October 1, 2006.

First some background. Here is the official description of the H-1B.

Established by the Immigration Act of 1990 (IMMACT), the H-1B nonimmigrant visa category allows U.S. employers to augment the existing labor force with highly skilled temporary workers. H-1B workers are admitted to the United States for an initial period of three years, which may be extended for an additional three years. The H-1B visa program is utilized by some U.S. businesses and other organizations to employ foreign workers in specialty occupations that require theoretical or technical expertise in a specialized field. Typical H-1B occupations include architects, engineers, computer programmers, accountants, doctors and college professors. The current annual cap on the H-1B category is 65,000.

Of those 65,000, 6,800 are set aside for free trade agreements with Chile and Singapore, effectively leaving 58,200 visas. During the dot.com boom the number of H1-B visas available was raised to 195,000 but lowered again in a misguided attempt to save American jobs. Congress did allow an additional 20,000 visas for foreigners who have received advanced degrees in the US and there are still a few of those visas available.

These low visa limits will just cause large corporations to continue to develop and grow their overseas R&D labs. Instead of having these workers in the US helping our economy and advancing science and technology in the US, these limits will add to the erosion of the US dominance in these areas.

Do a Google News search on this topic and you get mostly foreign articles on the topic. While the visa limit does not directly affect US citizens, we should all be concerned about its effect on our country's ability to lead in S&T.

Extreme Oracles

Let's look at some relativized worlds which really push the limits of what we don't know how to prove. Once again I refer you to the zoo for definitions of these classes.

• P=PSPACE (Baker-Gill-Solovay)

  One of the original oracles collapses everything. P=NP=co-NP=PH=⊕P=PP=BQP=P^#P=PSPACE=NPSPACE.

• Generic Oracles (Blum-Impagliazzo or see our toolkit paper)

  These oracles separate as much as possible. P≠NP, the polynomial-time hierarchy is infinite, PP is not in P^NP, NP is not in ⊕P and much more. Oddly enough they diagonalize against machines that need to fulfill a promise condition and so with the appropriate construction one also gets P=NP∩co-NP=UP=BPP=BQP.

• P=⊕P and NP=EXP (Beigel-Buhrman-Fortnow)

  Relative to this oracle ZPP=⊕EXP and the isomorphism conjecture holds (all NP-complete problems are reducible to each other via invertible bijections).

• P=NP and ⊕P=EXP (Beigel-Maciel)

  The polynomial-time hierarchy collapses to P and yet the exponential hierarchy sits inside ⊕P.

• P=⊕P and BPP=EXP^NP (Buhrman-Torenvliet [Corollary 4.8])

  No even very weak derandomization for BPP. Valiant-Vazirani puts NP in RP^⊕P but in this oracle NP is not even in co-NP^⊕P.

• P^RP=NEXP (Buhrman-Fenner-Fortnow-Torenvliet)

  No even very weak derandomization for RP. Implies P^NP=P^NEXP (also implied by the next oracle).

• P^NP=⊕P=PEXP (Aaronson)

  A strong version of Beigel's oracle where P^NP is not in PP (though the entire polynomial-time is in P^PP) and PP is not closed under Turing-reductions.

You can replace ⊕P with Mod_kP for any prime k in any of the above. We don't believe any of the statements to be true in the "real world" but all of them remain open and would require nonrelativizing techniques to disprove.

Information and Computation

Elsevier is opening up I&C for the rest of the year.

The Publisher and Editorial Board of Information and Computation are pleased to announce that for one year, effective immediately, online access to all journal issues back to 1995 will be available without charge. This includes unrestricted downloading of articles in pdf format. Journal articles may be obtained through the journal's web site or Elsevier's ScienceDirect.

At the end of the year, the retrieval traffic during the open access period will be evaluated as future subscription policies are considered.

Albert R. Meyer, Editor-in-Chief, MIT Computer Science & AI Lab
Chris Leonard, Publishing Editor, Elsevier
Moshe Vardi, Associate Editor, Rice University

I should note I am a member of the I&C editorial board.

A good place to start reading is the top 25 downloaded articles.

Sudoku Revisited

Robin Houston writes

Although I'm not a complexity theorist, I very much enjoy reading your weblog. I also enjoy solving the Sudoku puzzles published in the British press, so it was doubly nice to see your May 25 post about the complexity of Sudoku!

As far as I can tell, it follows from Yato's work that the problem:

1. Given a partially completed grid, find a valid completion if there is one; otherwise report that there isn't one.

   is solvable in polynomial time iff P=NP.

   That's interesting of course, and it's a problem that faces those who set the puzzles; but the problem that we solvers are faced with is not quite (1). It's:

2. Given a partially completed grid that has a unique valid completion, find that completion.

Can anything be said about problem (2)? If there were a polynomial- time algorithm for (2), would it follow that P=NP? If not, would there be any other significant consequences for complexity theory?

Good question. Since Yato's reductions preserve solutions the problem is equivalent to finding a satisfying assignment of a Boolean formula that has exactly one satisfying assignment (Unique SAT).

We don't know if Unique SAT is NP-complete in the traditional sense. However Valiant and Vazirani have a nice paper that shows how to randomly reduce SAT to Unique SAT. Putting it together we get the following equivalence:

• Given a partially completed grid that has a unique valid completion, probabilistically find that completion in polynomial time.
• NP=RP (i.e. all NP problems have efficient probabilistic solutions).

Since we don't believe that NP has fast probabilistic algorithms, we expect that there are no efficient procedures to completing a generalized Sudoku grid, even if there is only one such completion.

Is the Thrill Gone?

Sanjeev Arora and Bernard Chazelle write the Viewpoint Column Is the Thrill Gone? in this months Communications of the ACM.

One wonders if the failure of computer scientists to articulate the intellectual excitement of their field is not one of the causes of their current funding crisis in the US. Too often policymakers, and hence funding agencies, treat computer science as a provider of services and infrastructure rather than an exciting discipline worth studying on its own. Our promises of future technological innovations and scientific advances will be more credible to them if they actually understand that past and current breakthroughs arose from an underlying science rather than a one-time investment in "infrastructure."

We think it is high time that the computer science community should reveal to the public our best kept secret: our work is exciting science—and indispensable to the nation.

You would think that Arora and Chazelle are preaching to the choir by publishing in the communications of the main computer science academic society. But the ACM also tries to represent the broader computer professional and the CACM reflects these mixed priorities. Each month CACM takes some current topic (Spyware this month) and has a collection of academic papers on that topic that look of little direct interest to practitioners. (Compare this approach with Technology Review that hires science writers to explain the work of academic and industrial researchers.)

So we need people like Arora and Chazelle to remind the ACM about the science in computer science. We need a separate Computing Research Association to push the computer science research agenda. And most importantly, as Arora and Chazelle say, we need to make broader public aware of the excitement and importance of computer science.

Favorite Theorems: Abstract Complexity

July Edition

As a graduate student, Manuel Blum wanted to study computational complexity freed from any specific machine model. His paper set the tone for much of complexity of the late 60's.

Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, JACM 1967.

Blum defined a resource measure as any partially computable function Φ_M (think time) of a machine M that fulfilled some simple axioms.

1. For all x, M(x) halts iff Φ_M(x) halts.
2. The language {<M,x,m> | Φ_M(x)=m} is computable.

Blum argues that time complexity on any reasonable model of Turing machine would fulfill these axioms. He also noticed that space complexity also fulfills the axioms. Though the axioms are very general, Blum shows their power with the speed-up theorem.

Speed-Up Theorem: For every computable function r, there is a language L such that if M accepts L there is an N accepting L with r(x,Φ_N(x))≤Φ_M(x) for almost all x.

For example there is some language L such that if any algorithm computes L in t(n) steps there is another algorithm computing L in log t(n) steps. This might seem to violate the time hierarchy but t(n) does not have the time constructibility needed for the hierarchy. Blum also showed there was a language that couldn't be sped up much and a computably-bounded relationship between any two abstract resource measures.

Borodin and Trakhtenbrot independently proved the gap theorem for abstract complexity measures.

Gap Theorem: Given any computable function g(x)≥x there is a recursive function t(x) such that if Φ_M(x)≤g(t(x)) for all x then there is an N accepting the same language as M with Φ_N(x)≤t(x) for almost all x.

In particular there is a function t(n) such that DTIME(t(n))=DTIME(2^t(n)) and thus DTIME(t(n))=DSPACE(t(n)).

McCreight and Meyer proved the union theorem.

Union Theorem: Let t₁, t₂, … be a computable enumeration of increasing resource bounds. There is a computable function t such that the following are equivalent for all M.

• For some i and almost all x, Φ_M(x)≤t_i(x).
• For almost all x, &Phi_M(x)≤t(x).

For example there are computable functions t₁ and t₂ such that DTIME(t₁(n)) is equal to P and DTIME(t₂(n)) is exactly the primitive recursive languages.

McCreight and Meyer also give an honesty theorem showing that computable t there is (in a weak sense) a time-constructible t' such that languages computable with resource bound t are equal to languages computable with resource bound t'.

After the P versus NP problem was popularized by Cook and Karp in 1971, the focus of complexity went to polynomial-time (which also was machine independent) and away from abstract complexity.

The New Research Labs

I am just finishing the last of three west coast trips this summer. I went to the Complexity conference, two universities (U. Wash and Caltech), three ballparks, a Bat Mitzvah and a film shoot. I also visited the Holy Trinity of internet companies: Microsoft Research (both in Silicon Valley and Redmond), Yahoo! Research (Pasadena) and a Google (Mountain View), the last of which seemed more like a summer camp than a corporation.

Microsoft, Yahoo and Google all deal with large amounts of data and need to look at a number of CS related issues often requiring good theoretical techniques in areas like search, auctions on search words, recommender systems, spam filtering and much more. While the research labs of the 80's and 90's (AT&T, Bell Labs, IBM, Bellcore/Telcordia, NEC and others) have pared down their research groups, Microsoft, Yahoo and Google are currently hiring many computer scientists from programming positions to pure theory researchers. For example take the two IBM theorists who organized the last Complexity conference: Sivakumar just joined Google and Ravi Kumar went to Yahoo Research which by the way is now headed by theorist Prabhakar Raghavan. You can see how important researchers are to these companies in the recent fight between Microsoft and Google over Kai-Fu Lee (whom I best know because his Othello program beat my Othello program in a 1989 tournament).

Corporate research labs go in cycles from where they need new ideas in a developing field and build up strong research groups to the point where they have have basic commodities (think long-distance phone calls) and need to cut back research groups to remain competitive. Hartmanis and Stearns developed complexity at the GE Research Labs in Schenectady and soon after both left for academic positions and a few years after that IBM and AT&T built up their theory groups. Will Microsoft, Yahoo and Google eventually find less need for theoretical research? Probably but for now, we once again see theoretical computer scientists needed by companies setting the future of computing.

Screenplays of Science

An email from Rocco Servedio.

Did you see this New York Times article? Thought you might be interested in pointing this out on the weblog, maybe a CS theory screenplay will come out of it… :)

Thanks Rocco though Suresh beat me to it. Reminds of this old (and just updated) post from the early days of this blog.

On a similar vein, my daughters are excited about Disney's new Virtual Magic Kingdom. Perhaps we need a Virtual Science Kingdom to get kids excited about math and science: Help Captain Complexity three color the map to save the Traveling Salesperson.

Moons and Planets

When I was in grade school we learned that Jupiter had twelve moons. We had a test. "How many moons does Jupiter have?" I wrote "12" and it was marked correct. In 1974 a thirteenth moon was discovered. The moon didn't just pop into existence in 1974, it was always there (at least when I took my test). Now we know Jupiter has at least 63 moons. The answer of 12 wasn't even close; what I was taught to be a fact was simply not correct.

Now we have ten planets (or is it eight?) circling our sun. Is nothing sacred? What about "My very educated mother just served us nine pies?" What other "facts" from my childhood were incorrect. Are we sure we just have one sun in our solar system?

Maybe that's why I like mathematics and theoretical computer science. Eight plus seven will always be fifteen; nondeterministic space will always be closed under complement. We know what we know; we know what we don't know; sometime what we didn't know we now know but nothing we knew later becomes false.

Two New Blogs

Chris Leonard who edits the Elsevier journals in theoretical computer science has started a weblog Computing Chris. He plans to address some of the concerns of the community to commercial publishers and Elsevier in particular. Feel free to suggest topics to Chris.

Jeff and Suresh point to David Eppstein's new weblog 0xDE. Eppstein always had a number of fun and useful stuff on his website including a catalog of the complexity various games and puzzles.

Relativizing Space

We normally define relativization to an oracle A with a special Turing machine that has an extra tape where the machine can write down a string x and move to a special state q_? and will magically go to a state q_y if x is in A and q_n otherwise.

Scott Aaronson asked me about relativization for space classes noting the difficulty of the above definition. Does the oracle tape count as space? You want a log-space bounded machine to at least write its own input on the oracle tape but you don't want the tape to be used as auxiliary storage.

Ruzzo, Simon and Tompa developed the best model for oracle relativization. They allow a long oracle tape with the following restrictions:

• The oracle tape is one-way write only.
• A nondeterministic (or probabilistic or quantum) machine must act deterministically while writing on the oracle tape.
• Once the query is made the tape is magically erased.

In this model a log-space machine can ask polynomial-size queries but these queries can be computed in log-space from the input and an extra O(log n) bits (the configuration of the machine right before writing the oracle query).

The Ruzzo-Simon-Tompa definition works well for defining Turing reductions for space-bounded machines but not so much for relativizing theorems, for example showing that alternating polynomial-time equals polynomial space for all oracles. Jonathan Buss gave a model to handle this case but we don't really get limitations on techniques for relativization results on space classes like we do for time. Best not even to bother looking for relativized space class oracles and just think of PSPACE of alternating polynomial-time in results like there is an A such that P^A=PSPACE^A.

The Secrets of Success

What does it take to be a successful in our profession?

• Intelligence. You need an innate talent in different forms to succeed as a scientist.
  • Problem Solving. Using well-established techniques in the appropriate way to find solutions.
  • Creativity. Original research means one needs to look beyond the current set of tools and develop new approaches to problems.
  • Vision. Discovering new problems and directions of research.
• Hard work. Enough said.
• Luck. Working on the right problem at the right time. If you work long enough` the law of averages will catch up with you (for good or for bad).
• Discipline. The discipline to focus on research for a period of time without getting distracted from other responsibilities or by the internet or other activities. Some people find it best to schedule time for research and hole themselves up somewhere to think about a problem.
• Commitment. Be willing to spend a considerable amount of time on a problem even if you keep running into dead ends.
• Training. Taking and working hard in classes. Having and taking advantage of a good advisor. Reading papers and textbooks. When you see a theorem in a paper try to prove it yourself first. Only then can you truly appreciate a proof and learn from it.
• Colleagues. Having co-authors, especially those that complement your talents, can help you do more than you could on your own. But just having good people to talk to, to bounce off proof ideas and discuss research directions can greatly help you find the right approach to a problem.

Powerful, Aware and Evil

The Americans develop a powerful computer to run its nuclear weapons. The Soviets develop a similar machine. The two are connected and take over the world with threats of nuclear annihilation. So goes the story of Colossus: The Forbin Project, one of the scariest movies of my childhood.

Build a powerful computer, it becomes self-aware and turns evil. We've seen this theme in many movies including 2001: A Space Odyssey, War Games and Terminator 3. Computer scientists as Frankensteins, building monsters they cannot control.

In 1982, Disney put together a TV special that tried to argue against the computers as monster theme. They could have used a better title than "Computers are People, Too!" and avoided pushing their new movie Tron about an evil computer.

Colossus did scare me as a kid but when I grew up I realized computers, as powerful as they get, don't become self-aware or inherently evil and they can always be rebooted or unplugged. Bad people can use computers in evil ways but computers themselves are just tools not the perpetrators.

I bring this up because of the new movie Stealth opening today in the States about a plane controlled by a computer that becomes self-aware and starts destroying stuff. Scaring a new generation about the evils of computer science.

Majority is Stablest

Consider the following two voting schemes to elect a single candidate.

1. Majority Vote.
2. A Majority of Majorities (think an electoral college system with states of equal size).

Which of these voting systems are more stable, i.e., less likely to be affected by flipping a small number of votes?

In an upcoming FOCS paper, Elchanan Mossel, Ryan O'Donnell and Krzysztof Oleszkiewicz prove the "Majority is Stablest" conjecture that answers the above question and in fact shows that majority is the most stable function among balanced Boolean functions where each input has low influence. To understand this result we'll need to define the terms in the statement of the theorem.

• Balanced: A Boolean function is balanced if it has the same number of inputs mapping to zero as mapping to one.
• The influence of the ith variable is the expectation over a random input of the variance of setting the ith bit of the input randomly. The conjecture requires the influence of each variable to be bounded by a small constant.
• Stability: The noise stability of f is the expectation of f(x)f(y) where x and y are chosen independently.

The majority is stablest conjecture has applications for approximation via the unique games conjecture.

Understanding Proofs

When do you understand a proof? Such understanding has many levels.

• Knowing the rough techniques used.
• Following the proof line by line.
• Can recreate the proof.
• Can explain the proof to others.
• If someone else claims a mistake in the proof, you can show them why they are wrong.
• Applying the proof techniques to other theorems.

For me for example, Toda's theorem I fully understand; the PCP theorem I sort of understand (though hopefully I'll understand it better after I teach Dinur's proof in the fall) and the parallel repetition theorem I will never understand in its current form.

Why do we understand proofs?

• Part of the job, as a referee, reviewer or advisor.
• We care about the theorem, because it is important and/or something we've worked on.
• We've heard the proof is nice and short and worth reading.
• We want to apply the proof techniques to other problems.

Unfortunately I suspect most proofs are read with the last goal in mind. A nice proof is a work of art, something to be savored, not something to be milked.

What Kind of Science is Computer Science?

In 1981, Juris Hartmanis wrote some observations on the early days of computational complexity. The article also contains some interesting discussions on issues like how CS fits in with the other sciences.

I see computer science as a brand new species among other sciences, and I believe that it differs fundamentally from the older sciences. As a matter of fact, I am convinced that in large parts of computer science the classic research paradigms from physical sciences or mathematics do not apply and that we have to develop and understand the new paradigms for computer science research. The fundamental difference between, say, physics and computer science is that in physics, we study to a very large extent a world that exists, and our main objective is to observe and explain the existing (and predict new observable) phenomena. The relations between experiments and theory are quite well understood and richly illustrated by successful examples. Computer science, on the other hand, is primarily interested in what can exist and how to describe and analyze the possible in information processing. It is a science that has to conceptualize and create the intellectual tools and theories to help us imagine, analyze, and build the feasibly possible.

Computer science is indeed a different intellectual discipline than we have ever encountered before. It shows some haunting similarities with physical sciences and mathematics (whose basic research paradigms and goals are quite different), but it differs from both of these disciplines in some very fundamental ways. As a matter of fact, quite often the paradigms, borrowed from physical sciences and mathematics, have been incorrectly applied to computer science research with predictably frustrating results. Similarly, the attempt to view computer science as an engineering discipline does not properly capture its essence. There is a substantial engineering component in computer science (or its applications), particularly in building computing machines and managing large software projects, but its core activities do not fit the traditional engineering paradigms.

In view of these observations, I believe that one of the very important tasks for the computer science community is to understand better the nature of computer science and develop the new research norms, paradigms, and methodology without which it will not mature into an independent and influential science. In particular, the relations between theoretical and experimental computer science must be clarified and new interactions must be forged. This is not just a matter of producing "more practical theories" and applications of theory, which we certainly need. It is the hard and challenging task of determining for a new science how theory, experiments, and practice should interact. Furthermore, this is not just an esoteric exercise in the philosophy of science; whether we admit it or not, our underlying beliefs, our conception of our field of study, and our perception of what is possible all fundamentally influence what kind of science we are going to build.

Complexity versus Computability

To paraphrase George Bernard Shaw, Computability Theory and Computational Complexity Theory are two fields separated by a common terminology. Computability (Recursion) Theory started in the 1930's with the work of Turing, Church, Gödel and Kleene and complexity theory gathered steam in the 60's. Complexity theory derives many of its definitions from computability theory such as Turing machines, reducibility, completeness and lowness and the polynomial-time hierarchy is an analogue of the arithmetic hierarchy. Several complexity theorists originally received their Ph.D. in computability theory.

One can say computational complexity is just computability theory with resource bounds but the fields feel quite different.

• Complexity theorists consider themselves part of the theoretical computer science community and find themselves mostly in CS departments. Recursion theorists consider themselves logicians and find themselves mostly in math departments.
• Complexity theorists try to understand efficient computation analogous to theoretical physicists trying to understand how the universe works, where computability theorists consider more ethereal questions of logical definability. Consider the example of quantum computing: Many complexity theorists analyze the computational power of these machines where quantum has had virtually no effect on computability theory.
• Outside of diagonalization, the tools and techniques used in the fields are completely different. Rare does one see a priority or finite injury argument in complexity, whereas algebra and combinatorics don't appear in most computability proofs.

The University of Chicago has had for many years a strong presence in computability theory led by Bob Soare who wrote a major textbook in the area. I sat in Soare's class in the hope some of the techniques in computability would help my research in complexity (for the most part they haven't) and have gone to a few logic seminars. Everything I do they call "zero."

The difference in thinking hit me during a logic seminar where the speaker asked "How do we usually show that a language is computable?" I thought find an algorithm. The speaker answered his own question "Show that the language is c.e. and co-c.e."

Magic is in the Eye of the Beholder

I just finished the latest Harry Potter book. Amazing how much you can read when stuck at an airport. It seemed like half the people at the Seattle airport on Monday were reading that book.

No spoilers in this weblog. Let's just say the wizarding community has seen better days.

Ever notice that except for a few new potions and spells, technology has not changed much in the wizard world. If Hermione could only google "half-blood prince" she wouldn't have to spend so much time in the library. Email beats owls any day. Wouldn't it be nice for them to have some music in their lives, an iPod or at least a radio?

This is what happens in a culture where they don't teach their young science and math and no one seems to go to college.

Winnie the Mathematician and a Few Comments on Comments

Today's Science Times has an article on Danica McKellar an mathematically-talented actress, best known for her role as Winnie on Wonder Years. She has a Bacon number of two and an Erdös number of four, the first completely legit example I know of someone with finite Bacon and Erdös numbers.

An administrative issue on comments. Because I apparently violated a security policy on our department computers, you can no longer post new comments on the old commenting system, that is on posts before May 9, 2004 as well as the General Comments link. You still can read the old comments and post comments on posts since May 9, 2004.

And while I'm on the topic of comments and because some have asked, I have never and never will post a comment anonymously on this weblog. I encourage everyone to sign their comments (what do you have to hide) or at least use an alias so we can match comments to the same writer. Still I'd rather you leave comments anonymously than not leave them at all.

I've also been asked about deleting comments. I reserve the right to delete any comment but so far have done so only in the following cases:

1. Duplicate comments.
2. Comment spam.
3. Once because the author of the comment requested it to be deleted.
4. Once because the comment was too long. The comment started with something like "I wrote a book on the topic and here is the first chapter…" If you have something long to say put it somewhere else on the web and put a link in the comments.

Computer Science Has Been Very Very Good To Me

Ever notice how computer science departments in the US are like baseball teams. They try to hire the best players so they can be better than other departments (try to be in the "top ten" for instance). Already strong departments with lots of resources continue to hire the best people and become even stronger. MIT, despite being close to Boston, is like the New York Yankees of computer science.

One can push an analogy too far and I've already crossed that line but let's keep going.

• Baseball players are initially tied to a certain team though after a certain number of years they can become a free agent or prevent their team from trading them. Professors can become free agents after any year and after seven years, if they are still with the department, get a no-fire clause.
• Baseball teams have minor leagues to train young players. We have graduate students.
• Baseball has had a strong commissioner who mediates disputes and can make changes for the good of the game. We could use someone like that.
• Baseball sells naming rights of its stadiums. Universities sell naming rights of their buildings.
• Baseball has a hall of fame honoring the very best. We have the Turing award. But like baseball we could also have a physical location with memorabilia like the original draft of Cook's paper or the chalk Manindra Agrawal used to prove Primes in P with his students.
• Baseball teams trade players. Imagine David Karger and Madhu Sudan for Umesh Vazirani, Luca Trevisan and a grad student to be named later.

Do Only Simple Theorems Have Simple Proofs?

My technical posts rarely draw many comments but Tuesday's post on Savitch's Theorem brought a long discussion on hard versus easy proofs that started with this comment.

This is a good example of how STOC/FOCS have grown significantly in quality over the years. Savitch's theorem was in STOC 1969, and the proof is trivial.

The proof of Savitch's theorem is easy (trivial is a little strong) but the result was surprising at the time and has had a profound impact on complexity since. I'd love to see STOC and FOCS have results this easy and this important.

I had mentioned before that an easy proof can hurt your chances of acceptance at a conference. Let's take a look at the viewpoint of the program committee.

If you have a previously established hard theorem, one that many people have worked on but no proofs or only complicated proofs have been found, then short proofs are valued. Dinur's proof of the PCP theorem fits in this category. A simple proof of the parallel repetition theorem or the unique games conjecture would also be welcome in STOC or FOCS.

But most papers at STOC and FOCS do not solve previously established hard theorems. They extend previous work, improve bounds or make partial progress towards the major open questions. The program committee has to decide whether the result represents real progress or it just easily follows from previous work. An easy proof gives an indication of the latter.

Unfortunately this gives an incentive for the authors to make their proofs look difficult in their papers. A quick way for a PC member to kill a paper is to show an easy proof but the committee doesn't have the time to try and find easy proofs for all the submissions.

MC Plus +

Guest post from theory music expert Bill Gasarch.

There is some (not a lot) of novelty songs about computer science, and less about theory.

There is a new CD (with mp3 downloads) of computer science songs in Gangsta Rap style.

One of the song is about Alice and Bob transmitting messages, so that would qualify as theory.

The CD is more interesting than funny.

Warning: Not suitable for children.

Favorite Theorems: P = NP for Space

June Edition

In 1970 Walter Savitch proved one of the truly classic results in complexity showing that one can simulate nondeterministic space in deterministic space with only a quadratic slowdown.

Walter Savitch, Relationships Between Nondeterministic and Deterministic Tape Complexities, Journal of Computer and System Sciences, 1970.

In complexity terms, for any space constructible function s(n) ≥ log n,

NSPACE(s(n))⊆DSPACE(s²(n))

You can find the proof in an earlier post.

As a consequence you get PSPACE=NPSPACE, which is why you don't see NPSPACE in the zoo.

Chandra, Kozen and Stockmeyer used a modification of the Savitch algorithm to show that polynomial space can be simulated in alternating polynomial time. This relationship led to showing lots of games PSPACE-complete and played a critical role in showing IP=PSPACE.

Circuit wise, Savitch's algorithm puts NL (nondeterministic log-space) in SAC¹ (log-depth circuits with constant fan-in ANDs and unbounded fan-in ORs).

For a directed graph G=(V,E), let G^k=(V,E^k) where (u,v)∈E^k if there is a path of length at most k from u to v in G. One way to view Savitch's theorem is to compute G^2k from G^k using O(log n) additional space. You then apply this graph powering log n times to get from G=G¹ to Gⁿ where (u,v)∈Eⁿ if there is a path from u to v in G.

Reingold uses a similar paradigm in his result that SL = L. He shows for undirected graphs that you can do a weaker form of graph powering (using expander graphs) but with a similar effect using only O(1) additional space at each step.

But after 35 years we still have no better upper bound on the deterministic space complexity of NL than O(log² n) from Savitch's Theorem.

The Organized Scientist

Some professors consider it a badge of honor to keep huge stacks of papers covering their desk and often most of their floor. But in reality once you bury a paper in other papers you won't ever deal with it or find it again when you need it. We are really no different than any other professional and just a few simple techniques can greatly unclutter your life.

For every piece of paper that enters your life you should do one of three things:

1. Trash (or recycle) it.
2. File it away, and it its an action item put it on your To Do list.
3. Deal with it right away and then do one of the above.

Do not just drop it on your desk for future action. It will get covered by another piece of paper and you might as well have recycled it.

If it is a form that needs to be filled out than do so. If it is something you don't have time for now (like a referee report) than keep those in a special place in your desk and add it to a To Do list.

The above rules apply to email as well.

For a To Do list, I use the Tasks page on Yahoo Calendar which I can access from any computer (and it's free). I use the "Due Date" field as a start date so I can sort tasks by when I want to do them.

If you print a paper from the web to read and you think you might need it again in a week or so what should you do? Recycle it and print it again when needed. Don't tell me I'm wasting paper. You'll just print it again when you can't find it anyway. As a general rule you should never save anything you can find on the internet.

How to get started? Go through all of your papers in your office applying the rules above. Too much effort. Then recycle everything. You weren't going to deal with them anyway and now you'll have a clean office and be ready to stay organized.

Computer Science in High School

When I went to high school (1978-81) we had a computer room with three teletype machines that connected at 10 characters/second and we saved programs on paper tape. We also had a math teacher, Mr. Jaeger, who taught us not only how to program those computers but also used them to teach concepts like probability. We would run simulated card shuffling algorithms to test our calculations of the probabilities of poker hands.

A recent AP article says that computer science courses in high schools are getting less interest from students as well as from the states setting curriculum. This decline in interest at high school leads to the decline in CS majors we see throughout the American universities. A similar phenomenon is going on in many other countries as well.

The usual reason given is the perception of a weak job market in computers. But I think there is another issue. In my high school days, outside of a few games you couldn't do much with a computer unless you programmed. Today computers have become almost as commonplace as televisions and teens use them for a variety of tasks, including researching on the web, communication via email, instant messaging and blogging, and writing papers, all without an inkling of how to program. Computers have become a commodity and they don't see an additional value in knowing how and why they work any more than they need to know physics to drive their cars.

One of the great challenges of computer science was to make computers important and useful in everyday life. We are now becoming victims of our success.

Matrix Rigidity

Nanda Raghunathan points me to a new paper by Gatis Midrijanis giving a simple proof of the best known rigidity lower bounds for the Sylvester matrices.

The rigidity of a matrix M is a function R_M(r) equal to the minimum number of entries of M that you need to change in order to reduce the rank to r. Strong rigidity bounds would have applications for circuit and communication complexity.

Let N=2ⁿ. We define the N×N Sylvester S by labeling the rows and columns by n-bit vectors and let s_i,j=(-1)^i·j.

Theorem: If r ≤ N/2 is a power of 2 then R_S(r) ≥ N²/4r.

Proof: Divide S uniformly into (N/2r)² submatrices of size 2r×2r. One can easily verify these submatrices each have full rank. So we need to change at least r elements of each submatrix to reduce each of their ranks to r, a necessary condition to reducing the rank of S to r. QED

This proof works for any matrix whose submatrices have full rank. Consider the N×N matrix B where b_i,j=1 if i ≡ j (mod 2r) and 0 otherwise. By the same proof R_B(r)=N²/4r even though the rank of B is only 2r.

The moral of this story: We conjecture that the Sylvester matrices have very high rigidity but we still lack the tools that make full use of the structure of these matrices.

Different Views of Consciousness

The great game theorist Robert Aumann writes about consciousness.

Sometimes, people express perplexity as to the nature of the problem. They do not see anything mysterious about consciousness, and do not understand in what way it is different from other neurological functions like, say, the regulation of breathing. Asked whether a computer could in principle be conscious, they answer, "why not?"

We are dumbfounded by this reaction, and can only conjecture that these people are themselves not conscious. To me, it is evident that no combination of silicon chips and wires could conceivably "experience" in the sense that I do. Consciousness involves something beyond the merely physical and mechanical.

A bit of a different view than that of Manuel Blum.

The question whether an entity is CONSCS is a function of its algorithms, not the stuff (silicon or carbon) that implements those algorithms.

Why are great scientists like Blum and Aumann taking on consciousness late in their careers? One of the many possible research questions Blum threw out in his talk:

What happens when an entity stops being an entity?

So perhaps they study consciousness as a way to deal with their own mortality.

Independence Day in America

Old Joke: Is there a fourth of July in Canada? Sure there is, right between the third of July and the fifth of July.

Outside of the US the Fourth has no special meaning so non-Americans have no qualms running conferences and workshop over our holiday. This will be my first time in three years spending the entire Independence Day in the US. Last year I was in Banff and in 2003 on a plane to Denmark. (I may not collect much sympathy here.)

How will I celebrate America's 229^th Birthday? A parade in the morning, a friend's house for barbecue and capping the night with fireworks. Should be a perfect Fourth.

Research Directions for Theory

Sanjeev Arora asked the "theory blogs" to take up the issue of finding a few new challenges of theory that one can sell to nonspecialists and congressional aides. SIGACT has set up an outreach committee led by Richard Karp that will prepare a list of research directions for the theory community and they want your input. More from Suresh.

I feel a little déjà vu here. Ten years ago Karp led a NSF sponsored group with the mission of suggesting where the NSF theory group should focus its funding. The group held a panel discussion at the end of the 1995 STOC conference. Representatives from different subfields gave a short talk on the importance of their fields. After these presentations the panel opened the discussion to the audience.

Now instead of a physical panel discussion, Arora asks for a virtual one in a hope to draw from a larger base of people. Feel free to leave your ideas as comments on this post, on the committee page of the Theory Matters Wiki (edit password: tcs), or just by email to one of the committee members. Not everyone was happy with the last Karp report, so better to get your comments in now than complain afterwards.

FOCS Accepts

The list of accepted papers for the upcoming FOCS Conference has been posted (via Suresh via Bacon). Given recent comments the Internet really raises expectations on how fast we get to see the list. As I write this the list still has a mysterious "One extra paper" at the end.

In complexity two of the unique games papers I mentioned on Monday will be at FOCS. Some other interesting looking complexity papers:

• Mark Braverman, On the Complexity of Real Functions.
• O'Donnell, Saks, Schramm and Servedio, "Every decision tree has an influential variable". I can't find the paper online but here is a talk abstract. Update 6/30: Paper is now available.
• Ran Raz, Quantum Information and the PCP Theorem where he shows, among other results, that every language has a quantum interactive proofs with quantum advice.

Looks like the big area winners at FOCS are upper and lower bounds on approximation, electronic commerce and cryptography.

Defining Theory

Theory Matters points to a definition of Theoretical Computer Science given on the SIGACT Home Page.

The field of theoretical computer science is interpreted broadly so as to include algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.

This definition first appeared in the December 1997 SIGACT News with a slightly different order and missing quantum computation and automata theory.

I dislike these "laundry list" definitions. They both tend to overcompensate by listing too many areas (e.g. "the study of randomness" is really subsumed by the other areas) and failure to capture all the areas we study (e.g. electronic commerce). Such lists cannot remain stable over time and need constant updating. We find it hard to delist any areas even if we should.

Most importantly laundry lists don't capture the spirit of a field. If we really wish to sell our field properly we need to start with a clear definition. Here is a suggestion.

Theoretical Computer Science is the formal analysis of efficient computation.

Simplicity should beat complexity every time.

The Unique Games Conjecture

A unique game consists of an undirected connected graph G=(V,E), a color set C, and for each edge {i,j} with i<j a permutation π_i,j:C→C. A coloring of the graph c:V→C fulfills an edge {i,j} if π_i,j(c(i))=c(j).

There is also a linear version of unique games where C is a finite field and for each {i,j}, π_i,j(x)=a_i,jx+b_i,j with a_i,j and b_i,j in C and a_i,j≠0.

If a coloring fulfills all the edges then knowing the color at one edge uniquely determines all of the other colors. One can efficiently determine whether such a coloring exists by trying all possible colors at one node and seeing if any of the resulting coloring fulfills all the edges.

However it might be difficult to determine whether one can fulfill some large fraction of the edges. Subhash Khot defines the unique games conjecture.

For every constant δ>0 there is a fixed finite color class C such that it is NP-hard to distinguish the following two cases for any unique game with color class C.

1. There is some coloring that fulfills at least 1-δ-fraction of the edges.
2. Every coloring fulfills at most a δ-fraction of the edges.

Some results on unique games:

• Khot, Kindler, Mossel and O'Donnell reduce unique games to approximating Maximum Cut better than the best known approximation due to Goemans and Williamson (about 0.878567). Khot et. al. also required a "Majority is Stablest" conjecture which was later proved by Mossel, O'Donnell and Oleskiewicz. Thus under the unique games conjecture any improvement in approximating Max Cut would imply P=NP.
• Similar results showing that given the unique games conjecture (and P≠NP) it is hard to approximate Vertex Cover with 2-ε (Khot-Regev) and Sparsest Cut within any constant (Chalwa-Krauthgamer-Kumar-Rabani-Sivakumar).
• Luca Trevisan shows that we can solve the unique games in polynomial time if we allow δ=o(1/log n) instead of a constant.
• In an upcoming FOCS paper, Khot and Nisheeth Vishnoi use unique games to (unconditionally) disprove the conjecture that negative type metrics (metrics that are squares of Euclidean metrics) embed into L₁ with constant distortion. They also show a superconstant lower bound on the integrality ratio for Semi-Definite Programming relaxations for Sparsest Cut.

The introduction of Trevisan's paper gives a nice overview of unique games.

Update 6/28: The hardness of approximating sparsest cut given the unique game conjecture is also in the Khot-Vishnoi paper done independently from CKRRS. Also Khot has a recent survey in SIGACT News on PCP-based hardness results that has a section on unique games.

The End of an Era?

On May 13 in the US, the Star Trek franchise (temporarily?) ends 18 straight years of first-run episodes. Bill Gasarch comments.

About a month ago was the final episode of ENTERPRISE. I just saw it last week. I assume that NONE of the readers are saying "Gee, how did he do that!"

At one time many computer scientists were also science fiction fans.

At one time both were small communities (with enrollment dropping computer scientists may return to being a small community).

At one time you couldn't time-shift how you watched TV so people would talk about the same show the next day.

At one time there was not so much Science Fiction out there so all the fans graviated towards the same materials.

So in the past there was much more cohesivness to the CS/Sci-Fi community.

There is no longer.

Is this good or bad?

I thing its good to NOT be so homogenous. New ideas come from all kinds of places. And you don't want people who are not Sci-Fi fans to NOT major in Comp Sci since they think they have to be.

Herbie: AI Marvel

Rarely do people notice the true technological breakthroughs in science fiction and fantasy movies. Roger Ebert gets it in his review of the rather silly Herbie: Fully Loaded, a new entry in the series about the mischievous car.

I see I have subconsciously stopped calling Herbie "it" and am now calling Herbie "he." Maybe I've answered my own question. If Herbie is alive, or able to seem alive, isn't this an astonishing breakthrough in the realm of Artificial Intelligence? That's if computer scientists, working secretly, programmed Herbie to act the way he does. On the other hand, if Herbie just sort of became Herbie on his own, then that would be the best argument yet for Intelligent Design…

The real story is Herbie's intelligence. The car seems to be self-aware, able to make decisions on its own, and able to communicate with Maggie on an emotional level, and sometimes with pantomime or by example. Why then is everyone, including Lohan, so fixated on how fast the car can go? The car could be up on blocks and be just as astonishing.

It goes to show you how we in the press so often miss the big stories that are right under our noses. There is a famous journalistic legend about the time a young reporter covered the Johnstown flood of 1889. The kid wrote: "God sat on a hillside overlooking Johnstown today and looked at the destruction He had wrought." His editor cabled back: "Forget flood. Interview God."

Communicating Open Problems

A famous complexity theorist once said "The hardest part of being an advisor is not working on your student's problems." Good open problems are quite rare and one is often torn between the desire to see a problem resolved as quickly as possible versus giving people a fair chance to work on them. So I put together a set of guidelines for distributing problems.

1. If you ask someone about what problems they are working on you shouldn't start working on those problems or give them to others without permission. When this rule is violated, even students in the same department are sometimes afraid to discuss their own research with each other.
2. If someone discusses a problem with you shouldn't mention the problem to others without permission. Asking a question like "Do you mind if I tell this problem to my students?" is sufficient.
3. If you are an advisor and you give a problem to a student you shouldn't work on the problem yourself or give it out to other students without the first student's permission.
4. Outside the advisor-student relationship the above rule does not apply. You can work on a problem even if you give it to someone else or distribute it as you wish unless you've had a prior agreement.
5. Once you make a problem public (in a talk, in a paper or on the web) the problem is fair game to all.

I realize I have not always followed all of these rules myself and I apologize. One could argue that one best advances science by making all problems as widely available as possible but following these guidelines will open communication as researchers will have less need to hide what they work on.