Complexity Year in Review

Theorem of the year goes to Omer Reingold who shows Undirected Connectivity in Logarithmic Space, settling the long-standing open problem. Also of note, Ran Raz's lower bounds on multilinear formulas and a series of paper extracting randomness from independent sources I had mentioned earlier as well as new improvements by Raz. We had many other great results throughout the year, check out the ECCC to sample many of them.

The National Science Foundation and computer science funding face a challenging future. We have seen the end of the ITR program that has poured needed money into IT research. CISE reorganizes (putting complexity theorists and numerical analysts into the same program for example) as they struggle to meet a new reality of CS funding. To add to the burden the NSF had an actual decrease in its funding for FY 2005.

The decrease in foreign graduate students as US schools made news over the past year. The difficulty in obtaining visas since the terrorist attacks in 2001 certainly play a role but I give more weight to stronger local alternatives manned by many of those foreign students we have educated over the last several decades.

We lost three prominent members of our community: Shimon Even, Carl Smith and Larry Stockmeyer.

Outside of complexity we had an election that divided this country (but not the scientists), the Red Sox winning the world series and an ongoing struggle in Iraq. Unfortunately the year ends with a terrible natural disaster and we all should support the efforts to help those affected recover from this tragedy.

Copyrights on Conference and Journal Papers

A guest post from Alan Selman

It is a common and acceptable practice to present a preliminary version of a paper at a conference and then to submit the full paper to a refereed journal. The Foreword of a recent STOC proceedings states, for example,

The submissions were not refereed, and many of these papers represent reports of continuing research. It is expected that most of them will appear in a more polished and complete form in scientific journals.

That is the ideal. In practice, many of us have been in the habit of putting complete versions of accepted papers in conference proceedings. This is not a wise strategy. Assuming that the publisher of the conference proceedings holds copyright of the papers that appears in the proceedings, the paper that one submits to a refereed journal must be substantially different from the one that appears in a conference proceeding in order to avoid copyright infringement. I asked my contact at Springer, the publisher of the journal Theory of Computing Systems, how different the journal version of a paper should be from the conference version, and was told to use 25% as an acceptable guideline. This is a reasonable response that should not too difficult to manage for theorists, and can be taken up by proofs and explanations that were not included in the conference version. I should add however, that Lance Fortnow asked the same question of IEEE, the copyright holder for papers that appear in the Conference on Computational Complexity, and the response was far more onerous. Lance's contact at IEEE called for 30% to 70% new material, and material from the original paper should be there only to support new ideas. I would rather abide by Springer's recommendation than IEEE's. The essential point is that the journal version must be essentially different from the conference version.

Computation and the Socio-Economic Sciences

Fred Roberts, Rakesh Vohra and myself are co-charing the DIMACS Special Focus on Computation and the Socio-Economic Sciences, a series of workshops and other activities designed to bring together computer scientists and social scientists. The focus has already hosted some good workshops on topics like Electronic Voting and Auctions. Let me put in a plug for a couple upcoming workshops.

At the end of January, Richard McLean, Daijiro Okada and myself are organizing a workshop on Bounded Rationality at Rutgers. Bounded rationality looks at game theory questions like equilibria with computationally-bounded participants.

Immediately following the Bounded Rationality workshop is the workshop on Markets as Predictive Devices (Information Markets). The organizers Robin Hanson, John Ledyard and David Pennock have created a program with a set of speakers that spread the range from theory to practice in markets designed to estimate the probability of future events. The program ends with a panel discussion on the Policy Analysis Markets that came under fire a year and a half ago for its "terror futures".

In mid-April, Rakesh Vohra and I are organizing a workshop on Large-Scale Games to be held at Northwestern. This workshop will examine questions in game theory that deal with issues in large scenarios like the internet with many players, incomplete information, lack of common knowledge, asynchrony and related problems.

We have two other scheduled workshops in the focus, Polyhedral Combinatorics of Random Utility in June and Yield Management and Dynamic Pricing in August, and many more workshops under development.

Tragedy in Asia

Chennai, the location of the recent FSTTCS conference reviewed in the last post, was one of the areas hit hard by today's earthquake caused tsunami. The globalization of science really makes these tragedies seem close even to those of us on the other side of the planet.

Our condolences and prayers go to those in all areas affected by today's events.

FSTTCS 2004 at Chennai

By Prahladh Harsha and Jaikumar Radhakrishnan

It was nice to be back in Madras after a long time and even nicer to meet friends from MIT and elsewhere during this year's Foundations of Software Technology and Theoretical Computer Science Conference. FSTTCS is the longest-running international conference on computer science in India, and is organized under the aegis of the Indian Association for Research in Computing Science (IARCS).

