Informatics in Indiana

Many universities try to integrate information technology into many different disciplines usually through their computer science departments. Our neighbors to the east are creating a bold experiment in this integration, the Indiana University School of Informatics, with fastly growing departments spread over several of their campuses.

What is informatics? According to Indiana, Informatics is

• understanding the impact technology has on people.
• the development of new uses for technology.
• the application of information technology in the context of another field.

Their research groups already encompass quite a few areas including biological, chemical and social issues of information technology.

I visited the Informatics department in Bloomington a few months ago and sensed an excitement of growing a new discipline and bringing in many information technology researchers from different scientific disciplines. Note the real distinction between computer science that studies and improves the nature of computation and and informatics that aims for integration of information technology between various areas of study.

Mixing researchers from vastly different disciplines has had its shares of successes and failures and only time will tell how successful the Indiana experiment will become. But I'm extremely impressed with the commitment from the University and the state to this area of informatics and I expect we'll hear much more from Indiana in this area.

Comments

Some strong comments on Rocco's post on the recent Columbia theory day. In my own highly biased point of view, I find the study of efficient computation critical in a society that becomes continually reliant on computation on both explicit computers and implicitly in various biological, economic and physical systems. And how can one study efficient computation without developing reasonable models of computation and analyzing those models?

I don't mean to sound so altruistic; I get paid to do what I love. But I do truly believe one needs to understand the mechanisms that make up our world if we wish to improve them. I write this weblog, in part, to educate about the beauty and applications of theoretical computer science.

A comment about comments. I understand that many of you choose to post anonymously rather than register at Blogger and I'm fine with that. If you don't mind please add your name at the end of the comment. I like to know who is behind the comments and its useful to match up different comments by the same person. Of course, I'd rather get your comments anonymously than not at all.

Update 5/21: Stanley Fish, the departing Dean of the Arts and Sciences of University of Illinois at Chicago argues more for a separation of academic research and policy.

I exit with a three-part piece of wisdom for those who work in higher education: do your job; don't try to do someone else's job, as you are unlikely to be qualified; and don't let anyone else do your job. In other words, don't confuse your academic obligations with the obligation to save the world; that's not your job as an academic; and don't surrender your academic obligations to the agenda of any non-academic constituency � parents, legislators, trustees or donors. In short, don't cross the boundary between academic work and partisan advocacy, whether the advocacy is yours or someone else's. Marx famously said that our job is not to interpret the world, but to change it. In the academy, however, it is exactly the reverse: our job is not to change the world, but to interpret it.

A Part-Time Ph.D.?

A question from a reader (slightly edited):

There are no part-time (or even full time) Ph.D. programs at top universities in computer science or mathematics that can be completed by those who work full time. For various personal reasons I find myself in a position that requires me to work full time; however, I am passionate about theoretical computer science/mathematics. Unfortunately, most American schools do not accommodate Ph.D. students under these circumstances. Is this a decision based upon the assumption that those who work full time will not produce good/enough work, or is this a decision based, simply, upon the fact that professors want to work standard hours and teaching a course from 5:30 - 6:20 is quite non-standard?

Courses are not a major issue. The course requirements for a Ph.D. usually do not significantly differ than those for a Masters and many universities offer a Masters program in computer science for full-time workers. I do see two other major barriers to a part-time Ph.D.: Funding and Research.

Nearly all Ph.D. student get funded for tuition and some living expenses via a fellowship, teaching assistantship or research assistantship. Government agencies generally don't give fellowships to part-time students and a TA or RA requires about twenty hours a week, leaving someone who already has a full-time job with no time for actually completing the Ph.D.

But suppose you felt that a Ph.D. was worth the expense or were independently wealthy and for some reason still had to work a full-time job. Ph.D. level research in math and theoretical computer science requires intense background study and long stretches of thinking, understanding the problem and working through many different ideas until one actually makes significant progress toward original work. For this one needs time and the relationship is not linear. Someone who can spend forty hours a week focusing on research will be far more than twice as successful as one who can only spend twenty.

The dominant limitation on number of Ph.D. students in CS departments is funding. If you have a record that would have gotten you in to a top computer science department as a full-time Ph.D. student and you bring your own money to the table, I suspect at many schools you can work out a part-time schedule. But you'll find doing original research on a part-time basis a daunting if not impossible task.

Randomized Blogspace

A report from Theory Day co-organizer Rocco Servedio

On Friday May 14 a special Columbia/IBM Research/NYU Theory Day was held at Columbia University in New York City. The New York area theory days started at Columbia in 1982; this one was a special event to mark both the 25th anniversary of the CS department at Columbia and the 250th anniversary of Columbia University.

More than 280 attendees came out to hear four talks by outstanding theorists:

• Richard Karp (UC Berkeley): Current Challenges in Computational Genomics: Haplotyping
• Shafi Goldwasser (MIT/Weizmann): Proving Hard-Core Predicates using List Decoding
• Prabhakar Raghavan (Verity/Stanford): Finding Information in Networks
• Peter Shor (MIT): Quantum error correction and fault tolerant quantum computation

The day ended with a panel discussion on "The Future of CS Theory." Avi Wigderson (IAS) joined the four speakers for the panel, which was moderated by Mihalis Yannakakis (Columbia). Here is a brief summary of what was said.

Mihalis started things off by observing that over the past 50 years CS theory has enjoyed outstanding successes and has had tremendous impact on computing. Indeed, some of the successes were so profound that they gave rise to whole new fields of computer science (databases, security) that are no longer thought of as "CS theory". Mihalis asked each of the panelists to briefly give their views on the future of CS theory. Some highlights of what they said:

Avi observed that CS theory can (and should) have more impact on early education, starting in high school or even earlier. We can give important insights into fundamental ideas such as adversaries, randomness, learning, recursion, games, proofs, and "getting things done efficiently" (which Avi referred to as "the oldest profession in the world"). He also highlighted some specific goals for CS theory at this point, which included showing that BPP ≠ NEXP; coming up with non-natural proof techniques for circuit lower bounds; discovering new types of quantum algorithms; developing a general theory of what types of algorithms can give optimal approximation ratios; and proving that SL = L and that MATCHING is in NC.

Dick Karp warned against taking anyone's advice or predictions too seriously. That said, he advocated for a healthy balance between foundational questions at the core of CS theory and new questions that arise from the role of computation in the world and the sciences. He highlighted three areas of interest for the future: (1) the study of large scale distributed systems such as the Web, incorporating ideas from economics and game theory; (2) connections with areas of natural science, ranging from statistical physics to quantum mechanics to biology; and (3) the "new face" of AI in which stochastic and graphical models and statistical inference are playing a big role.

