On Language

Language has never been my strong suit. I didn't speak full sentences until I was five. I had a 220 point spread between my verbal and math SAT scores. I fumbled through three years of high school French (which required some summer school). This knowledge of French was only useful a couple of times. Wandering the streets of Paris, a women asked me Quelle heure est-il? and I knew enough to show her my watch but enough to actually tell her the time. Also I saw Secrets & Lies in France and sometimes the French subtitles made more sense than the heavily accented English.

During my undergraduate years at Cornell I struggled and gave up on Spanish. Luckily a linguistics professor had a theory that people who had trouble learning English early (like me) would have too much difficulty in picking up a new language, so I could take an intro linguistics course to cover my language requirement. Pretty cool as we covered context-free languages simultaneously in linguistics and in my introduction to theoretical computer science class.

In graduate school my three years of high school French got me out of the Ph.D. language requirement. If English was not the lingua franca of our field, I would be in serious trouble. I've always been impressed how many non-native speakers of English have succeeded in computer science.

I spent an entire year on sabbatical in Amsterdam but only learned enough Dutch to navigate the supermarkets and order in restaurants. Most Dutch speak English (and 3-4 other languages) and my attempts to say most Dutch words usually got responses in English. Still I definitely missed something as when I left a conversation the language shifted to Dutch and I couldn't get back in.

Suppose I could retroactively master a single foreign language, what language should it be? At times I would have liked to know Dutch, German, Hebrew, Japanese and the occasional French, Spanish, Danish, Italian and Portuguese. In the future I suspect I would visit countries speaking Hungarian, Russian, Chinese, Swedish and many others. I've gotten very good at navigating in countries where I don't know the language. In most European countries I can pass as a local as long as I keep my mouth shut.

The University of Chicago has a rather strict TOEFL requirement that would likely have caused a problem for me had I grown up in say Germany. Our department also has a small foreign language requirement for the Ph.D. Foreign language requirements made sense in a different era when papers were written in many languages. I remember a scene in graduate school where my advisor Mike Sipser and some Russian speaking students poured over the latest paper by Razborov translating from the Russian and hoping to understand Razborov's next great result. But now with nearly all papers written in English the requirement seems like a relic from a bygone time. Perhaps we should require every student to take the test in French, for France still has a few researchers stubborn enough to keep writing in their native tongue.

Conference Presentations

The quality of conference presentations have, on average, much improved over the past decade or two. Why? Certainly technological improvements like PowerPoint and advanced LaTeX macros have helped. As our field gets more specialized, talks in general theory conferences have to appeal to a wider audience which tend to improve the presentation. Or perhaps I'm just remembering only the bad talks from the good old days.

Despite the increase in quality, I find myself going to fewer and fewer talks in general theory conferences. I learn much more talking directly to my fellow computer scientists. As for the presentations, I can read the papers later.

A fellow computer scientist suggested that we hire a company to videotape the talks and make them available on the web. A back of the envelope calculation suggested we could make this happen for about $10 extra per participant for a reasonably sized conference. I am not a fan of making talks available on the web. Outside of a conference, who has time to sit at a computer screen and watch talks. I also worry about giving people yet another reason not to go to a conference. Remember the most important aspect of a scientific conference are not the talks and papers but bringing members of the community together.

Newspaper Odds

My cell phone received a breaking new alert yesterday: The FDA is investigating a link between the impotence drug Viagra and blindness. The story also made the front page of today's Chicago Tribune. Look carefully though and you'll notice 38 reports of blindness among the 23 million Viagra users. Even if the drug directly caused the blindness the numbers translate to a 0.00017% chance of losing your sight using Viagra. Breaking news indeed. You have a much greater chance losing your sight not using safety goggles in the workplace and not have as much fun in the process.

This is an example of what I call newspaper odds. If some people's misfortune appears in the newspapers then the odds are so low that you really shouldn't worry about it. High school mass shootings. Mad Cow Disease. Carbon Monoxide Deaths. No significant need to worry about these.

When deaths become too common to appear in a newspaper then you need to take notice and act carefully, say with automobile accidents or AIDS. Of course a cause of death might not appear in a newspaper simply because it doesn't happen, like recent US major commercial airline disasters. How to we tell the difference: celebrities. If a celebrity dies of AIDS or gets seriously injured in an automobile accidents, newspapers will cover it and remind us that these remain serious concerns for us all.

CCC 2005

Ravi Kumar and D. Sivakumar, the local organizers of the upcoming Conference on Computational Complexity in San Jose, ask that I post the following. I hope to see you all there.

The early registration deadline for Complexity 2005 is 5 pm EDT on FRIDAY, MAY 27, 2005 (Eastern Daylight Time == 4 hrs behind Coordinated Universal Time (UTC/GMT)). Please take special note of the time: though the conference is on the Pacific Coast, early registration ends 5pm Eastern Time.

When you register for the conference, if you are not an IEEE Member but a SIGACT/EATCS Member, please enter that number (e.g., SIGACT xxxxx) to qualify for the discounted rate.

Please consider staying at the Conference hotel, Hyatt Sainte Claire; besides being convenient, it will help limit the conference expenses.

In San Jose and around the Silicon Valley, you will experience a unique combination of cultures and cuisines (American, Asian, European, Mexican) like nowhere else. There is a large number of restaurants, coffee shops, and bars within walking distance from the conference venue; these include highly-rated upscale restaurants as well as hole-in-the-wall type places that serve authentic food from around the world. For example, you could even get falafels that pass Ziv Bar-Yossef's stringent standards, and South Indian food certified by your local organizers as the best outside of Chennai. If you're one of those poor souls that happen to be vegetarian/vegan at a theory conference, relax -- there's Good Karma, White Lotus, and Vegetarian House within walking distance.

During mid-June, San Jose is an absolutely pleasant place to be, with daytime highs close to 80 degrees Fahrenheit (about 27 degrees Celsius), and night time lows near 55 degrees Fahrenheit (about 13 degrees Celsius). Downtown San Jose, where the conference will be located, has numerous interesting places: the Cesar Chavez Plaza and the Tech Museum of Innovation are right across from the hotel. The Center for the Performing Arts (CPA), the San Jose Repertory Theatre, the San Jose Museum of Art, San Jose State University, as well as the light rail station, are all within walking distance. CalTrain station (to go to San Francisco) is only about a mile away. The Repertory features Exceptions to Gravity by Avner Eisenberg during some of the conference days. CPA has the Festival of Cultures by the SJ Jazz Society, and an American Musical Theatre show during some of the conference days (see here). The Museum of Art (no entry fee!) has the Blobjects and Beyond : The New Fluidity in Design exhibit during all of June. The Tech Museum of Innovation is a one-of-its-kind museum that you should absolutely not miss when you're in town; during June, the IMAX theater there features a limited-screening edition of BATMAN, plus the Mysteries of the Nile -- be sure to check it out. If you're bringing children along, they will definitely enjoy the Children's Discovery Museum, within walking distance of the conference. Unfortunately, Major League Soccer's San Jose Earthquakes are playing Chivas USA on the road in Los Angeles.

Complexity and Sudoku

A Chicago undergrad Amanda Redlich gave a presentation and used the shorthand ity (Complex-ity). Clever. Of course this should never be confused with ity.

Today's Chicago Tribune has an AP article on the British craze of a Japanese number game Sudoku. In this puzzle you have a 9x9 grid subdivided into 9 3x3 grids. The goal is to fill the full grid with numbers 1 through 9 such that each number appears exactly once on each row, column and subgrid given some initial partial setting.

As a computational complexity theorist, I immediately wondered how hard is the generalized game on an n²xn² grid. A little googling shows the problem is NP-complete, shown in a 2003 Master's thesis of Takayuki Yato at the University of Tokyo. His proof uses a simple reduction from the Latin Squares problem proved NP-complete by Charles Colbourn.

STOC Business Meeting Redux and More

My liveblogging experiment didn't quite work as planned. I seemed to have lost half of what I wrote and then my battery died. So here is some basic info from the meeting.

• Most of the discussion was on theory funding and on the STOC republication policy and most of those discussions survived from yesterday. Check out the new Theory Matters site advocating increased theory funding.
• The Gödel Prize went to Noga Alon, Yossi Matias and Mario Szegedy for their paper The space complexity of approximating the frequency moments.
• Omer Reingold and Vladimir Trifonov won the best paper and best student paper awards respectively for their algorithms for undirected connectivity.
• Future Conferences: Complexity 2005 in San Jose, California June 12-15. Early registration deadline is Friday. FOCS 2005 in Pittsburg October 23-25, STOC 2006 in Seattle May 20-23, Complexity 2006 in Prague July 16-20, STOC 2007 and Complexity 2007 as part of FCRC in San Diego June 9-16 and STOC 2008 will be in Victoria.
• Check out the poster of the NP-completeness and the new DIMACS Implementation Challenge.

The conference had several good surveys commemorating Larry Stockmeyer who passed away last summer. Stockmeyer's advisor Albert Meyer gave a talk describing how they worked together and giving an interesting small result in Stockmeyer's thesis that certain sets created through diagonalization have i.o.-speedup. I also posted the slides and paper from my Stockmeyer lecture.