The 24th edition was held in Chennai between Dec 16 and Dec 18. The conference was preceded by two workshops on Algorithms for dynamic data (Dec 13 - 14) and Logics for dynamic data (Dec 15). Here are a few statistics about this year's FSTTCS: 38 accepted papers (out of 178 submitted from 38 countries), attendance of about 175 (nearly 35% from outside India). The invited speakers: Pavel Pevzner (UCSD), Javier Esparza (Stuttgart), Piotr Indyk (MIT), John Reynolds (CMU) and Denis Therien (McGill). The proceedings of the conference were published by Springer in LNCS series.

FSTTCS attracts papers in Logics & Semantics and Algorithms & Complexity. Biased by our interests, we attended only the presentations on Algorithms & Complexity. In our view, the highlights were:

• M Fürer, S P Kasiviswanathan, An almost linear time approximation algorithm for the permanent of a random (0-1) matrix.
• A K Ponnuswami, H Venkateswaran, Monotone Boolean circuits for bipartite perfect matching require exponential size.
• L Radamacher, S Vempala, Testing geometric convexity. This paper demonstrates that testing whether a given set S in R^n is convex or far from convex (in the property-testing sense) can be determined by queries, whose number is independent of the actual size of the set S, but is however exponential in the dimension of the space (i.e., n). The set S is presented to the tester by a membership oracle and a random oracle.
• J Hitchcock, A Pavan, Hardness hypotheses, derandomization and circuit complexity. This paper shows that the NP-machine hypothesis is implied by both the Measure hypothesis and pseudo-NP hypothesis. These 3 hypotheses are some of the commonly used hypotheses in derandomization. Furthermore, the authors show that several of the derandomization and circuit lower-bound results that are known to follow from the latter two hypotheses also follow from the NP-machine hypothesis.
• J Kempe, A Kitaev, O Regev, The complexity of the local Hamiltonian problem. The local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It was known that the 1-local Hamiltonian problem is in P while the k-local Hamiltonian problem is QMA-complete for k >= 3. This paper settles the case for the 2-local Hamiltonian problem and shows that it is also QMA-complete. Thus, the k-local Hamiltonian problem is similar in spirit to MAX-k-SAT which is NP-complete for k > = 2.

Some authors could not attend the conference. The paper Minimum weight pseudo-triangulations by J Gudmundsson and C Levcopolous was presented beautifully by Mark de Berg. The paper on No, coreset, no cry by S Har-Peled, was presented by Kasturi Varadarajan. The author did not get a visa in time from the Chicago consulate (there are some advantages to traveling on an Indian passport), and had sent a recording of his presentation. In the end, Kasturi did a wonderful job using only the slides, but one was left wondering what the video looked like.

Prof. Rani Sirmoney, who turned 75 in July 2004, was honored in a special session at the conference. Prof. Sirmoney is a senior and highly respected theoretical computer scientists in India who works in the area of Formal Languages, Automata Theory, Machine Learning and DNA Computing. She has nurtured several generations of researchers through her teaching and collaborations. In her speech, she thanked her colleagues at the Madras Christian College for their support and encouragement, and mentioned, among other things, that she never faced any gender-based discrimination at that institution.

Favorite Theorems Recap

In 1994, I listed My Favorite Ten Complexity Theorems of the Past Decade in conjunction with an invited talk at that year's FST&TCS conference. Over this past year in this weblog I went back and picked my favorite ten complexity theorems of the decade since that first paper.

• Derandomization (Impagliazzo-Wigderson)
• Primality (Agrawal-Kayal-Saxena)
• Probabilistically Checkable Proofs (Håstad)
• Connections (Trevisan)
• Superlinear Bounds on Branching Programs (Ajtai)
• Parallel Repetition (Raz)
• List Decoding (Sudan)
• Learning Circuits (Bshouty-Cleve-Gavaldà-Kannan-Tamon)
• Quantum Lower Bounds (Ambainis)
• Derandomizing Space (Saks-Zhou)

The purpose of these endeavors is not just to have a top ten list but to use these great results to highlight several areas in computational complexity where we have seen significant progress in recent years. Ten areas do not do justice to complexity and we also have great results in proof complexity, Kolmogorov complexity, constructions of expanders and extractors, zero-knowledge proofs and structural complexity.

We'll do this again in ten.

Numb3rs

Coming in January to the American television network CBS, a series about a FBI agent who recruits his brother, a math genius, to help solve crimes. I don't hold much hope for realism in Numb3rs (anyone remember Q.E.D.?) but any show that shows mathematicians in a good light helps shape public perception of our field.

I would like to know the "actual events" that inspired this series.

Ooscla

One of my Indian graduate students mentioned the university yookla and gets confused when I talk about Texas (not UTA) or Illinois (as opposed to UIUC which is too easily confused with UIC).

