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)