Complexity theory is well represented in this year's conference with some very nice papers in extractors, derandomization, PCP construction, hardness amplification and much more. Check out the program to see more.

On Friday and Saturday nights, the STOC hotel hosted proms from local schools. It's easier to explain baseball to non-Americans than the concept of a prom where high school students wear fancy clothes and spend large amounts of money for a single party.

STOC Business Meeting

10:45 PM: Hal Gabow on STOC republication policy. When can one submit to STOC when similar paper appeared in previous conference. Current policy does not allow simultaneous submission of the same (or essentially the same) abstract material to another conference with a published proceedings. Should this be more precise? Who enforces the policy? Should the policy be changed?
SIGPLAN policy allows republication if additional value of its publication beyond that of the original paper.

9:57 PM: Michael Foster, Director of CCF at NSF
Proposal tripled over last five years. CISE budget won't change much in next few years.
What's Theory For: Hard foundational questions, linkages between disparate fields; incubator.
Expect theory researchers to do theory but also work in other areas.
Theory Program: Maintain strong supporters in complexity. Narrow systems-theory gap in algorithms and consider applied theory co-funded with other groups.
Looking for theory program director and senior advisor to Peter Freeman (head of CISE).
Questions: How is funding allocated in NSF? Need to show theory necessary to advance well-being of the country. Resist urge to take money away from other ares. Avoid entitlement arguments.

9:37 PM: Andy Bernat from CRA.
CRA focuses on increasing funding and helping researchers with their careers.
DARPA cuts in basic research funding, more than half (>$100M) in last four years. Those researchers are now turing to the NSF.
At recent Future of Computer Science hearing of House Science Committee DARPA argued it funding the computer science that needs funding. Committee charges CS community to come up with a list of areas in CS that need funding. Several workshops planned to address this including summit to be organized by Bill Wolf.
What we can do: Become program director, division director, and assistant directors at NSF. Push on advisory committees, participate in CRA and talk to our legislators. Read CRA Blog.

9:10 PM: Discussion on Theory Funding chaired by Sanjeev Arora.
Some background here and a new Theory Matters website.
Theory claims smaller part of full NSF budget in CS. But also general funding crisis is in funding crisis. Tension between "Core CS" and "Applications of CS"
TCS's greatest strength: Unexpected Payoffs: NP-completeness led to crypto to zero-knowledge to interactive proofs and PCP to coding theory as well as boosting.
More in Advocacy Document.

8:58 PM: Laszlo Babai
G�del Prize: Noga Alon, Yossi Matias and Mario Szegedy for their paper On the space complexity of approximating the frequency moments.

8:52 PM: Andy Bernat from CRA
Outstanding Undergraduate Award: Male Winner Mihai Patrascu (MIT). The female winner, Andrea Grimes (Northeastern) was awarded at the Computer-Human Interaction conference.

8:36 PM: Program Chair Report:
Best Paper: Omer Reingold, Best Student Paper: Vladimir Trifonov, for their low space algorithms for undirected connectivity.
84 accepted papers out of 290 Submitted
33 out of 80 (41%) in complexity.
31 of 128 (24%) in algorithms.
20 of 82 (24%) in "alternative models."
Submissions from 23 countries. Israel most after US.

8:22 PM EST: Local Arrangements Report:
256 Participants including 108 students.
Total Income and expenses each about $97K.

No beer!

I'm liveblogging the business meeting. Keep it here.

Welcome Summer

Most US universities have ended their academic year and moved into the summer season. I like summer not so much for the weather (it gets hot and muggy in Chicago) but for a relaxed research atmosphere. Less courses and more importantly virtually no faculty meetings of any kind give us the time to put some concentrated effort into research.

Summer is also the conference season. We have conferences and workshops year round but many organizers like to have their conferences in the summer when they won't conflict with courses. Instead we have conferences conflicting with each other. Be careful that you don't want to go to too many conferences as they cut into your the summer relaxed research atmosphere.

I plan to attend at least two conferences this summer, STOC, which starts this weekend in the beautiful suburbs of Baltimore and, of course, the Conference on Computational Complexity next month in San Jose. Stop by and say hi if you are there.

It's not summer yet in Chicago. We run in quarters at the University of Chicago and have two more weeks of classes followed by finals week. I can go to STOC missing only one day of classes but there were some conferences and workshops later on I will have to skip for finals week and graduation.

We get our revenge in the fall where most universities start at the beginning of September or earlier and our classes don't start until the last week of September. We hardly see any conferences scheduled in September, particularly in the US, because it is the beginning of most universities semesters. So I use September to visit faculty at other schools. We used to take vacations in September (crowds are smaller everywhere) but now the kids have school starting in late August making our effective summer quite short.

A Long Time Ago in a City 800 Miles Away

I was 13 when I went to see the first Star Wars movie on opening weekend in 1977 in New York City when it was just called "Star Wars" without a subtitle or episode number. Theater staff handed out buttons saying "May the Force be with you." We had no idea what that meant. We then entered the theater and saw a great movie.

That first movie remains my favorite of the Star Wars series to date, with the movie's single tight finale and the "Force" more mysterious than real. Special effects in movies have gotten so good that they can no longer wow you like they could back then.

In the early 90's a Chicago professor gave a welcome lecture to the incoming freshman and ended by saying "May the Force be with you". Most of the students had no idea what he was talking about. I felt old that day.

As the final Star Wars chapter officially opens in the US today, my oldest daughter is only three years younger than I was when the first movie arrived. The movie has gotten good reviews and I look forward to reliving my youth, being with the Force and traveling one last time to that galaxy far far away.

George Dantzig 1914-2005

George Dantzig passed away last Friday. In the 1940s Dantzig invented linear programming and developed the simplex method for solving LP.

Simplex works well in practice but it remains open whether simplex runs in polynomial time for worst-case inputs (though see this paper by Spielman and Teng). Dantzig's death comes just two weeks after the passing of Leonid Khachiyan who had the first provably efficient algorithm for linear programming three decades after Dantzig developed the simplex method. Khachiyan's ellipsoid algorithm is not at all practical as compared with the simplex method.

Crisis in Theory Funding

Guest Post by Boaz Barak

The National Science Foundation (NSF) has a program called "Theory of Computing" which is the only program devoted to funding research in theoretical computer science. We use here "Theoretical Computer Science" in a broad sense, which includes research in Algorithms, Computational Complexity, Cryptography, Computational Learning, Network algorithms, etc. (Of course theoreticians can and do also apply to more application-oriented programs such as cybertrust and others)

Although the ToC program never had a large budget, looking at the projects and people it funded throughout its history, we can safely say that it had a huge impact much beyond the boundaries of TCS and even beyond the boundaries of Computer Science at large. Indeed, much of the initial research on field-transforming concepts like Quantum Computing, Boosting of learning algorithms, Cryptographic Protocols, Interactive Proofs, and more was supported by this program.

Unfortunately, the budget of ToC program has been more or less stagnant at approximately $7M per year since 1989 (in dollars without adjusting for inflation the ToC budget was $6.4M in 1989, $5.1M in 2004, and will be $7.2M in 2005). Needless to say, in these 15 years the costs of research (such as faculty salaries, student stipends etc.) grew even beyond the global rate of inflation. Also the overall CS budget at NSF tripled during this time. Thus the ToC program budget that was merely insufficient in 1990 and dangerously insufficient in 1999 is now at what can only be described as a crisis level. This is a situation that must be corrected if we wish our field to continue to thrive. Given TCS's achievements in the last few decades and challenges for the future, this should concern not only theoretical computer scientists.

What can we, TCS faculty in the U.S., do to fix this?

1. First of all, educate ourselves about the funding situation and ways to solve it. If you can, please come to the business meeting at the upcoming STOC, where these issues will be discussed.
2. We need to participate more in the NSF, this includes reviewing proposals, participating in panels, and volunteering for positions. NSF administrators are actually quite appreciative and supportive of theory, but the situation will not change without active community involvement. In particular, please consider volunteering for the position of director of the ToC program.
3. We need to educate others about what we do. This includes bright math-inclined high school kids who could potentially become TCS researchers, educated adults (including also other scientists), and also other computer scientists. We need more popular science books, general audience lectures, essays and op-eds.

Pitfalls of the Tenure System

In my last post you can find some links and comments about the tenure system. Let me add a few concerns that don't often get mentioned.

• Tenure keeps academic salaries low: Tenure has a definite monetary value as when combined with life and disability insurance removes nearly all risk of future income. A university can then shave the salary in comparison to other lines of work. I suspect the shaving is high in the humanities where positions outside academia has a higher risk of long-term under or un-employment.
• Tenure allows universities to age discriminate: Because hiring with tenure requires a large long-term commitment, departments have to hold candidates for open tenured positions to a much higher standard than for open assistant professor positions. Often departments will only consider candidates for the assistant professor position. Without tenure, US law would prevent holding candidates to different standards because of age for basically the same position.
• Tenure Jail: Since most jobs in the US are not secure, one can change careers midstream without entailing much additional risk. Many tenured professors would be reluctant to leave their risk-free position for another career, even if that other opportunity would make them happier and possibly more successful.