So for the foreigners out there, here is a quiz for the common names for some major American universities, which all native-born Americans know because of their sports teams.

• USC (not ooscla or USCLA)
• South Carolina (not USC)
• Wash U (not woostle) as opposed to Washington or George Washington or Wash State
• California or just Cal. Though I would never say "Cal Prof Luca Trevisan"
• UTEP this time pronounced U-tep.
• Bama as opposed to UAB
• Mizzou
• Ole Miss
• UVM
• Wisconsin as opposed to UWM
• Maryland not UMCP as opposed to UMBC
• Miami (FL) as opposed to Miami (OH)

I could go on forever. Sometimes the name depends on where you say it. In Illinois we have Northern, Southern, Western, Northeastern as well as Northwestern.

Quality Matters

A commenter yesterday asked about a Crooked Timber post arguing that many strong departments place an emphasis on hiring students from other strong departments more than their actual publication record. The Crooked Timber post focuses on the social sciences and the hard sciences can and do put more focus on research itself.

In computer science, particularly in theoretical computer science we can really judge the quality of a student's research in a more objective way than a paper in say sociology. It does not matter where you got your Ph.D., if you didn't have strong results as a graduate student you won't find employment at a top university. If one does have solid results from a lesser known school one can find a top academic job though admittedly this happens less often.

I won't deny a strong correlation between where you got your Ph.D. and where you get employed: The best undergraduates choose the best graduate schools. At the strong schools you can usually find stronger faculty as potential advisors, stronger fellow students to work with and push you and you will have letter writers with stronger credentials when you do enter the job market. There is a social network among stronger schools that we cannot ignore. And some places, particularly those without experts in an area, will put too much emphasis on a student's department.

But we can better measure the quality and importance of a student's research and impact and that always plays the most critical role in whether one offers that person a position in a particular field.

Decryption by Clancy

Consider the following paragraphs from Tom Clancy's 1998 novel Rainbow Six.

The phone they spoke over was the Russian version of the American STU-3, the technology having been stolen about three years before by a team working for Directorate T of the First Chief Directorate. The internal microchips, which had been slavishly copies, scrambled the incoming and outgoing signals with a 128-bit encryption system whose key changed every hour, and changed further with the individual users whose personal codes were part of the insertable plastic keys they used. The STU system had defined the Russians' best efforts to crack it, even with exact knowledge of the internal workings of the system hardware, and they assumed the the Americans had the same problems—after all, for centuries Russia had produced the world's best mathematicians, and the best of them hadn't even come up with a theoretical model for cracking the scrambling system.
But the Americans had, with the revolutionary application of quantum theory to communications security, a decryption system so complex that only a handful of the "Directorate Z" people at the National Security Agency actually understood it. But they didn't have to. They had the world's most powerful supercomputers to do the real work. They were located in the basement of the sprawling NSA headquarters building, a dungeonlike area whose roof was held up with naked steel I-beams because it had been excavated for just this purpose. The star machine there was one made by the company gone bankrupt, the Super-Connector from Thinking Machines, Inc., of Cambridge, Massachusetts. The machine, custom build for NSA, had sat largely unused for six years, because nobody had come up with a way to program it efficiently, but the advent of quantum theory had changed that, too, and the monster machine was now cranking merrily away while its operators wondered who they could find to make the next generation of this complex machine.

I doubt anyone could turn a souped-up ConnectionMachine into a quantum computer. But one could imagine some smart NSA scientists finding a way to simulate a variation of Shor's quantum factoring algorithm on such a device, well enough to break moderately long RSA codes. Just thinking.

Favorite Theorems: Derandomizing Space

November Edition

We started this list of favorite theorems with derandomization of time classes. Now we end the list by looking at derandomizing space-bounded classes.

Over the last fifteen years we have seen several exciting results on removing randomness from space. Unlike time they require no hardness assumptions but until very recently didn't achieve full derandomization.

The techniques of Savitch's Theorem give us that randomized logarithmic space sits in deterministic log² space. We will focus on results that reduce the space needed to simulate randomized algorithms and the space for the most well-known randomized space algorithm, undirected s-t-connectivity.

Aleliunas, Karp, Lipton, Lovász and Rackoff showed that one can solve s-t connectivity in randomized logarithmic space by taking a random walk on the graph. Nisan, Szemeredi and Wigderson give a log^3/2 algorithm for s-t connectivity. Saks and Zhou give the same bound for every problem in randomized log space.

BP_HSPACE⊆DPSACE(S^3/2) by Michael Saks and Shiyu Zhou

Saks and Zhou's result remains the best known bound for randomized logarithmic space but we can do better for s-t connectivity. Armoni, Ta-Shma, Wigderson and Zhou improved the s-t connectivity bound to log^4/3 space. And just a few weeks ago we had Reingold's result putting s-t connectivity in the optimal logarithmic space, currently a front runner for the next favorite theorems list in 2014.