Peter also commented on the perils of predicting the future; we sometimes tend to think that there will be no more revolutionary ideas simply because we don't know what those ideas will be. But such ideas will come along from "out of the blue" as they always have. He noted that while past predictions for the future of CS theory have tended to be on the doom and gloom side, things have actually turned out pretty well -- there are interesting jobs and demand for theorists in industry; theory is more and more noticed and used by practitioners; and rather than becoming increasingly recondite and inward-looking, theory is building stronger connections with mathematics, physics, and other disciplines.

Prabhakar observed that what we think of as CS theory is really two main thrusts of work with some overlap: there is the theory of computation as an inherent phenomenon (i.e. when we study MOD 17 gates and what they can do even though nobody will ever build one), and the theory of computation as it is practiced (i.e. most of the world's cycles are spent making a billion people happy rather than crunching data for a few thousand scientists). The Web is a paradigmatic aspect of the second thrust; he noted that in this area economic factors may play a role at least as important as traditional resource bounds like time and space. Prabhakar also stressed the importance of backing up claims of practical relevance for our work (and, on an unrelated note, mentioned this weblog in a slide entitled "Randomized Blogspace".)

Shafi observed that CS theory is having an increasing impact on classical mathematics such as coding theory, number theory, and signal processing. On the other hand, we are also dedicating more energy (and having more success) in solving problems in the real world -- both of these trends are good signs for the field. She advised researchers to follow their own tastes and interests rather than anyone else's recommendations when it comes to "the next big challenge for the field."

After these statements the floor opened up to questions and discussion with the audience. A brief summary:

One questioner noted that the theoretical models of parallelism from 20 years ago don't correspond to how large distributed systems work now, and asked whether a similar phenomenon could be taking place with quantum computation -- are we studying the right model? Some panelists responded that while we aren't likely to end up with quantum computers that correspond exactly to quantum circuits, it seems likely that algorithms developed for the quantum circuit model will prove useful if/when we do get quantum computers in one form or another.

There was quite a bit of discussion about the role of CS theory in the undergraduate curriculum and what undergraduate CS majors should know about theory. Some panelists opined that NP-completeness, undecidability, models of computation, and algorithms are core topics that even high school students perhaps should know. A view emerged that there is real (potential) widespread interest out there in the "gems" of CS theory, and that we should do a better job of explaining what is fascinating and beautiful about our field to students.

In response to a question about the future status of the P=NP question, some panelists observed that other great research communities (mathematics, physics) have tussled with unsolved questions for centuries. We seem to be stuck right now, but on the bright side we have some understanding (natural proofs, for instance) of why we are stuck -- perhaps mathematicians should step back and think about why the Riemann hypothesis is still unresolved.

To close, here are three quotes lifted more or less verbatim from the panel discussion (but left anonymous here):

• "The future for DNA computation is dim" (in response to the question "What is the future for DNA computation?")
• "Polynomial time computation is a complex object to understand."
• "We are so much closer to understanding each other's talks than the mathematicians are."

Cornell's New President

On Friday I went to an alumni reception for Jeffrey Lehman, new president of Cornell University. Besides learning that the cinderblock dorms where I spent my freshman year are finally being demolished, a number of interesting aspects of university life came out of the question and answer session.

One question asked about lack of student activism on campus. Lehman acknowledged the problem outside of environmental issues and told of his plan for a mock presidential election at Cornell before the real election. This seemed like a weak answer--mock elections we had in high school. I doubt college students could get excited about a mock election when most of them can vote in the real thing.

On the other political end was a question about the liberal bias in faculty. Lehman acknowledged this as well but didn't consider it a problem as long as the conservative voice was not silenced. This was a good answer.

On affirmative action he said that Cornell needed more minority applicants and was working on a suggestion to start attracting students even in middle school. And someone asked a question about whether Cornell should have common core courses for the students, an interesting issue for me since even small changes in the University of Chicago's traditionally strong core have caused major controversy. Lehman said that Cornell will continue its tradition of not having any fixed course requirements for all students (besides the swimming test).

Favorite Theorems: Probabilistically Checkable Proofs

April Edition

No single topic has dominated computational complexity over the past dozen years than probabilistically checkable proofs (PCPs). Arora, Lund, Motwani, Sudan and Szegedy, in a paper on my 1994 list, showed that every language in NP has a polynomial-sized PCP that can be verified by probabilistic polynomial-time verifier using O(log n) random coins and some constant number of queries. Well beyond the complexity interest in this result, PCPs give hardness of approximation results for a variety of NP-complete problems.

Researchers in many exciting papers have improved the parameters of the PCP results in order to get improved limits on approximation. But one paper really puts it all together for some tight results.

Some optimal inapproximability results by Johan Håstad, JACM, Volume 48, 2001.

Håstad's paper shows that every language L in NP has a PCP with with O(log n) random coins and 3 queries, where

1. If x is in L then the verifier is convinced with probability arbitrarily close to one.
2. If x is not in L then no proof can convince the verifier with probability more than one-half.

There parameters are the best possible.

The paper gives some optimal approximation results. Consider Max-3-SAT, where one wants to find an assignment that maximizes the number of satisfied clauses of a 3-CNF formula. We can satisfy 7/8 of the clauses by choosing a random assignment, a process we can also derandomize. Håstad's result implies that no better algorithm exists unless NP is easy. The paper also gives improved lower bounds on approximation on problems like vertex cover and max cut.

Håstad's paper pulls in tools from a large collection of research papers. Madhu Sudan's lecture notes describes Håstad's results and the techniques and papers leading up to it. There's also been exciting PCP research since Håstad's paper but I'll have to leave that for another day.

An Auction of Google

For those with an interest in auction theory, the Google IPO auction gives an interesting testbed for auction mechanism design. Instead of having an investment bank set a fixed price for the IPO, instead Google will auction off the shares.

A New York Times article today describes many of the decisions and possible pitfalls of the various kinds of auctions Google might use. Also check out the Google SEC filing. One can learn quite a bit about auctions as well as the business of search engines from this rather informally written document. I have never had so much fun reading a prospectus.

My prediction: Great interest in Google will highly overvalue the stock whatever auction mechanism they will use. If you are interested in investing in Google, hold off until the price settles or you will suffer the dreaded "winner's curse."

Page Charges

The Journal of the ACM has started asking for page charges.

Author's institutions or corporations are requested to honor a page charge of $60.00 per printed page or part thereof, to help defray the cost of publication. Page charges apply to all contributions. Payment of page charges is not a condition of publication; editorial acceptance of a paper is unaffected by payment or nonpayment.

SIAM also recently asked us for $72/page for a Journal on Computing paper.

I despise page charges. Authors do the research, write the papers, give the journals the copyright and now the journals want us to pay for the privilege. I know the charges are optional and come from research funds but we have other needs for the money. The page charges on a moderate-sized paper could, for example, send a grad student or two to a major conference.

We have problems in our field with expensive for-profit journals and papers that never appear in refereed journals at all. We need to encourage authors to send their articles to journals run by the non-profit societies. We should not then send them a bill for doing the right thing.

Games

A readers asked about the complexity of games like Go and Chess. David Eppstein has a nice site giving a short description and references to a number of specific games.

Let us thought put such games in a general framework. We have a board and each player in turn can make one of a list of legal moves that depend on the current placement of pieces on the board. We focus on deterministic games of complete information, as opposed to games like backgammon or poker.

Games like Go and Chess are played on a fixed board, one could just enumerate all of the possible board combinations and perform perfect play in a constant amount of time. So we need to look at generalized versions of Go and Chess where the size of the board and the set of rules can vary.

Let's place this in a general setting. We have a polynomial-time algorithm that given a board and the current player can tell whether the game has ended with its outcome or can give a list of legal moves for the player. Chandra, Kozen and Stockmeyer have a seminal paper on these alternating games: If we restrict the length of the game to polynomial-time, such games characterize PSPACE (problems solvable with polynomial memory and unlimited time). Games with arbitrary long play on polynomial-size boards characterize EXP (exponential time).

So we have results like given an opening position on a generalized Go games, it is EXP-complete to determine if a player have a forced win. But even if the official Go rules allow it, I find it hard to believe that players can play the game for an exponential number of moves. So it makes sense to add some artificial stopping rules that cause the game to end after a reasonable amount of time and such games are usually PSPACE-complete.

The PSPACE-completeness results hold for many very simple games. This mirrors the fact that complexity does not arise from complicated actions, rather from the interactions of many simple actions.

New Web Host

I'm moving my web hosting service--if you can read this you are accessing the new host. I will wait a day or two to post again until the changeover is complete.

Meanwhile enjoy this Guardian column by John Sutherland describing how the British higher education system has evolved over the past four decades (via Crooked Timber). Many of the same issues apply in America and I suspect many other countries as well. Sutherland sums it up nicely.

The big question. Is the whole system in better or worse shape than it was in 1964? I don't know. All I do know is that I'd like to do it all again, and get it right this time.

America Losing Its Edge

Some required reading if you haven't seen it yet, a New York Times article on how America has lost some of its scientific leadership role over the rest of the world.

The article does not go much into the reasons behind the change so let me make some conjectures. For a long while now, the majority of Ph.D. students in the US came from other countries. As the academic job market in the US got tighter, many of these researchers went back to their home countries and established strong research groups there. Also recent technological changes have taken away some comparative advantage of doing research in the states as communication and access to research papers has become a much easier task.

I welcome the added competition, the more globalization of science that we have, the more we will all push one another with scientific research becoming the big winner. In my own field, I like seeing countries like Israel becoming theory powerhouses and definite growth of theory in places as diverse as India and Australia. A few years ago it would have been unthinkable to have STOC or FOCS overseas but recently STOC 2001 was held in Greece and the upcoming FOCS will be in Rome.

Most of all I hope the article serves as a wake-up call to American legislators. Time to give NSF that large budget increase that they've been talking about for several years now.

Karp Symposium

[A report from weblog correspondent Bill Gasarch. Link to Allender's talk added 5/7]

On Wednesday April 28 there was a SYMPOSIUM HONORING DR. RICHARD M. KARP at Drexel University in Philadelphia.

They were honoring him for winning the BEN FRANKLIN MEDAL IN COMPUTER AND COGNITIVE SCIENCE (There are Ben Franklin Medals for Physics, Chemistry, Life Sciences, Earth Science, Computer and Cognitive Science, and Engineering.)

There were three talks:

ERIC ALLENDER: The Audacity of Computational Complexity.

This talk described the basics of complexity theory and mostly focused on reductions. A nice contrast that it made:

1. in the year 2004 we have good reason to think that many problems (e.g., SAT, 3-COL) are hard, except factoring which is still hard to classify.
2. in the year 1970 most problems (including SAT, 3-COL) were hard to classify.

The talk also pointed out some of the problems with Computational Complexity (e.g., "How can you call a n¹⁰⁰⁰⁰⁰ algorithm feasible?") and answered them nicely (e.g., "we want to show problems are hard, so showing its not in P does that.") The talk both began and ended on the topic of CHECKERS and GO being computationally hard problems.

AVI WIGDERSON: The Power and Weakness of Randomness (When you are short on time).

This talk showed several examples of problems where randomness helps (hence randomized algorithms are powerful) but also indicated why there may be reason to think that you can always replace a randomized algorithms with a polynomial time algorithm (hence randomization adds no power). The problems it helped on involved sampling, routing in networks, and mazes.

RICHARD KARP: Even Approximation Solutions can be Hard to Compute.

This talk was about certain problems that can be approximated and certain ones that (it seems) cannot be. A nice contrast was variants of TSP, which ranged from what can be approximated very well, to what can be approximated some, to what can't be approximated. He also brought in randomized rounding as a technique for approximation. The talk ended on PCP (done informally) and how it can be used to show lower bounds for approximation.

OVERALL:
The talks were all well presented and quite understandable. The point of the talks was to expose our area to people outside of theory and perhaps even outside of computer science. As such the theorists in the audience did not learn much new; however, it is still interesting to see someone else's perspective on material that you are familiar with.

Conferences versus Journals

A reader asks why Gafni and Borowski did not publish their paper in a journal and become eligible for the Gödel Prize. I wish this was an isolated incident but it reflects on a sad state of affairs in computer science and theoretical computer science in particular. Too many papers in our field, including many great ones, do not get submitted to refereed journals. In an extreme case, Steve Cook received the Turing Award mostly for a STOC paper.

In most cases, conferences in computer science are more selective than journals. Your reputation in theoretical computer science is measured more by the conferences your papers appear than the journals. In other fields like mathematics, physics and biology, journals have a much greater reputation and most of their papers do appear in refereed form. I believe the reason is historical: computer science started as a quickly changing field and journals could not keep up with the rapidly emerging ideas.

Conference program committee cannot and do not produce full referee reports on conference submissions. Proofs are not verified. Papers are not proofread carefully for mistakes and suggested improvement of presentation. Computer science suffers by not having the permanency and stamp of approval of a journal publication on many of its best papers. The founders of the Gödel Prize put in the journal requirement to encourage potential award winning papers to go through the full refereeing process.

Many papers in our field do appear in journals and some researchers are extremely diligent in making sure all of their work appears in refereed form. Also I know of no computer scientist who purposely avoids sending their papers to a journal. But when we have a system that does not value journal publications, a computer scientist pressed for time often will not make the effort to take their papers past the conference version.

Is Disney World NP-complete?

The Unofficial Guide to Walt Disney World 2004 gives a lesson on complexity by describing the optimal tour of the Magic Kingdom as a traveling salesman problem. Some excerpts:

As we add more attractions to our list, the number of possible touring plans grows rapidly...The 21 attractions in the Magic Kingdom One-Day Touring Plan for Adults as a staggering 51,090,942,171,709,440,000 possible touring plans...roughly six times more than the estimated number of grains of sand in the whole world...Fortunately, scientists have been hard at work on similar problems for many years..finding good ways to visit many places with minimum effort is such a common problem that it has its own nickname: the traveling salesman problem.

The book goes on to describe the computer program they use to approximate the optimal tour. Read more here (which I found by searching within the book for "traveling salesman" on the Amazon site). You'll need to be a registered user of Amazon.com to read it.

Gödel Prize

From the PODC (distributed computing) mailing list via Harry Buhrman. Usually the winners are kept secret until the ICALP or STOC conference but the PODC mailing list has already broken the news.

It has been recently announced that this year's winners of the Gödel Prize are

• Maurice Herlihy and Nir Shavit for their paper "The topological structure of asynchronous computability" (J. ACM, 1999), and
• Mike Saks and Fotios Zaharoglou for their paper "Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge" (SIAM J. Computing, 2000).

As we all know, the result was initially published simultaneously in STOC 1993 also by Eli Gafni and Liz Borowski, but the Gödel Prize is awarded only to journal articles.

Congratulations to the winners!

Note that for the second time, the Gödel's Prize honors a core PODC topic (in 1997, Joe Halpern and Yoram Moses won the prize). This is a sign both of the scientific quality of the PODC community, as well as the respect it wins in the theoretical CS world at large.

In case you are counting, that's Complexity 5, PODC 2.

Theory Girl

From Bill Gasarch: There are some more novelty songs about theory (aside from THE LONGEST PATH) from the Washington CSE Band. The best one is THEORY GIRL.

A Few Short Announcements

Alan Kay will receive the 2004 Turing award. It can't always be a theorist.

Registration is open for the 2004 Conference on Computational Complexity. The final schedule will be posted soon. Also keep in mind STOC 2004 right here in Chicago.

The list of accepted papers for ICALP is up.

Finally, next Wednesday the 28^th in Philadelphia, Drexel is hosting a symposium on computational complexity honoring Richard Karp.

Are There #P Functions Equivalent to SAT?

Help me solve this problem, write the paper with me, get an Erdös number of 3 and it won't cost you a cent.

We can have #P functions hard for the polynomial-time hierarchy (Toda) or very easy but can they capture exactly the power of NP?

Conjecture: There exists an f in #P such that P^f=P^SAT.

There is some precedence: counting the number of graph isomorphisms is equivalent to solving graph isomorphism.

The conjecture is true if NP=UP, NP=PP or if GI is NP-complete. I don't believe any of these. Does the conjecture follow from some believable assumption or perhaps no assumption at all? We don't know if there exists a relativized world where the conjecture does not hold.

Even the following weaker conjecture is open: There exists an f in #P such that NP⊆P^f⊆PH.

A good solution to these conjectures might help us settle the checkability of SAT

 

Asian Food for Thought?

Many years ago, an Israeli graduate student made the rounds and gave talks at several US universities. When he arrived in Chicago, he asked me if Americans only eat Chinese food. I told him he hadn't seen a random sample of Americans and took him out for some good Chicago ribs. Afterwords he told me he preferred the Chinese food.

At a logic conference at Notre Dame, I ate dinner with a small group at one of the few Chinese restaurants in South Bend. Surprisingly no other mathematicians were eating in the restaurant. Just as we noticed this, the waiters started putting tables together and about five minutes later in walk about 20 logicians for dinner.

Why do mathematicians and computer scientists eat so much Asian food? Not just Chinese but Japanese, Thai, Korean, Vietnamese, Indonesian, Ethiopian (not Asian but close enough) and of course Indian (northern and southern). Not that I don't enjoy Asian food but what's wrong with a good hamburger?

Favorite Theorems: Primality

March Edition

Primality is a problem hanging onto a cliff above P with its grip continuing to loosen each day. - Paraphrased from a talk given by Juris Hartmanis in 1986.

It took sixteen more years but the primality problem did fall.

PRIMES is in P by Manindra Agrawal, Neeraj Kayal and Nitin Saxena.

This paper gave the first provably deterministic polynomial-time algorithm that could determine whether n is a prime given n in binary. The theoretical importance cannot be overstated. But why do I consider the paper a complexity result instead of just an algorithmic result?

Manindra Agrawal had already a strong reputation as a complexity theorist. The proof involves a derandomization technique for a probabilistic algorithm for primality. But more importantly primality had a long history in complexity.

Primality is in co-NP almost by definition. In 1975, Vaughn Pratt showed that PRIMES is in NP. In 1977, Solovay and Strassen showed that PRIMES in co-RP and testing primality became the standard example of a probabilistic algorithm. In 1987, Adleman and Huang building on work of Goldwasser and Kilian showed that PRIMES is in RP and thus in ZPP. In 1992, Fellows and Koblitz showed that PRIMES is in UP∩co-UP. Finally in 2002 came AKS putting PRIMES in P.

A runner-up in this area is the division problem recently shown to be in logarithmic space and below.

The Cost of Textbooks

The University of Chicago Bookstore has asked for textbook requests for the fall quarter by the middle of next month instead of during the summer as in past years. The reasoning: A burgeoning used textbook market. If the bookstore knows what books faculty will use in the fall, they can offer higher prices to pay for used books at the end of the spring quarter.

This is just an indication of the problems of higher textbook costs. CALPIRG has a recent extensive report on this topic. Textbook costs add to already spiraling increases in tuition and other college expenses.

In addition, I have more griping than usual about buying the textbook from students in my class though the book, Homer and Selman's Computability and Complexity Theory lists new for $50, under even the average used price mentioned in the CALPIRG report.

What should I do as a faculty member? Should professors strive to reuse the same textbook each year so student's can buy and sell used versions to keep their costs down? That can lead to courses getting stale very fast.

Or should I even forgo textbooks completely and rely on less organized material freely available on the internet? I already do this for graduate courses where strong up-to-date textbooks simply do not exist.

The View of a Science Writer

A friend of mine from college became a science writer for various newspapers and magazines. Once he told me about his two biggest complaints about scientists.

1. Scientists want everyone who works on a project to be named in an article.
2. Scientists want every detail in an article to be complete and correct.

You might initially take the side of the scientists. But the science writer does not write for the scientists but for the general public.

Put yourself in the position of the reader. The reader doesn't want to read through a long list of names that they won't remember anyway. The average reader also just wants an overview of the research and its importance. If removing some technical caveats and slightly oversimplifying the research achieves a better level of understanding to the reader, so be it.

Remember next time you read a science article in the popular press or get interviewed for such an article, the goal of the article is not to pass a serious referee review but to give the general public some glimpse into an important research area.

Blum Complexity Measures

The Blum speed-up theorem states that there exists a computable language L such that if L is in time t(n) then L is in time log(t(n)). The log function can be replaced by any arbitrarily slowly growing computable function. Instead of time one can use space or any other measure Φ that fulfills these properties:

1. Φ(M,x) is finite if and only if M(x) halts, and
2. There is a computable procedure that given (M,x,r) can decide if Φ(M,x)=r.

These are known as Blum axioms and measures that fulfill them are known as Blum complexity measures. They were developed by Manuel Blum in the late 1960's.

The Borodin-Trakhtenbrot Gap Theorem states that given any computable function g(n) (e.g. g(n)=2^n), there exists a function t(n) such that every language computable in time g(t(n)) is also computable in time t(n), i.e., there exists a gap between these time classes. Once again the theorem holds for any Blum complexity measure.

We don't see much of the Blum complexity measures these days for a few reasons.

1. The only truly interesting Blum measures are time and space.
2. The functions and languages that one gets out of the speed-up, gap and related theorems are usually quite large and artificial.
3. Many measures that we are interested in today, like the number of random coins used by a probabilistic Turing machine, do not fulfill the Blum axioms.

In 1991 I saw Manuel Blum give a talk discussing a new complexity measure, something about mind changes, that did not fulfill his axioms. So we had a Blum complexity measure that was not a Blum complexity measure and as Douglas Adams would say Manuel Blum "promptly vanishes in a puff of logic." [Just kidding-we like Manuel]

More News from Dagstuhl

Another Guest Post from Dieter van Melkebeek

Thursday morning, Shuki Bruck gave the first talk at the workshop that dealt with actual Boolean circuits. He pointed out that cyclic circuits can be combinational and may allow us to realize Boolean functions with fewer gates and/or less delay. Consider the following circuit with inputs x1, x2, x3, and outputs f1, f2, f3, f4:

 |-----------------------------------|
 |                                   |
 |    x1       x2     -x1       x3   |
 |    |        |       |        |    |
 |    |        |       |        |    |
 |    v        v       v        v    |
 |                                   |
 |-> \/ ----> /\ ----> \/ ----> /\ --|

      |        |        |        |
      v        v        v        v

      f1       f2       f3       f4

Although the circuit is topologically cyclic, the outputs are well-defined and only depend on the inputs. (Look at the cases x1=0 and x1=1 separately.) A careful analysis shows that every acyclic circuit that outputs f1, f2, f3, and f4 needs at least 5 nonunary gates. Thus, circuits with feedback allow us to gain a factor of 4/5 in terms of number of gates needed to compute these functions. (As usual, we do not count negations.) Shuki presented a sequence of Boolean functions for which the reduction in the number of nonunary gates asymptotically reaches 1/2 if we only allow gates of fanin at most 2. He raised the question how significant the reduction can be if we allow larger fanin.

Thomas Thierauf presented an NC² algorithm for unique perfect matching. A perfect matching in a graph is a collection of disjoint edges that cover all vertices. It is known for some time how to decide the existence of a perfect matching and how to construct one in randomized NC²:

1. Assign random weights from a small range of integers to the edges of the graph such that with high probability there is at most one minimum weight perfect matching. If we are in the situation with a unique minimum weight matching M, we can decide whether a given edge belongs to M by evaluating two determinants of matrices with integer entries that are exponential in the weights. Since the weights are small, we can do the latter in NC².
2. Run the NC² algorithm on all edges in parallel and verify that the result is a perfect matching M.

It is open whether perfect matchings can be constructed deterministically in NC.

To decide whether a graph G has a unique perfect matching, Thomas first runs step 2 above (with unit weights). If that test fails, the algorithm rejects since G either has no perfect matching or has more than one. If the test is passed, the algorithm additionally verifies that G has no perfect matching M' other than M. Such an M' exists iff G contains a cycle that alternates between edges from M and edges in G-M. The latter can be cast as a reachability problem in a graph that is roughly a concatenation of directed copies of M and G-M. Since directed graph reachability can be computed in NC² and the input to the reachability problem can be computed in NC² by step 2 above, the additional test runs in NC², as does the entire algorithm.

On Friday, Oded Lachish discussed the current records on unrestricted circuit lower bounds for explicit functions in n Boolean variables. For circuits that can use any binary gate, the record dates back to 1984 and stands at 3n. For circuits that can use any binary gate except parity and its negation, the record has recently been improved from 4n - O(1) to 5n - o(n). Both records use the technique of gate elimination, and Oded conjectured that the 3n result can be improved along the lines of the recent 5n - o(n) result.

The workshop ended at noon on Friday. One statistic: among the 33 talks, 3 were blackboard only, 5 used handwritten slides, 1 printed slides, and 24 were computer presentations.

Finally, I have one suggestion for those readers who have attended a Dagstuhl seminar in the past. In a response to changes in financial support, the Dagstuhl office is requesting information about research publications that grew out of or have otherwise been significantly influenced by a Dagstuhl seminar. If you are an author of such a publication, please send the information to office@dagstuhl.de. Let's try to keep the wonderful tradition of Dagstuhl alive!

A Free Lunch Theorem For Circuit Complexity

A guest post from Dieter van Melkebeek

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

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

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

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

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

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

Changes in Introductory Theory

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

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

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

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

Opening Day

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

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

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

Teaching High School Physics

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

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

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

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

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

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

Evolution

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

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

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

Is Satisfiability Checkable?

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

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

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

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

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

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

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

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

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

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

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

AT&T Research

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

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

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

Computer Science Unplugged

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

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

An Unnatural Post

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

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

What do you expect since I study an unnatural science?

Favorite Theorems: Derandomization

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

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

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

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

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

March Madness

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

Publishing Papers from Iran

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

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

More from the IEEE Spectrum.

Outsourcing and the Future of Computer Science

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

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

Seeing the Same People in Different Places

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

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

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

SIGACT News

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

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

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

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

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

Persi Diaconis

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

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

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

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

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

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

Counting the Rationals Quickly

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

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

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

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

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

Marriage and the Donald

A few interesting items from this week's Newsweek.

Chicago Theory Ph.D. Amber Settle and quantum computing expert Andre Berthiaume redefine marriage.

Donald Trump lists his seven rules of success. The first four apply directly to academic research.

1. You have to be born with enough brainpower.
2. Once you have that, you have to love what you're doing. I've never seen anyone succeed who didn't love what they were doing.
3. You cannot stop. If there is a concrete wall in front of you, you have to go through it. You can never, ever give up or even think in terms of giving up.
4. Confidence is a very important thing. But confidence isn't something you develop by saying "I'm going to do this or that." You really have to believe it.

Fermat's Last Tango

While visiting Bill Gasarch in Maryland, he chose to show a tape of Fermat's Last Tango, an off-Broadway musical based loosely on Wiles and his experience with Fermat's last theorem. Instead of Wiles they used the name Daniel Keane as the person who proved the theorem. Wiles should be thankful for the name change. We stopped watching after twenty minutes. It was full of monotonous music and clichéd stereotypes of mathematicians. We turned it off after an egotistical song by the Keane character about his "love" of numbers.
According to the video jacket, we missed the love triangle between Keane, his wife and mathematics which he discusses with Fermat, Gauss, Euclid and Newton who have visited from "aftermath." I have learned a valuable lesson: Math and Science can make good drama (Breaking the Code, Proof, Copenhagen and Arcadia as examples) but it doesn't make a good musical.

Why the NSF Needs Your Grant Proposals

One of our graduate students asked me why, if the NSF has limited grant money, do our program officers actively and sometimes aggressively encourage more grant proposals? Let me explain. The NSF uses, as one of their criteria to determine the amount of funding, the ratio of proposals funded from those submitted. A lower ratio indicates higher need and may lead to more funding. Project leaders don't want to lower the numerator as this means giving out fewer grants so instead they try to raise the denominator.

Unfortunately writing a grant proposal takes a considerable amount of time and effort so many researchers are reluctant to write a proposal that has little or no chance of funding. In theory especially one can make a reasonable determination to their chances of funding so even as the number of theorists grow and the theory budget remains steady, the ratio of funded proposals remains relatively constant.

We will have to see how these rules will apply now that the theory program has been reorganized into a part of the larger Formal and Mathematical Foundations Cluster. Nevertheless if you submit a grant proposal that doesn't get funded you can take solace in the fact that you are helping the community. Doesn't that make you feel better?

My Doom

Yesterday I got an email addressed from SUNY Stonybrook with a strange attachment. I checked it with a virus checker and then stupidly opened it. Apparently a new variation of the MyDoom virus got to my computer a few hours before its virus definition was available for download. This is a reason not an excuse.

My computer is clean now but many people I know got emails with the From addressed from someone else I know. So be careful when opening your email and don't make the same mistake I did.

And for all of you Mac and Linux users out there: Go ahead and laugh. (Just anticipating the inevitable comments)

Sneakers

Time for one of my complexity-related movie recommendations. The 1992 film Sneakers describes the adventures of a professional hacking team led by Robert Redford as they go after a device that will break any code. The movie is great fun throughout and I loved the early scenes with the mathematician who created the device (which I assume has a quick factoring algorithm inside). Still I nearly screamed at the screen when he gave a seminar while standing in front of the projected slides.

Recent Turing Award winner Len Adleman served as mathematical consultant for the film. Read about his experiences here.

The LaTeX Generation

When I started college in 1981 I brought a typewriter with me. Junior year of college I experimented with a simple text processor system called script--no more white-out but my papers looked artificial.

In the first year of graduate school I used something called troff to write a term paper for operating systems. But then, just as I had my first research paper to write, LaTeX made its way onto the scene.

Back then LaTeX was relatively easy to use and did a great job with mathematics and references. Running LaTeX took a long time but boy did our papers look good. LaTeX has since become the standard in theoretical computer science papers--one has to use it because everyone else uses it. LaTeX fell far behind in user interface but still does mathematics better than anything else out there. LaTeX runs blazingly fast on today's computers but my papers look like everyone else's papers.

On a recent visit to her grandmother's house, my daughter saw my college typewriter and said "Look, Daddy's old computer." She will never know the joy of white-out.

Parberry's Guides

The most requested topic I get is for my advice for graduate students. So I would be remiss not to mention Ian Parberry's excellent guides to giving presentations and refereeing papers. There are many schools of thought on both topics but you cannot do wrong by following Parberry's advice.

Are you asking "Why do I need a guide for refereeing? Nobody sends me papers to referee." Let me know. We can fix that.

And the Accepted Papers are ....

The closest thing this weblog has to the academy awards; the list of accepted papers of the upcoming Computational Complexity Conference is up.

Is it Recursive, Computable or Decidable?

Every reader of this weblog should know about the recursive and recursively enumerable (r.e.) sets, languages accepted by Turing machines where for recursive sets the machines must halt on all inputs and for r.e. sets the machines could run forever on strings not in the language.
So where's the recursion? The terminology comes out of historically different definitions of the recursive and r.e. sets and now we're stuck with it. Or are we?
In the mid-90's, Chicagoan Robert Soare decided his field of recursion theory suffered harm with its confusing terminology. He wrote a manifesto describing the origin of the concepts and the terminology and gave a passioned argument for changing the terms to computable and computably enumerable (c.e.) sets.
Was Soare successful? Yes and no. Within his own field most researchers now use the new notation. However the fundamental concept of recursive sets goes well beyond the relatively small sub-branch of logic now known as computability theory and it will take a much longer time for these name changes to propagate throughout computer science.
Soare missed another problem of the terminology, namely the word "enumerable." This term comes from the simple theorem that the r.e. sets can be alternatively defined as those languages of strings enumerated on an infinite output tape by a Turing machine with no input.
Because of these terminological issues, Michael Sipser, in his popular textbook, uses decidable and recognizable for the recursive and r.e. sets. I understand his motivation but find the new terminology only adds to students' confusion later in their career.
Whether I use recursive, decidable or computable depends on whom I am talking to. By default I find myself using recursive not because it's the best term but because it's the one that I grew up with.

Journal of Algorithms Editorial Board Bolts to New ACM Journal

Michael Nielsen has a post linking to a post linking to a post noting that the editorial board of the Journal of Algorithms (published by Elsevier) resigned en masse to start a new journal Transactions on Algorithms to be published by ACM.

I won't rehash all of these posts but let me make two points.

1. This move is not without precedent. For example the board of the journal Machine Learning (published by Kluwer) resigned en masse a few years ago to start the online Journal of Machine Learning Research. If publishers like Kluwer and Elsevier continue with their current pricing policies we will continue to see defections. Note though that Kluwer has managed to keep Machine Learning active.
2. From Felten: Computer scientists are lucky, in that most of our best journals and conference proceedings are published by our professional societies at reasonable prices and terms. This is true for American conferences, most non-American theory conferences use Springer's LNCS series. For journals, the professional societies (ACM, IEEE Computer Society, SIAM) publish only a small fraction of computer science journals. While many of the best theory papers go to the Journal of the ACM, Transactions on Algorithms will be ACM's first journal devoted to papers in theoretical computer science.

Minimal Indices

Let's look at some interesting questions about the set of smallest programs. This post relates more to recursion theory than complexity theory. No time bounds today.

Let f₁, f₂, ... be an enumeration of the partial recursive functions. We say f_i≠f_j if there is some input x such that either

1. f_i(x) halts and f_j(x) does not halt, or
2. f_j(x) halts and f_i(x) does not halt or
3. both f_i(x) and f_j(x) halt and f_i(x)≠f_j(x).

Define the set MIN as the set of indices i such that for all j<i, f_i≠f_j. How hard is the set MIN?

MIN is in Σ₂ of the arithmetic hierarchy. For all j<i you need to check that for some input x, one of the three conditions above hold (which might require a ∀ to check that a machine does not halt). We have two unbounded quantifiers (the first "for all" is bounded) so MIN is in Σ₂.

In fact this is tight for Turing reductions, every problem in Σ₂ reduces to MIN.

For an interesting open question we turn to a variation called MIN^*. We say f_i≠^*f_j if one of the three conditions above hold for infinitely many x. MIN^* contains the set of indices i such that for all j<i, f_i≠^*f_j.

Without too much effort one can show MIN^* is in Π₃. Marcus Schaefer shows that every language in Π₃ can be Turing reduces to an oracle that encodes both MIN^* and K where K is the usual halting problem. We would like to remove K which is equivalent to the following open question

Does K Turing reduce to MIN^*?

Read Schaefer's paper for details and many more interesting facts about MIN and MIN^*.

The MIT-Berkeley Axis

"I like everybody in this field" Berkeley professor Christos Papadimitriou said during his acceptance speech of the Knuth Award at the 2002 STOC conference. He paused and added "Even those not on the MIT-Berkeley axis whose papers usually do not get accepted into STOC and FOCS."

Papadimitriou was alluding to an earlier time, the 1980s, when indeed STOC and FOCS were dominated by papers (and program committee members) from MIT and Berkeley and those with strong connections with these institutions. When I attended grad school at MIT I grew to believe there was MIT theory and there was bad theory. Once I left MIT and moved off axis to Chicago I discovered whole beautiful areas of CS theory completely ignored during my MIT days.

The MIT-Berkeley axis still exists to some extent but has far less influence than two decades ago. The vagaries of the job market have forced MIT and Berkeley Ph.D.'s to spread out over a large variety of colleges and universities diluting the axis. Also the field has grown too large to be dominated by two institutions or two conferences.

Reading the Applications

I spent a considerable part of yesterday looking at applications for our Ph.D. program in theoretical computer science. Some of you readers might have an interest in what I look for in a potential graduate student. Keep in mind that other professors may read the applications differently.

Judging Ph.D. applications is not an easy task. Most of our applicants have near perfect grades (in math and TCS courses) and GRE scores (focusing on quantitative). Next I read the letters of recommendation. Nearly every recommender writes positive letters but you can definitely see some differences. "Best student in the past five years" means much more than "one of the top ten graduating CS students this year." Recommendation letters carry more weight if they show a personal contact not just "he took my class." I also pay particular attention to letters written by people I know, i.e., active members of the theoretical computer science community.

I check to see if an applicant has done any research as an undergrad (which helps but is not critical) and do a quick read of the statement of purpose. I know applicants fret considerably about the statement of purpose but in fact they carry very little weight. You can use them to explain anomalies in the application (health problems in the semester you got a C in algorithms). Trying to be clever can harm you. I remember one applicant years ago started the statement with "I want to be a graduate student because I don't want to work for a living."

Does it matter what undergraduate school you attended? We'll accept a student from any university or college, but I keep the quality of the school in mind as I evaluate the application.

Does it matter if you are a US citizen or even live in the US? Not really, though many universities including the University of Chicago have strict lower limits on TOEFL scores for incoming foreign students.

In short for me, assuming an applicant has good grades and scores, it is the letters of recommendation that make or break an application. Choose your letter writers well.

Super Theory Day at Columbia on May 14

Editor's Note: I don't plan to be an announcement server but this theory day deserves some extra publicity. Despite the self-aggrandizing it looks like quite an impressive event. Five famous speakers and most of them are known to give great talks.

The panel discussion should be quite interesting especially since Karp and Wigderson have had in the past well-publicized differing views on the topic. Read them here and here before you attend the panel.

There will be a super special Theory Day at Columbia on Friday, May 14, 2004. Theory Day, sponsored by Columbia, NYU and IBM Research, is a semi-annual conference which brings together New York Metropolitan area theorists for a day of interaction and discussion.

Why have a special one?

Because we have several reasons to celebrate:

1. Columbia University celebrates its 250th anniversary.
2. The Computer Science Department celebrates its 25th anniversary.
3. The Computer Science Theory group at Columbia celebrates its terrific theory faculty. The most recent addition is Mihalis Yannakakis.

The speakers and panelists will be:

Shafi Goldwasser (MIT/Weizmann)
Richard Karp (UC Berkeley)
Prabhakar Raghavan (Verity/Stanford)
Peter Shor (MIT)
Avi Wigderson (IAS)

Mihalis will chair a panel discussion on the future of CS theory.

To make this Theory Day really special we are planning

1. to provide lunch to the participants
2. to provide a commemorative T-shirt.

You will have to RSVP to get either; contact Rocco Servedio.

We hope you'll join us in celebrating theory in the midst of the local celebrations at Columbia.

Designing for Innovation

An interesting NSF press release describes the importance of the layout of offices to the productivity of a research group: Clustering items like refrigerator, printers, coffee makers in common areas increases chance encounters which leads to impromptu conversations and a higher level of innovation.

Such clustering may prove difficult given building layouts and worries about theft. But the study underscores that often the best research comes from unscheduled interactions between scientists as opposed to scheduled research discussions and even the simple choices of placement of offices for faculty and students should take this into consideration.

Let me throw out another question. Is it possible to get these chance encounters in cyberspace? Can we have some sort of virtual complexity coffeehouse? Or does the Internet, despite its great properties of improving communication and distributing information, actually stifle innovation by preventing those random connections we need for research?

A letter from the editors of the journal Computational Complexity

Dear friends and colleagues,

We would like to encourage you to submit suitable papers to the journal Computational Complexity (cc).

We believe that cc should be the main publication forum for papers in complexity theory. In our opinion, a high-quality specialized journal (like cc) should be a preferred option because of the following reasons:

• authors can have better impact on the field by publishing in cc, since their papers will be read by more complexity theorists.
• by having a specialized journal devoted to complexity, our community proclaims and enhances its identity.

What prompts this email is that the 2002 volume of cc was only published in 2003 and consisted of two rather than the customary four issues. This was mainly due to too few good submissions, and we did not want to compromise on quality. (The delays, in turn, caused further problems with library subscriptions.)

It is up to us, the relevant research community, to change this situation by submitting enough good papers to cc to make it flourish. Certainly, the number of high-quality complexity papers every year significantly exceeds the number we can publish, so we hope this is a realistic goal. We are committed to establishing the journal as a leading journal for papers in complexity theory.

Another advantage of publishing in cc: the publisher has a very liberal policy on copyrights and electronic versions. The copyright remains with the authors, and only the commercial-distribution rights are transferred to the publisher. Authors are free to post their work on any non-commercial forum.

You are most welcome to submit papers (via email) to us or to any member of the editorial board.

Currently, the delay between receipt of a final version of an accepted paper and its publication is quite short.

Joachim von zur Gathen (Editor-in-chief)
Sanjeev Arora (Assoc Ed)
Peter B�rgisser (Assoc Ed)
Oded Goldreich (Assoc Ed)

A Little Theorem

Here's a simple result I have seen several times recently, a bit surprising when you first see it.

Theorem: co-NEXP is in NEXP/poly.

NEXP are the languages accepted in nondeterministic time 2^poly(n). A language L is in C/poly for a complexity class C if there is a language A in C and a list of strings a₀, a₁, ... with |a_n| bounded by a polynomial in n such that x is in L if and only if (x,a_|x|) is in A.

I don't know who first showed this theorem and since the proof is rather simple it may have never been published. Let K be a complete set for NEXP and the polynomial length advice a_n for strings of length n is just the number of strings of length n in K. To nondeterministically check that y of length n is not in K, just guess a_n strings other than y of length n and verify they are in K.

This kind of result does not likely hold for NP. Yap shows that if co-NP is in NP/poly then the polynomial-time hierarchy collapses to the third level. This theorem above does not imply co-NEXP has subexponential nondeterministic circuit since exponential circuits might be required to describe the exponential computation.

Harry Buhrman noticed you can strengthen the result to show that EXP_tt^NP is in NEXP/poly where EXP_tt^NP are the set of languages nonadaptively reducible to an NP set in exponential time.

The Defense, Part II

Hein Röhrig successfully defended his Ph.D. thesis at the University of Amsterdam yesterday. The Dutch thesis defense reminds me most of a traditional American wedding. The defense takes place in a chapel. The players include the defender (Röhrig), two paranimf (the groomsmen role), the promotor (advisor, in Röhrig's case two promoters: Harry Buhrman and Paul Vitányi), a Pedel (an official position in the university now held by a woman; she plays a master of ceremonies role) and eight opponents (including myself). The defender and paranimf are in full tux and tails, the Pedel and full professors in academic gowns and the other opponents in suits. In the audience are the defender's friends and family.

The ceremony starts by the defender giving a short description of this thesis to the audience from a Podium in front of the chapel. Led by the Pedel, the promotors and opponents enter the chapel from the back and march to sit in the choir seats. For forty-five minutes the opponents, one at a time, ask hard questions to the defender about his thesis. At the end the Pedel reenters the chapel marches to the front, hits her staff on the ground and says "Hora Est" (Time has expired). The opponents and promotors march out of the chapel to a discussion room where we vote on the defense and sign the thesis. We march back in, present the diploma where the promoters read some traditional text and give a short speech.

The ceremony is followed by a receiving line and reception with dinner later on.

Call me a romantic but I truly enjoy the pomp and circumstances that accompany the Dutch defense sorely lacking in the American counterpart.

Howdy from Amsterdam

I have returned to Amsterdam for the week. I did my sabbatical in Amsterdam seven years ago and I always enjoy the visit. Yesterday I saw the soccer team Amsterdam Ajax beat NEC (the team from Nijmegen, not my previous employer). Today I am visiting CWI, the Dutch math and computer science institute in the group of Harry Buhrman (my most prolific co-author) and Paul Vitányi (who co-wrote the book on Kolmogorov complexity).

Also visiting CWI is Kolya Vereshchagin from Moscow. I had an interesting idea about Kolmogorov complexity but Vereshchagin had the same idea weeks ago. Hate when that happens.

Tomorrow is Hein Röhrig's Ph.D. defense. Hein always wanted me to mention him in this weblog having mentioned both of his officemates, John Tromp and Ronald de Wolf, before. So here is my graduation present to Hein.

STOC and the NSF

A couple of quick notes.

The list of accepted papers for the upcoming STOC conference has been posted. The most intriguing looking paper in complexity is Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size by Ran Raz (also mentioned earlier by Scott Aaronson).

Congress has finally passed the FY 2004 US budget. A 5% increase for NSF, 4.8% for research and related activities.

The Defense, Part I

You've taken your classes, passed your preliminary/qualifying exams, done your research and written your thesis. What stands between you and the Ph.D.--the thesis defense.

After all this buildup, the defense in the states is rather anti-climatic. The student gives an extended talk on his thesis research, the thesis committee peppers the student with questions, then the committee deliberates and decides whether to pass the student.

The defense is mostly for show, the student almost always passes. If the student didn't deserve to pass the fault lies not with the student but with the advisor for letting the process get this far. A dirty little secret: We often make the deliberation longer than needed just to add a little drama.

I have served on defense committees in Denmark and Portugal that follow this same basic plan. But not all countries do the same.

I remember visiting the University of Karlsruhe (Germany) when a parade broke out. I asked about the parade and my host said someone just got their Ph.D. I have also heard of some countries where the advisor has to defend the thesis. Glad I don't teach there.

I bring this up because next week I sit on my third committee at the University of Amsterdam. The Dutch do their Ph.D. defenses the way the way a defense ought to be done. What happens at the Dutch defense? I'll let you know next week.

John Lewis

[From Chris Fuchs]

Dear friends in the quantum information and foundations communities,

Many of you may not know it, but the concept of a generalized quantum measurement or positive-operator-valued measure was introduced in

E. B. Davies and J. T. Lewis, "An Operational Approach to Quantum Probability," Communications in Mathematical Physics 17, 239-260 (1970).

Last night, John Lewis passed away here in Dublin, his home of 28 years, from complications due to a recent surgery. He was a good man, honest and upright, and left us a deep legacy. He will be missed.

The Da Vinci Code

On my vacation I read Dan Brown's The Da Vinci Code, a very popular book I received recently as a gift. Warning: Minor spoilers follow.

I always enjoy a novel with an academic protagonist but the Da Vinci Code reads like a bad conspiracy theory using the roles of the professor and other experts to give the theory some weight. But I bring up this book in this weblog because it spends considerable time on various cryptographic schemes.

I don't blame the author for not using modern cryptography but the methods described would be laughable 50 or 100 years ago. Imagine using the password 1123581321 to guard the biggest secret in the history of religion. It only gets worst: backwards writing, simple anagrams, substitution ciphers, riddles. I suppose these make for fun puzzles for the reader but do not make for a safe secret.

The book describes one intriguing device supposedly invented by Leonardo Da Vinci called a cryptex, a small cylinder with a combination lock that will destroy its written contents if broken. However the book calls it a rudimentary form of public-key cryptography, which only tells me Dan Brown has no idea what that term means.

For a far better novel dealing with cryptography and the related paranoia, check out Neal Stephenson's Cryptonomicon.