A Day of Links

The US House Committee on Science held a hearing yesterday on The Future of Computer Science Research in the U.S. You can watch the webcast or read the testimony. The CRA Blog also has it covered.

Thomas Friedman's column today talks about how the US no longer dominates the ACM programming contest.

A couple of links about tenure. An Inside Higher Ed article on the strange policies for tenure decisions (thanks Jeff) and a Chicago Tribune op-ed piece arguing against tenure altogether.

Temporal Theory

One of our gradate students wanted to define a property P of classes C to hold if we don't know that C has complete sets. Doing so would make the concept time dependent. IP would have property P in 1989 but not in 1991 after we knew IP=PSPACE. One can easily show "If P=BPP then BPP has complete sets" but we don't have "If P=BPP then BPP has property P" rather we would have to say "If we know P=BPP then BPP has property P." Location can also be an issue. If the Martians have a proof that P=BPP then BPP has property P on Mars but not on Earth. Temporal Logic might give us a way to reason about such statements but basing them on unknown mathematical facts seems strange.

Suppose someone proves the polynomial-time hierarchy collapses. Then it didn't collapse because it was always collapsed and in fact was never a true hierarchy. The only reason we call it a hierarchy today is because we don't know that it isn't.

In mathematical reasoning we can't know whether a statement is true unless we have a proof of that statement. However once we have a proof of a theorem like P≠NP then not only do we have P≠NP now but in fact P≠NP was always true even before we had the proof. Despite this we can't help thinking that theorems become true as we see a proof. A year ago undirected connectivity wasn't in log space and now it is. However the theorems that were proven before I started graduate school were all true since the dawn of time.

Complexity of Computer Computations

Deep into the bowels of the Physical Sciences Library I went to retrieve the Proceedings of a Symposium on the Complexity of Computer Computation to track down Karp's famous paper for my last post. Later I discovered one of my fellow Chicago professors, Janos Simon, attended that conference as a young grad student and still had the proceeding in his office.

The symposium held March 20-22, 1972 at IBM Yorktown marked a shift in theoretical computer science towards more algorithms and complexity from logic, automata and grammars. The symposium attracted 225 registrants on par with our current STOC and FOCS conferences. From the preface:

The symposium dealt with complexity studies closely related to how computations were actually performed on computers. Although this area of study has not yet found an appropriate or generally accepted name, the area is recognized by a significant commonality in problems, approaches, and motivations. The area can be described and delineated by examples such as the following.

1. Determining lower bounds on the number of operations or steps required for computational solutions of specific problems such as matrix and polynomial calculations, sorting and other combinatorial problems, iterative computations, solving equations, and computer resource allocation.
2. Developing improved algorithms for the solution of such problems which provide good upper bounds on the number of required operations, along with experimental and theoretical evidence concerning the efficiency and numerical accuracy of those algorithms.
3. Studying the effects on the efficiency of computation brought about by variations in sequencing and the introduction of parallelism.
4. Studying the relative complexity of classes of problems with respect to lower bounds on computation time. In this effort, specific problems are classified as having equivalent difficulty of computation; for example, those problem which can be solved in a number of operations which is a polynomial function of the size of the input.

The symposium had a panel discussion on the state of the field, with a panel that included four future Turing Award winners: Robert Floyd, John Hopcroft, Richard Karp and Michael Rabin. The proceedings has a transcription of the panel session. Here are some edited quotes.

Ray Miller (Moderator): There are four general questions.

1. How is the theory developing from originally being a scattering of a few results on lower bounds and some algorithms into a more unified theory?
2. What specific examples have been found to demonstrate how real computer computations were improved from studies of this type?
3. Is the progress of numerical-type computations and understanding of them much ahead of the combinatorial?
4. Are there important open questions?

Floyd responding to the first question: Slowly.

Karp: We need a to find a name for our subject. "Computational Complexity" is too broad in view of the work of Blum and others, at least until we can gather them into our fold; "Concrete Computational Complexity" is too much like civil engineering; "Complexity of Computer Computations" doesn't ring true; Markov has already taken "theory of algorithms" away from us…Getting these materials into university curricula, particularly the undergraduate curriculum, is important and it's going to happen quickly.

There are lots of things that computer people do that aren't mathematical in the nineteenth century sense. We manipulate strings, we prove theorems, we retrieve information, we manipulate algebraic formulas. Looking at the primitives appropriate to these domains, we can get a much richer class of problems.

Charles Fiduccia: Working against unification is the failure of specifying a model for the computation. There seems to be too much emphasis on what is being computed and little emphasis on the model.

Hopcroft (responding to Floyd): You could change "slowly" to "it's not". Karp has shown many of these problems complete, the implication being that therefore these problems are hard. That might not be the case, they could even be algorithms that run in linear time. On the other hand, the fact that we know so little about lower bounds provides a lot of interest in the area.

Albert Meyer: The obstacle is not that we don't have a good formulation of a machine model. We have many different models, but we can't prove lower bounds for any of them.

Mike Patterson: Suppose somebody were to prove P≠NP then this would be of great personal and dramatic interest. But if it were to be established by a quite traditional, ordinary argument, which is just happened that nobody had thought of, then we would see in retrospect that it was the wrong problem.

Numerical and combinatorial algorithmic people, with some small exceptions, never did integrate well. But Blum and the computational complexity people did come "into the fold" and algorithms and complexity would come to dominate theoretical computer science in the US. The naming issue never did have a satisfactory solution, the Europeans call it Theory A. And I would be very happy with a "traditional ordinary" proof of P≠NP but I strongly doubt the solution is so simple.

As a side note, had I been able to find Karp's paper online I would never have read about this symposium that marked the new direction of theoretical computer science research.

Favorite Theorems: Combinatorial NP-Complete Problems

April Edition

If Cook made the P versus NP question interesting to logicians, Karp made the question important to everyone else.

Richard Karp, Reducibility Among Combinatorial Problems, Proceedings of a Symposium on the Complexity of Computer Computations, 1972.

All the general methods presently known for computing the chromatic number of a graph, deciding whether a graph has a Hamiltonian circuit, or solving a system of linear inequalities in which the variables are constrained to be 0 or 1, require a combinatorial search for which the worst case time requirement grows exponentially with the length of the input. In this paper we give theorems which strongly suggest, but do not imply, that these problems, as well as many others, will remain intractable perpetually.

Karp's paper used Cook's Theorem that satisfiability was NP-complete to prove 21 other problems NP-complete, including Clique, Integer Programming, Hamiltonian Cycle, Chromatic Number, Partition and Max Cut. Many of these problems arise from real-world optimization problems and Karp showed that if any of them have efficient algorithms then they all do. Researchers would later extend Karp's techniques to show hundreds if not thousands of natural problems are NP-complete.

Karp's paper named the classes P and NP and defined the notion of reduction (now often called Karp Reduction) where a language A reduces to a language B if there is a polynomial-time function f such that x∈A iff f(x)∈B. He defined a notion "polynomial complete" as the set of problems A in NP that every other NP-problem reduces to A, a notion we now call NP-complete. Karp also makes the argument that the definitions are robust to different reasonable encodings of the problem and different models of Turing machines.

Karp also alludes to the polynomial-time hierarchy.

If P=NP then NP is closed under complementation and polynomial-bounded existential quantification. Hence it is also closed under polynomial-bounded universal quantification. It follows that a polynomial-bounded analogue of Kleene's Arithmetic Hierarchy becomes trivial if P=NP.

Karp lists three NP problems whose classification was open at the time.

• LINEAR INEQUALITIES: Basically Linear Programming, shown to be in P in 1979 by the recently departed Khachiyan.
• NONPRIMES: Shown to be in P in 2002 by Agrawal, Kayal and Saxena.
• GRAPH ISOMORPHISM: Not known to be in P but if GI is NP-complete then the polynomial-time hierarchy collapses which was shown in 1987 by combining results of Goldreich-Micali-Wigderson, Goldwasser-Sipser and Boppana-Håstad-Zachos.

Ranking CS Departments

A few years ago, one ranking listed Harvard as the number one engineering school. The schools were ranked by average starting salary of their graduates and both of Harvard's engineering students that year got good jobs.

I could do several posts on rankings but let us focus on rankings of Ph.D. programs in computer science. One cannot give a linear ordering of departments: One department might have a strong theory group and another strength in systems. Even within theory, one department could have strong algorithms while another group has strong complexity. Even then one's graduate experience depends more on their individual advisor than the department as a whole.

Nevertheless Americans like statistics and ordering things including CS departments. There are two major rankings of Ph.D. programs: The US News and World Report ranking last updated in 2002 and uses a methodology of giving questionnaires to department chairs and directors of graduate study. The NRC ranking looks at a slew of different statistics but hasn't been updated since 1993. I hear rumors that the NRC will do a new ranking soon.