Can We Fairly Teach and Grade?

Academic bloggers (like Jeff and Suresh) are up in arms about a column by Ailee Slater in the University of Oregon student paper.

We are currently paying a large amount of money to attend this University and receive an education. If I have paid to be taught something, shouldn't there be a repercussion for the teacher rather than, or at least as well as, the student when knowledge has not been taught?

Although teachers cannot be responsible for the self-failings of their students, it still seems unfair that they are allowed to judge how much a particular student is learning. I pay the teacher to teach me, and then I get slapped with the label of failure if the teacher deems that I haven't learned the correct information?

If students only paid for education they why would my grade matter? Whether I give you an A or a D won't affect how much you actually learned over the quarter. Students also want a certificate of quality of that education (a diploma and a transcript) to further their future careers. No legitimate university would give such certification just for tuition money. They need to verify that the students have indeed learned. That's why we have a grading system.

But Ailee does have a good point: I do have a conflict grading the students based on what I tried to teach them. Most of us try our best to grade fairly but deep down we know if a hard-working student hasn't mastered the material perhaps we should have taught differently. We often tend to overcompensate for this bias leading to grade inflation.

Unfortunately, other than standardized exams, I see no other reasonable alternatives of evaluating students. So professors need to grade students as fairly as they can and students need to acknowledge that education is not just a right but also a responsibility even when they are paying for it.

A Map of Complexity Classes

Iowa State graduate student Chad Brewbaker created a graphical map of the complexity classes in the zoo. Who says you can't have fun with complexity?

The Other Nigerian Scam

Volunteer to organize a conference and I guarantee you will get an email like the following

I am a computer scientist from Nigeria. I am interested in attending your conference. I come from a very poor university and I am in need of funds and/or please write me a letter for visa.

They play to our vanity and our desire for diversity. Wow, Africans interested in computational complexity! Don't be fooled, in nearly every case they have no interest in computer science, they just want an easy way to come to Europe, the US or Canada.

There is that small chance a poor African student really is interested in complexity so I typically reply to such letters by

Thank you for your interest in our conference. Please send us your latest CV and a statement explaining your reasons for attending the meeting and we will be happy to consider your request.

In every case I have never heard from the letter writer again.

The NSF Gets Some Attention

The National Science Foundation rarely gets mentioned in the popular press. After the recent budget cut, the NSF now gets some mention, including a New York Times article, editorial and Thomas Friedman's column and an editorial of the the San Jose Mercury News. Perhaps taking a cut this year will help NSF in the long run as congress should no longer feel it can cut science funding without anyone noticing.

However, the US budget process takes the greater part of a year and we need to put pressure at many points, from the initial proposed budget from the White House to the various committees to the final vote in the fall. Complaining after the fact alone will not help the NSF but instead we need to make the case during each part of the process particularly when the final budget bills get approved starting in September.

When Average Case is the Worst Case

Birthday Boy Rocco Servedio gave a talk at TTI on Friday on learning random functions over random inputs. John Langford asked about distributions that put more weight on simpler string, those of lower Kolmogorov complexity. That reminded me of a nifty 1992 result of Ming Li and Paul Vitányi.

Fix your favorite programming language and let K(x) be the length of the smallest program generating string x. Define μ(x)=2^-K(x), known as the universal distribution for reasons I won't get into here. Notice how strings of smaller complexity get more weight.

Theorem (Li-Vitányi) Any algorithm using time T(n) on average over the universal distribution uses time O(T(n)) in the worst case.

Li and Vitányi prove their theorem by showing that if the set of worst-case inputs is small they will have a short description and thus more heavily weighted under μ. Read all the details in their paper.

Bad Timing

Texas student Vladimir Trifonov gives An O(log n log log n) Space Algorithm for Undirected Connectivity. If it came out a few months earlier (assuming the proof is correct) it would have been an amazing result, greatly improving the previously best known O(log^4/3 n) bound. Unfortunately for Trifonov, Omer Reingold announced his result giving the stronger O(log n) space algorithm a few weeks earlier. Trifonov's work was done independently from Reingold.

Trifonov's proof uses techniques based on PRAM algorithms for connectivity completely different from Reingold's zig-zag methods.

Use Google to Search Your LaTeX Files

In the month of November 44.3% of the hits on this website came from windows machines. If you are in this minority and don't mind a small amount of hacking, read on.

GDS Plus allows Google Desktop Search to search text files. Use this GDSPlus.conf where I've added the "tex" and "bib" extensions and your LaTeX and BibTex files will be indexed and searchable. A great benefit for those of us who can't keep track of which theorems and definitions we put in which papers.