The US News ranking captures perception of strength instead of strength itself, often based one's opinion of a department from a few years back. On the other hand, the purpose of rankings are perception as we wish to be perceived as a strong department. We all complain about the rankings but they affect us greatly, in recruiting students (Americans especially use the rankings to choose a Ph.D. program) and recruiting faculty. When hiring faculty we often rightly or wrongly give extra weight to Ph.D.s from higher-ranked departments. Deans and provosts use the rankings to allocate resources as higher rankings lead to more prestige for the university as well.

For example, if a mid-level department wishes to have the strongest quality faculty they should hire mostly in one area, as people like to join groups with people they know, respect and can work with. But this approach won't help much in the rankings so most departments try for a broad faculty with likely lower overall quality but a better ranking.

At least forty departments have a stated goal of being a top-ten department. The pigeonhole principle guarantees many won't end up happy.

An Endless Frontier Postponed

Science has a special issue on Distributed High Performance Computing including an article Service-Oriented Science by Chicago's own Ian Foster. The must read is an editorial An Endless Frontier Postponed by Ed Lazowska and Dave Patterson.

At a time when global competitors are gaining the capacity and commitment to challenge U.S. high-tech leadership, this changed landscape threatens to derail the extraordinarily productive interplay of academia, government, and industry in IT. Given the importance of IT in enabling the new economy and in opening new areas of scientific discovery, we simply cannot afford to cede leadership. Where will the next generation of groundbreaking innovations in IT arise? Where will the Turing Awardees 30 years hence reside? Given current trends, the answers to both questions will likely be, "not in the United States."

Also from the CRA:

The timing of the issue also couldn't be better, given that the House Science Committee will hold a full committee hearing on "The Future of Computer Science Research in the U.S." on Thursday, May 12th. You can watch it live on the Science Committee's real-time webcast (also archived).

Postdocs

While other fields have standardized postdoc programs, computer science still searches for the right approach for postdocs. While we have had postdoc positions since I can remember, quite often researchers have gone straight from Ph.D. to tenure-track positions particularly in times of high growth in CS departments (early-mid 80s and mid-late 90s).

We are now seeing a spike in the demand for postdoc positions for several reasons.

• A tightening job market means less tenure-track jobs so more people opt to do postdocs to build up their CVs. Several researchers are even taking second and third postdocs, not long ago a rarity in CS.
• Many students opt to delay a tenure-track position for a year and do a postdoc first. The commitment goes both ways, if a department is holding a position for a student then that student is committing to going to that department. It's not fair to go back on the job market during that postdoc year. Some departments are becoming more reluctant to allow the year delay because of bad experiences with students not fulfilling that commitment.
• More and more students attend graduate school in their home countries and hope to eventually return to permanent jobs in those countries but take postdoc positions elsewhere to get a broader view of the field.

Alas we don't have an increase in postdoc supply to go along with this demand. Many of the industrial research labs have shrunk and hire few or no postdocs. Meanwhile most US academic departments have no permanent postdoc programs and CS grants are rarely large enough to cover the cost of a postdoc (as opposed to Canadian and European groups which tend to have more postdocs). Just another way the US is losing strong researchers to other countries.

Dilemmas of Prisoners and Professors

Some interesting game theory and philosophy from the last couple of NUMB3RS episodes. Usual spoiler warnings.

In the April 22nd episode Dirty Bomb there were three suspects who wouldn't talk. Charlie, the mathematician, likened the situation to Prisoner's Dilemma and suggested putting the suspects in the same room, which is usually the wrong thing to do in prisoner's dilemma. What Charlie did was compute the utility for each suspect cooperating (with each other and not the FBI) based on family considerations and their previous record and convinced the one with the most to lose by cooperating to defect and talk to the FBI. Clever, but I really wonder if that would work in real life.

Last Friday's episode Sacrifice took a more philosophical direction. A murdered think-tank computer scientist was developing a program that measured academic potential based on where someone grew up, down to a city block. If such a program actually worked, how should a program be used, if at all? How far should one go to stop the project?

Charlie and his physicist friend Larry ruminated on whether scientists are responsible for how their research gets used, as well as a discussion on the lonely life of a scientist at a lightly attended memorial service for the murder victim. The episode also had a physics joke I don't quite get.

Applied physicists are from Venus; Theoretical physicists wonder why it spins in the other direction.

I really enjoy those discussions between Charlie and Larry because they ask some interesting questions and add some dimension to a public view of mathematicians and scientists.

Leonid Khachiyan (1952-2005)

Leonid Khachiyan passed away Friday at the age of 52. Khachiyan was best known for his 1979 ellipsoid algorithm giving the first polynomial-time algorithm to solve linear programming. While the simplex algorithm solved LP well in practice, Khachiyan gave the first formal proof of an efficient algorithm in the worst case. The ellipsoid algorithm also has applications for more general convex programming questions and can be used for approximating semidefinite programming used for example in the Goemans-Williamson algorithm approximating max-cut.
One of my first exposures to theoretical computer science came in high school when I read a New York Times article describing the algorithm. I later learned that article has become our standard example of bad science writing, focusing more on an unlikely link to NP-complete problems instead of just describing the important theoretical problem Khachiyan's algorithm does solve.

Mr. Khachiyan's method is believed to offer an approach for the linear programming of computers to solve so-called "traveling salesman" problems. Such problems are among the most intractable in all of mathematics…In the past, "traveling salesman" problems, including the efficient scheduling of airline crews or hospital nursing staffs, have been solved on computes using the "simplex method".

New York Times science writing (and science writing in general) has vastly improved since those days.

Read this Weblog, Get a Job

One of the requirements for a software engineering job at Autodesk.

Good knowledge of common algorithms and data structures; understanding of computational complexity

Clemens Lautemann

Some sad news from Thomas Schwentick.

What we have feared during the last weeks and months came true yesterday morning: Clemens Lautemann died at the age of 53 from cancer.

Most recently Lautemann had been working on logical characterizations of complexity classes but I will remember him most for his beautiful proof (or here) that BPP, the class of languages with efficient probabilistical computatins, is in the second level of the polynomial-time hierarchy. In 1983 Sipser had shown BPP in the fourth level, and very soon after Gács and Lautemann independently showed BPP in the second level. Lautemann gave a very simple combinatorial proof that I consider one of the prettiest applications of the probabilistic method to complexity.

The Quality Thesis

Too often Ph.D. theses in computer science consist of not much more than a couple of "papers stapled together." A shame as one can use the thesis to truly bring out the importance of one's research.

There is no serious upper page limit on a thesis and you can truly spend the extra time to make your thesis stand out.

1. Put the results of your earlier papers together in a common framework and add some new results you never bothered writing up. (Harry Buhrman's 1993 thesis has a large collection of results on exponential-time computations that I still often consult.)
2. Take the time to expand the proof of complicated results to the right amount of intuition and depth. (For many years Madhu Sudan's 1992 thesis had the best write-up of the proof of the PCP theorem.)
3. The initial chapters of your thesis can serve as an introduction to a relatively new research area, (Michael Kearns's 1989 thesis gave an early broad overview of computational learning theory.)
4. Or give your own impressions of a more established field (Scott Aaronson's thesis expounds on his views of quantum computing.)

If you are looking for a job you'll be too stressed to do research anyway so why not take the time to write a quality thesis which will get your thesis widely cited and possibly even widely read.

My Mouse and Me

Today is take your daughter (and son) to work day so today's post is written by Annie Fortnow (age 10) on the topic of her choice.

This is a Dell Computer. It has 3 different parts. The first part is the screen. The screen is were you see what you are typing. The next part is the keyboard. The keyboard is the place were you type. The last part is the mouse. It is my favorite part because it helps me to click on the things that I want to click on.

There are many other parts of a Dell Computer. Those are the parts that I recognize the most. But the mouse is my favorite part. The mouse comes in many different shapes and sizes. On a laptop the mouse is either a circle in the middle, a square at the end, or both. On a regular computer the mouse is either an oval, a trackball, or looking like a mouse.

The mouse is a really important part of the computer. I will always keep mine in handy.

The Story of Ribbit

Around 1980 for fun in New Jersey we would go visit the electronic video arcades to play various games like Asteroids, Pac-Man, Tempest, Missile Command and many others. I was not much of a player but I was fascinated by the games themselves and wondering what it was like to program them. Between high school and college in the summer of 1981, a high school friend Chris Eisnaugle and I tried programming up a few games on his Apple II. I remember getting a passable version of Asteroids working in a couple of days.
We talked with a computer magazine writer who said we could legally sell a game based on an arcade game as long as we changed the name and slightly changed the user interface. We focused on the game Frogger which was not yet available for the Apple and created Ribbit written mostly over winter break. That spring we sold the program through a local computer store before we got a cease-and-desist order from Sierra Online, who had bought the personal computer rights to Frogger. So we ceased and desisted but not before 1200 copies of the program got sold. I made about $2000 from the program, not bad for a college freshman in 1982. Also a computer magazine review of Frogger liked our program better!

"Sierra Online's Frogger is even worse than the game named after the sound a frog makes."

In the summer of 1982 I worked as a instructor/counselor at the Original Computer Camp, Inc. in Los Olivos, California, which had a series of two-week sessions. Early in the summer none of the campers had heard about Ribbit but later on quite a few did. Not because of the 1200 legal copies but because pirated versions of the game were widespread. At first I was quite upset at the piracy, even deleting the game from the disks of the campers who had the game with them ("There is no honor among thieves" one such camper complained referring to the fact that we had stolen the idea of the game from Frogger). But soon I realized that we weren't selling any more legal copies anyway and the game lived on through its pirated versions. Still it wasn't long before Ribbit was mostly forgotten. On the webpage I set up for Ribbit I posted a pirated version of the game I found on the web. To get the original version I would have to find the disks buried somewhere in my mother's house and then find a machine that can read floppy disks from a time when disks were floppy.

scIenCE Princess

My daughters saw the movie Ice Princess over the weekend. Based on what they told me here is the basic story: Casey decides to do a science project on figure skating and uses physics and computers to help some skaters improve their routines. Casey's mom is really pushing her to science and sets up an interview for an academic scholarship to Harvard (Note to Hollywood: Ivy League rules prohibit academic scholarships). But Casey falls in love with figure skating and goes against her mother, says no to Harvard and follows her new dream of skating.

I have nothing against "follow your dream" movies and Ice Princess does put science and computers in a good light, at least in the early part of the movie. But just once can't we have a movie where a young woman whose parents want her to be a great figure skater, gymnast or tennis player but instead she follows her dream of becoming a scientist.

Favorite Theorems: NP-Completeness

March Edition

This month we honor the papers that gave us the first NP-complete problems and marked the official beginning of the P versus NP question. The P and NP notation did not originate with these papers but I will use them anyway for clarity.

Steve Cook, The Complexity of Theorem-Proving Procedures, STOC 1971.

Suppose a nondeterministic Turing machine M accepts a set S of strings within time Q(n), where Q(n) is a polynomial. Given an input w for M, we will construct a propositional formula A(w) in conjunctive normal form such that A(w) is satisfiable iff M accepts.

In this paper Cook gives the first formal treatment of the P versus NP problem. He gives several examples of NP problems and notes his notion of NP is equivalent to a class of extended positive rudimentary relations due to James Bennett. He introduces P-reducibility (now often called Cook reductions) where one reduces a problem A to a problem B by solving A using a polynomial-time machine with access to an oracle for B. His main theorems show that Tautology and Subgraph Isomorphism are hard for NP under P-reducibility. The quote above came from the beginning of the proof for Tautology.

The theorems suggest that it is fruitless to search for a polynomial decision procedure for the subgraph problem, since success would bring polynomial decision procedures to many other apparently intractable problems…The theorems suggest that Tautology is a good candidate for a set not in P, and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory.

Indeed.

Leonid Levin, Universal'nyie Perebornyie Zadachi (Universal Search Problems), Problemy Peredachi Informatsii 1973. Translation in appendix of the Trakhtenbrot survey.

If we assume that there exists some (even if artificially formulated) problem of the search type that is unsolvable by simple (in terms of volume of computation) algorithms, then it can be shown that many "classical" search problems have the same property.

Levin claims that any NP problem reduces to any of a list of problems including tautology, subgraph isomorphism, tiling, set cover and a few others. As was the Russian tradition of the times, Levin's paper does not have fully formal definitions or any proofs. Still he has similar results and the same insight as Cook that one can reduce any NP problem to specific natural problems.

All of these problems are solved by trivial algorithms entailing the sequential scanning of all possibilities. The operating time of the algorithms, however, is exponential, and mathematicians nurture the conviction that it is impossible to find simpler algorithms…but not one has yet succeeded in proving it.

In today's world results proven today get transmitted around the world in minutes. But given the technological and even more important the political situation of the 70's, Cook and Levin did not learn of each other's work until years later. Today we give them both credit for taking the P versus NP problem out of the abstract and connecting it to solving natural problems. Now only three decades later the P versus NP problem has become one of the great open questions in all of mathematics.

A Fine Line Between Prank and Fraud

You have probably heard this story by now. Some MIT students created a computer-generated paper accepted to a non-reviewed session of the Systemics, Cybernetics and Informatics conference. I haven't mentioned the story earlier because I didn't want to give the students extra publicity but now that the story has hit the AP wire something needs to be said: What these students did was just plain wrong.

I'm no big fan of the SCI conference but virtually none of the conferences in computer science fully referee their submissions. A clever student could write a paper with a bogus proof and have a chance of that paper being accepted at a major conference like STOC. I would consider someone who intentionally submits a bogus paper to STOC guilty of academic fraud. Why are these MIT students any different?

Students make mistakes and we should tell them what they did was wrong instead of just glorifying such activities.

And The Winner Is …

Haipeng Guo wins the math poetry contest with the poem below. Congratulations and thanks to all that participated.

When a P-man loves an NP-woman

Been a happy deterministic man
With a simple polynomial brain
I contented myself with P problems,
And always looked at NP with disdain.

Fell in love with a polynomial woman,
But with a non-deterministic wit,
She said she would marry me,
Only if I could show her that P=NP.

I rushed to the library and studied,
Asked Garey & Johnson for a hint to the truth,
They said "this is quite a hard question",
But none of them had a hint or a clue.

Went to church and prayed to The Almighty,
"Please Oh Lord, give me a lead the truth",
"Don't waste your time son", a voice said laughing,
For I myself on this wasted my youth.

First oracle says you will marry
Second one tells you you'll split
Time moves, paths branch, results may vary
Accept the state that finally fits

If you finally marry this girl,
And P=NP was true,
What a Chaos: E-banking unsafe, Salesmen traveling cheaply!
And mathematicians with nothing to do!

If I grant your happiness,
The precondition must be no witness,
Even you both did nothing completely wrong,
The punishments will be exponentially long.

If you really want to marry this woman,
Then randomness might be the only key,
But please stop praying for an answer to me,
For I could not decide on this P=NP!

A New PCP Proof

There is some buzz about a new construction of probabilistically checkable proofs by Irit Dinur. The PCP theorem, first proved by Arora, Lund, Motwani, Sudan and Szegedy in the early 90's, states that every language in NP has a proof that can be verified randomly using O(log n) random bits and a constant number of queries. The PCP theorem has had many applications to showing hardness of approximation results and has had many improvements such as Håstad's tight result that I highlighted last year.

The previous proofs used considerable algebraic techniques. Dinur takes a more combinatorial approach using a powering and composition technique (inspired by Reingold and the zig-zag product) to separate the gap in 3SAT without increasing the number of variables.

An upcoming STOC paper by Ben-Sasson and Sudan gives a PCP for SAT of only quasilinear size but requiring polylogarithmic queries to verify the proof. Dinur, by applying her construction to those PCPs, can now create quasilinear-size proofs which only need a constant number of queries for verification.

Discussion Questions

New Balance has been heavily advertising some questions about sports so I'd thought I would give my own discussion questions about academics.

• You've been working hard on a research problem and someone else solves it. Does that make you feel happy or sad?
• Three people in an office. Two of them bounce ideas back and forth to prove a new theorem while the third just tries to keep up. Should the third person be a co-author?
• You are reviewing a paper and see an easy but major improvement to the paper's main result. What do you do?
• Your friend is applying to your university and you see that one of his recommenders wrote a weak letter. Do you tell your friend?
• Your advisor of the opposite sex has two tickets to a concert you really want to see and invites you to join him/her. Would you go?
• You discover a student wrote something strongly negative about a colleague on their weblog. What would you do, if anything?
• Would you still be a scientist if you could do research but all your work had to be published anonymously?

Go forth and discuss.

The Translation Lemma

A simple trick that every complexity theorist should know but, based on some recent conversations, not every complexity theorist does know. Roughly speaking collapses for small resource bounds imply collapses for large resource bounds. Here is the result for NTIME (nondeterministic time) and DTIME (deterministic time) but the proof works for nearly every pair of complexity measures.

Translation Lemma: Let f(n), g(n), h(n) be reasonable (time-constructible) functions with h(n)>n. Then

NTIME(f(n))⊆DTIME(g(n)) implies NTIME(f(h(n)))⊆DTIME(g(h(n))).

The proof uses a technique known as padding. Let L be in NTIME(f(h(n))) via a machine M. Define A by

A = {x01^h(|x|)-|x|-1 | x in L} We can compute whether x01^h(n)-|x|-1 is in A by simulating M(x) which takes nondeterministic time f(h(|x|))=f(m) where m=h(n) is the length of the input. So A is in NTIME(f(m)) and by assumption in DTIME(g(m)).
Now if we want to compute whether x is in L we can use the DTIME(g(m)) algorithm for A on x01^h(n)-|x|-1 taking total time g(h(n)) since the input has size m=h(n). QED

As an immediate consequence we get that if P=NP then E=NE (where E=DTIME(2^O(n))) by letting h(n)=2ⁿ.

The translation lemma works in only one direction. You need h(n)>n, you can't unpad an arbitrary x. It's open whether E=NE implies P=NP for instance.

The lemma has many applications. Here is one example.
Theorem: If P=NP then some language in E does not have subexponential-size circuits.

Proof: In the Σ₄ level of the E-time hierarchy we can compute the lexicographically-first language A that cannot be simulated by any 2^n/2-size circuits. If P=NP then the polynomial-time hierarchy collapse to P. By a version of the translation lemma with h(n)=2ⁿ the polynomial-time hiearchy collapsing to P implies the E-time hierarchy collapses to E. Thus A is in E but A does not have subexponential-size circuits.

A Modest Proposal

A guest post by Michael Mitzenmacher

Lance nicely invited me to expand on my views on the format for conference submissions. Currently, I am on a program committee using the standard theory call:

A submission for a regular presentation must be no longer than 10 pages on letter-size paper using at least 11-point font…additional details may be included in a clearly marked appendix, which will be read at the discretion of the program committee.

We have actually had discussions on whether to reject out of hand papers that use 10 point font or otherwise violate this standard.

The problem is that many, including myself, think that this formatting rule is silly, and so it has been widely ignored or at least painfully abused for many years. I would like to propose a simple and logical alternative: conference submissions should be in the same format (or as near an equivalent as possible) as the final conference version. Many other conferences (such as AAAI and Sigmetrics) use this approach with great success.

The advantages of this approach include:

1. It reduces the work of the authors. Right now, authors have to create entirely distinct submission versions and final versions of conference papers using various formats. Most authors find this a hassle, and this is my main reason for the proposal. I hate writing the same conference paper multiple times just to cope with formatting issues.
2. It gives the reviewer a more accurate picture of the conference paper. Reviewers will have a very good idea of what the paper will look like in the conference proceedings, making it easier to judge. When you're staring at 20+ pages of appendices, it is hard to tell what the final paper will look like.
3. It enhances fairness. Because this is a standard with a clear reasoning behind it -- you cannot have a longer submission than conference paper -- people are more likely both to follow and enforce the rule, avoiding potential unfairness.

I have heard of some disadvantages of this approach. Let me attempt to dispense with them.

1. The format is too hard for the reviewers to read.

   My response: If this is the case, then perhaps the conference paper format itself should be changed -- after all, don't we expect many people to actually read the conference version? If the conference paper is packed tight for other reasons (the publishers charge by the page), then for submissions design as near an equivalent format as possible. If we find 10 double-column 10 point pages with style file A essentially equals 20 single-column 11 point pages with style file B, then clearly state that in the call and ask for the latter. (Luca Trevisan pointed out this is done for the Complexity Conference already.)

2. Appendices are necessary when there are long proofs that won't fit in the paper.

   My response: If the proofs won't fit in the final conference paper, this is something a reviewer should see and know. The program committee can either allow appendices, with the knowledge they won't have room to appear, or allow pointers to more complete versions (TRs, arXiv preprints) that the reviewers can examine if they desire.

3. By having different formats, we force authors to revisit and hopefully improve their paper.

   My response: Nice intentions, but don't people already want to make their published work as good as possible? This seems unnecessary, and not worth the price.

I ask all program committee chairs to please consider this modest proposal.

Paper Pet Peeves

Little things that annoy me in research papers.

• Declarative first sentences of the introduction, like "Analyzing Left-Handed 12-SAT is a key approach to solving the P versus NP question." Just because you say it doesn't make it true.
• "We use novel techniques that might be of independent interest." A double faux pas. You don't get to call your own techniques novel. "Might be of independent interest" is such a meaningless statement.
• Footnotes (and parenthetical statements) which interrupt the flow of the paper. If it's not worth mentioning in the text then don't mention it.
• Using citations as nouns like "[13] using techniques of [6] showed the main result of [4] follows easily from [18]." I hate having to keep flipping to and from the references to read these papers.
• Using the cliché "larger than the number of atoms in the known universe." It's big. We get it.
• Using the word "respectively" which says "I'm going to give you something hard to parse because I'm too lazy to write two sentences."
• Titles with symbols or complexity classes: If you can't describe your research with words you might consider becoming a mathematician.

Does a book exist if nobody reads it?

A recent conversation with a graduate student.

Student: I couldn't find the paper online.
Me: So walk over to the library and get the paper there.
Student: But you can't take those books out and I don't want to spend hours at the library reading the paper.
Me: So make a copy and take it home.
Student: The library has copy machines?

Here is where I tell the story that when I was a graduate student and wanted a paper I walked five miles barefoot in blizzard conditions (actually two flights of stairs) to the library, or would send a stamped self-addressed envelope to an author. Not that we should go back to those times but don't ignore papers just because you can't find them online.

The next generation gets even worse. From a discussion in an undergrad class.

Student: I searched really hard for this topic and didn't find much. Are you sure it even exists outside of class?
Me: Really, I'm sure the math library [right down the hall] has several books on the topic.
Student: Oh, I just used Google.

Are we really getting to the point that if something isn't on the internet (or even on the internet but Google doesn't find it) then it doesn't exist?

The Battle of Grantsburg

From FYI:

Challenges to the teaching of evolution in public schools across the country have prompted National Academy of Sciences President Bruce Alberts to write to all members of the Academy. Warning of "a growing threat to the teaching of science," Alberts calls on Academy members, if such a controversy arises in their state or school district, to take actions against "attempts to limit the teaching of evolution or to introduce non-scientific `alternatives' into science courses and curricula."

Let me take you to the trenches in such a school district, Grantsburg, a small town in northwestern Wisconsin.

A good college friend of mine who grew up in suburban Connecticut, after finishing medical school and residency took a family practice position in Grantsburg. He got married, had kids and grew to like the rural life. But recently he got involved in a nasty battle with the school board.

The board last fall, after viewing an anti-evolution movie, had authorized teachers to teach "alternate theories of evolution" in the science curriculum. Last December, the board under some pressure changed the policy

Students are expected to analyze, review and critique scientific explanations, including hypotheses and theories, as to their strengths and weaknesses, using scientific evidence and information. Students shall be able to explain the scientific strengths and weaknesses of evolutionary theory.

Not much of an improvement. So the opposers brought in local professors to discuss the importance of evolution but this failed to sway the board.

So finally they tried to replace the board with a slate of science-friendly candidates but just this week they lost that fight as well.

And so my friend, who simply wanted to be a good country doctor, has made some enemies and worries about about the education his kids will receive.

Baseball is Back

A perfect spring day in Chicago and all of my afternoon meetings mysteriously canceled so I took visiting Portuguese professor and avid soccer fan Luis Antunes to his first baseball game, the Cleveland Indians against the White Sox.

Luis was sure he would be bored. We got awesome seats behind home plate and I introduced him to the full baseball experience with Polish sausages for lunch and Take me out to the ballgame during the seventh-inning stretch. Luis knew little about baseball but pretty soon he concentrated on every pitch counting balls and strikes. During the game he even said "baseball is not quite as boring as I had feared." The experience became complete when the Sox scored four runs in the bottom of the ninth to win the game.

Yes, baseball is back and all is good in the world.

Math Poetry Contest

From a poster in my building:

What is the longest song?

"ℵ₀ bottles of beer on the wall."

Happy Mathematics Awareness Month!

April is also National Poetry Month. In honor of April I am running my first (and perhaps last) annual math poetry contest. Winner will receive a copy of Complexity of Computations and Proofs (Jan Karjicek, editor), volume 13 of Quaderni di Matematica, Dipartimento di Matematica della Seconda Universitá Napoli, 2004.

Submit your new original poem on a mathematics or theoretical computer science theme in the comments section of this post with your name and/or email. One entry per person. Entries due by 11:59 PM CDT on Monday April 18. A panel of celebrity judges will choose the winning poem based on whatever criteria they deem fit. The decision of the judges are final.

Update: And the winner is…

What happened to the PRAM?

When computational complexity gets accused to having no connection to reality, I bring up the story of the PRAM (Parallel Random Access Machines), a complexity model killed by technology.

Today we think of the class NC in terms of circuits: NC contains the problems solvable in polynomial-size and polylogarithmic-depth circuits. But Nick Pippenger originally defined the class to capture parallel computation: problems solvable on a PRAM with a polynomial number of processors and polylogarithmic time. The PRAM model had several processors that shared a polynomial amount of random-access memory. There were three main variations:

• EREW–Exclusive Read/Exclusive Write: Every memory cell can be read or written only by one processor at a time.
• CREW–Concurrent Read/Exclusive Write: Multiple processors could read a memory cell but only one could write at a time.
• CRCW–Concurrent Read/Concurrent Write: Multiple processors could read and write memory cells. This variation had several subvariations depending on how one handled conflicting writes.

PRAMS got criticized due to the unrealistic nature of immediately addressable shared parallel memory. Areas like VLSI and Parallel Models (like the butterly network) worked to address these concerns. However while algorithmicists worried about the various PRAM models, achieving the better networks only causes a logarithmic factor increase in time and doesn't affect the complexity class NC.

So why don't we think PRAM anymore when we look at NC? Moore's Law. Processors got faster. Much much faster. The ideas of having many many processors each doing a tiny bit of work seems wasteful these days when we can just as cheaply have each processor do a lot of work.

We still see active research in parallel computing and one can speed up many computations using a large number of machines sometimes far away from each other just connected via the internet. But the best one could hope for is perhaps a quadratic improvement, not the exponential improvement that comes from PRAMs.

Another Breakthrough!

Speaking of space complexity, Adam Kalai, Adam Klivans and Rocco Servedio have extended Reingold's result to show that every language in randomized logarithmic space has a deterministic log-space simulation, i.e., RL = L. Cool.

You can find a copy of their paper here.

Sublogarithmic Space

A reader asks

I wanted to ask you something about the Savitch and Immerman-Szelepcsényi theorems that I saw you have in your weblog. In both thorems we have that s(n)≥logn. Why is that?

For any space function s(n), we also need to have a pointer to read every bit of the input and thus we'll have n2^O(s(n)) possible configurations. For s(n)≥log n, we can safely ignore the extra factor of n but for s(n)=o(log n) this causes problems for directly using the proofs of Savitch and Immerman and Szelepcsényi.

Still many researchers have studied sublogarithmic space classes but these results tend to be dependent on the exact machine model and it's tricky to understand what they tell us about general computation.

A Non-Standard Post

Mike O'Donnell tells a story of talk he saw once where the speaker considered the following recursive program: f(n) := output 0 if n = 0; output f(n-1) otherwise. By straightforward induction one can show that for any natural number n, f(n) will halt in a finite number of steps. The speaker argued that if we take n to be a non-standard natural number (which is bigger than all the standard integers) than the program will never halt. Mike O'Donnell counters that it will halt, just in a non-standard number of steps.

Suppose we could prove P≠NP in the theory of arithmetic. I can create a machine M that solve SAT on standard formula φ using |φ|^k time if k is nonstandard: Since k and thus |φ|^k is greater than every standard integer, we have time to do exhaustive search. However there will be some nonstandard φ that M will fail to solve satisfiability in time |φ|^k time, for whatever the satisfiability question for nonstandard φ means.

Now suppose P=NP in the standard model but P≠NP in some non-standard model (and thus the P versus NP question is independent of the theory of arithmetic). We have a standard machine M and a standard integer k such that M(φ) correct computes whether a standard φ is in SAT in |φ|^k steps. But for some non-standard φ, M(&phi); would fail even though it gets to run in time n^k for the nonstandard n=|φ|. Even if we allow M and k to be non-standard there will be some φ that M will fail to determine satsifiability.

You can keep playing this game and never get into trouble assuming the theory of arithmetic is consistent. But I get a headache when I try to think what non-standard Turing maching, non-standard polynomial running time and satisfiability of non-standard formula really mean.

Getting an Edge

Using performance-enhancing drugs has become a major issue in national and international sports, most recently in Major League Baseball in America where many major players have admitted (or refused to deny) using steroids to increase their power.

What about in academics? Supposedly some mathematicians have used amphetamines to get an edge or keep up with younger mathematicians. If we discover that a mathematician used such a performance-enhancing drug to prove a theorem would we take away his credit for that result? No, we wouldn't.

I don't have any direct evidence that any mathematicians or computer scientists actually use any performance-enhancing drugs, other than caffeine of course. Even so I doubt many of us would agree to random drug testing of academics. But then why should professional athletes be held to a different standard than professional academics?

My Brother

I have a brother who worked in the music industry and got us first row tickets to Kool and the Gang. I have a brother who was an entertainment lawyer who appeared on Court TV and a morning show in Trinidad and Tobago. I have a brother who co-founded a popular fantasy sports website commisioner.com which was later bought out by CBS Sportsline. I have a brother who was shown in a bar celebrating the Red Sox during the World Series telecast last fall and a week later pictured in the New York Post with the trophy. I have a brother who created an award winning short film in New York and is now producing a movie in LA.

I have but one brother. Happy Fortieth Matt. Thanks for making my life seem so ordinary.

P=NP and the Arts

A few years ago someone asked Steven Rudich, a complexity theorist at Carnegie-Mellon, why he thought P is different than NP. He replied "I can recognize great music but I can't create great music," the implication being that it's much harder to find a solution than to verify one.

But suppose NP-complete problems do have very efficient algorithms. Can we use them to create art, perhaps, as someone recently suggested to me, create a new Mozart opera, Shakespeare play or finish Schubert's symphony?

Perhaps we could use P=NP to find a small circuit that outputs "Shakespeare" plays. But these plays will only extrapolate from his known works. The program cannot add the new creative ideas Shakespeare puts in his works. It cannot create art just generate similar pieces.

Of course this whole exercise is moot since we strongly believe that NP-complete problems are hard. Even so a P=NP fantasyland might put some mathematicians and computer scientists out of work but true artists will still create in ways computers can never match.

Complexity LaTeX Package

From Chris Bourke: I've created a LaTeX package for typesetting complexity commands ($\P$, $\NP$, etc). Its available on CTAN. Not only does it define commands for classes (and languages, functions) but with just an option call to the package, you can specify the font all the classes are typeset in. I welcome feedback.

Tape Reduction

Given a k-tape Turing machine can we reduce the number of tapes without too large an increase in time and space (memory)? Not just an esoteric question, tape reduction plays an important role in time and space hierarchies and creating efficient reductions.

For space we have an easy result: Every k-tape s(n)-space bounded Turing machine can be simulated by a 1-tape machine in O(s(n)) space. Create a single supertape with separate "tracks" for each of the original tapes and add markers for the locations of the heads on each of these tapes.

For deterministic and nondeterministic time, this constructions yields a t²(n)-time 1-tape simulation of a k-tape t(n)-time machine and this is the best you can do (consider { x#x | x∈Σ^*}). We can do much better if we reduce k tapes to 2 tapes.

We can simulate any nondeterministic t(n)-time k-tape machine in nondeterministic O(t(n)) time on a 2-tape machine. Roughly the simulation guesses every step of the transition function on one tape and uses the other tape to verify the transition function on each tape of the original machine one tape at a time.

For deterministic time we can only achieve a weaker result: Every t(n)-time k-tape machine has a 2-tape simulation using O(t(n)log t(n)) time. The proof (due to Hennie and Stearns) is quite involved and I won't give it here. The proof has a nice side effect: The construction creates an oblivious machine where the head movements depend only on the input length. One can use this fact to show that we can simulate any t(n)-time Turing machines with O(t(n)log t(n))-size bounded fan-in circuits and reduce any t(n)-time nondeterministic computation to satisfiability questions of size O(t(n)log t(n)).

Paul Fortnow (1937-1980)

My father passed away 25 years ago today. I thought I would share some of the lessons I learned from him.

• Once you win an argument, stop arguing.
• Always play to win. He would always take a handicap and play his hardest rather than dumb down his play particularly in chess, his favorite game.
• When he went to college, the engineers measured their prowess in the number of digits of precision they could get from their slide rules. I guess he didn't get enough digits as he gave up engineering and eventually went into marketing.
• The extra character in a movie that seems to serve no purpose is the one that committed the murder.
• He said "When you grow up and drive you can choose the radio station." Like my daughters let me get away with that.
• Nixon really was a crook.
• Given enough money, there is nothing anyone won't do.
• He meticulously taught me how to keep score in baseball as this is a skill every American should know. He then told me never to keep score as it distracts from the game.
• The two course he regretted not taking in college were art and music appreciation. So I took art appreciation in my first year. Big mistake. For the record the two courses I wish I took were economics and mathematical logic.

Dad, if you are surfing the net from the great beyond know that I miss you and my family, including the daughter-in-law and granddaughters you never met, think of you often. And your Red Sox finally won the World Series.

The End of the Travel Season

In 2005 I have already traveled on five trips to four different countries on three different continents. My travel comes in bunches. I didn't teach in the winter quarter (at the cost of doubling up in the spring) so I planned much of my travel during this time. After I return tomorrow I have no major trips planned until STOC in late May.

Why do I travel? I don't enjoy at all the act of traveling despite the advantage of non-stop flights to nearly everywhere from Chicago. The tourism bit has long lost its allure. After a while all the cities and universities start to look the same.

I don't need to travel. I could hole up in Chicago, just work with the students and visitors and have a moderate research career. I have tenure so my job is safe in any case. So why travel?

1. People: Working with people, talking with people, drinking with people. Traveling to visit different people keeps my research and academic life from getting stale.
2. Getting Away: Like most people, I have considerable work and family responsibilities and travel allows me to escape and have time to focus on research. When I visit someone for a short time they will usually make time to work with me as well. The internet has prevented me from completely escaping but I can usually tell people I'm away and I will deal with the problem when I get back. I do try to keep to a goal of not leaving the family for more than a week at a time.
3. Being Involved: If you want to be an active member of the community people need to know who you are. Don't travel and people will forget you. Email is not a good substitute for meeting face to face.

Traveling has many virtues but I am really looking forward to two straight months of going no where at all.

Bicycling in Holland

When I visit Amsterdam I rent a bike for much the same reason I rent a car when I travel to New Jersey. CWI is in the east part of the city and does not have great access via public transportation. A bicycle lets me get from the hotel to CWI quickly and also gives me easy access to the rest of the city.

Why does the Netherlands have such a strong biking culture? Most of the country is flat, the cities are compact (at least by Chicago standards) and the weather never gets too hot or too cold to bike. One can reliably commute by bike nearly every day of the year. The country has many dedicated bike paths and marked bike lanes on many major roads. Traffic laws greatly favor bikes over cars. This all gives positive reinforcement to bicycling in this country.

Bicycles here for the most part do not have hand brakes or multiple gears but are otherwise rather sturdy. Bicycle lights are required at night; a visiting complexity theorist got a ticket for not using his. Virtually no one wears a helmet. When we lived here on sabbatical we would put our one-year old daughter on a bike seat on the handlebars without a helmet—the norm for Holland but might have gotten us arrested back in the states.

Bicycle theft is a big problem especially in the cities. The general rule is to spend as much on the lock as you did on the bike. Locking up your bike requires knowing your topology; Get it wrong and you might lose a wheel or worse yet keep your wheel and lose the rest of the bike.

Most people in Holland don't bike for health or environmental reasons. Bicycling is often simply the easiest way to get from point A to point B.

What Makes a Good Collaborator?

This week I visit CWI in Amsterdam where I spent my sabbatical year eight years ago and continue working relationships with many people here especially Harry Burhman. Harry is my strongest collaborator in the sense that I have written far more papers with him than any person. So what makes for a good collaborator?

• Strength—A good collaborator should of course be a strong researcher in my area of interest and Harry certainly fits that bill. But there are many great complexity theorists I have hardly or never worked with.
• Compatibility of Strengths—The strengths should complement each other nicely. Good collaborators know their areas well and can quickly focus the inherently difficult parts of a problem and have different tools and approaches they can bring to the table.
• Respect—Good collaborators need to trust and respect each others ability and judgment.
• Philosophy—Long-Term collaborators need to share beliefs on what problems are important and worth working on.
• Personality—You need to have a friendly relationship outside of work. It helps immensely if your respective families get along.
• Luck—Finding the right problems to work on together at the right time. You need a good first collaboration before you start making time for further collaborations.
• Distance—This seems counterintuitive but two people in the same geographical area rarely have a long history of collaboration. It's hard to make time for working together when you are in close proximity. Also two people who see each other constantly get tired of working with each other no matter how compatible they are. Better to keep in email contact and have several short and long visits where one can allocate time for the other.

There is something else that I can't perfectly describe where something just "clicks" when you have someone you can work with well.

The Reality of Virtual Pets

The Tamagotchi craze has hit my daughters' school. The Tamagotchi is a small toy with a few buttons and a screen where you can play with a cartoonish creature. You can feed and play with your creature to make him/her happy. Two people can point their devices at each other and their Tamagotchis will play and possibly "mate".

First my older daughter's fourth grade friends gave her a Tamagotchi and soon after my younger first grader also wanted one and we relented. She then convinced several of her first grade friends that they needed them which caused some parents to call us mostly because they got these Tamagotchi and nobody could figure out how to work them. My first grader is giving out lessons tomorrow.

These devices beep when they need attention—food or playing or needing cleanup after an "accident". Don't attend to them and they will die. My kids pay constant attention to the Tamagotchi and it is sometimes hard to bring them back to reality. My youngest, a couple of days ago, got all excited when her Tamagotchi learned to go to the bathroom by himself. It didn't seem like all that long ago that I got excited about the same thing for her.

Luckily young kids are fickle and the Tamagotchi craze will soon pass. But move over Godzilla, the scariest monster from Japan is a friendly looking creature in a plastic case.

NP-complete Problems and Physical Reality

Scott Aaronson has a fun paper in the complexity column of the new SIGACT News where he addresses the question: Can NP-complete problems be solved efficiently in the physical universe? Worth reading though I can sum up the answer in one word: No.

Favorite Theorems: Efficient Computation

February Edition

How do we formalize the notion of efficient computation? Two important papers from the 60's suggest polynomial time algorithms are efficient though both caution against equating the concepts.

Paths, Trees and Flowers, Jack Edmonds, 1965.

The Intrinsic Computational Difficulty of Functions, Alan Cobham, 1964.

Edmonds paper will always be best known for giving the first efficient algorithm for matching on general graphs. But I list it here because of a section of his paper labeled "Digression". Edmonds talks about the difference between exponential and algebraic (polynomial) order though he cautions against any rigid criteria for efficiency.

An explanation is due on the use of the words "efficient algorithm"…I am not prepared to set up the machinery necessary to give it formal meaning, nor is the present context appropriate for doing this…For practical purposes the difference between algebraic and exponential order is more crucial than the difference between [computable and not computable]…It would be unfortunate for any rigid criterion to inhibit the practical development of algorithms which are either not known or known not to conform nicely to the criterion…However, if only to motivate the search for good, practical algorithms, it is important to realize that it is mathematically sensible even to question their existence.

Cobham defined the class we now call P as important because of its machine independence.

For several reasons the class P seems a natural one to consider. For one thing, if we formalize the definition relative to various general classes of computing machines we seem always to end up with the same well-defined class of functions. Thus we can give a mathematical characterization of P having some confidence it characterizes correctly our informally defined class. This class then turns out to have several natural closure properties, being closed in particular under explicit transformation, composition and limited recursion on notation (digit-by-digit recursion).

Cobham also offers a caution.

The problem is reminiscent of, and obviously closely related to, that of the formalization of the notion of effectiveness. But the emphasis is different in that the physical aspects of the computation process are here of predominant concern.

Perhaps Cobham realized there might be future models of computation that may not correspond to his class P. Later developments of randomized and quantum computation will show that perhaps we cannot have a fixed notion of efficient computation.

The Researcher's Dilemma

I finally read Clayton's Christensen's The Innovator's Dilemma. A few years ago an NEC executive gave a talk using the ideas in the book to explain NEC's interest in quantum computing.

Christensen divides new technologies into two groups: sustaining and disruptive. Sustaining technology helps improve a product for its current customers for example Intel building a faster microprocessor. Disruptive technology is technology that is not initially useful for a big company's current clients. So other newer and smaller companies develop the technology for a niche market. But eventually the technology improves to meet the needs of the original big company's customers at a much lower cost. At this time the big company cannot catch up with the new technology and loses their main business to the newer startups. Christensen gives many examples such as the development of smaller disk drives and the advent of discount stores like Target hurting bigger retailers like Sears.

The book makes some solid arguments but determining which technologies will be disruptive is quite difficult. So companies need to place lots of bets perhaps why NEC funds quantum computing research just in case it becomes a disruptive technology in the future.

Do the same concepts apply to research? In complexity we have had some disruptive technologies, for example, the PCP theorem for hardness of approximation or the idea of Nisan and Wigderson of using hard languages to derandomize, or going way back the whole concept of NP-completeness. Other concepts like circuit complexity have not been as disruptive as originally thought. Also one could view tools like the probabilistic method or extractors as disruptive.

What could happen to large companies can also happen to researchers. Suppose George is a researcher who creates new results building on current ideas with small twists (sustaining technology). George ignores some new ideas in complexity because it doesn't seem to help him prove new results in his area. But as those new technologies develop they later allow others to go well beyond what George has done. Now George is behind the curve on the new disruptive technology and can no longer play an important role even in his own field.

What can George do? He can learn the new techniques or he can change fields. And often the newcomers never properly learn the old tools and George can still pull a few surprises out of his hat.

Finding Duplicates

Here is an interesting problem given by Muthukrishnan during his talk in the New Horizons workshop.

Start with an array A of n+1 entries each consisting of an integer between 1 and n. By the pigeonhole principle there must be some i≠j and a w such that A(i)=A(j)=w. The goal is to find w. Depending on A there may be several such w, we want to find any one of them. The catch is that you only get to use O(log n) bits of memory.

First a warm-up puzzle: Find w using only O(n) queries to entries of A (remember you only get O(log n) space). Hint: Use pointer chasing.

Now suppose A is streamed, that is we get in order A(1),A(2),…,A(n+1) and then get another pass etc. How many passes do you need to find a w?

You can find w in n+1 passes just by trying each possible value for w. With a little work you can use O(log n) passes doing a binary search.

Muthukrishnan asks whether the number of passes needed is Ω(log n) or O(1) or something in between.

Theory in Japan

Japan has produced some excellent theorists, like Seinosuke Toda who won the 1998 Gödel prize for his paper reducing the polynomial-time hierarchy to counting solutions of NP problems. But Japan has not had the large international impact in theoretical computer science as countries like Israel, India or Hungary.

In this trip I am seeing signs that this may change for the better. The conference is kicking off a new project New Horizons in Computing that shows a serious commitment of the Japanese government to computer science theory. The large turnout, over 130 registrants the majority of which are students, shows a keen interest in theory from the academic side as well.

I'd like to see more Japanese go abroad for graduate work and postdoc positions and more Japanese universities making theory an important part of their computer science programs. But given the excitement I see at this meeting I am very hopeful that Japan will also become a true theory powerhouse in the near future.