Computational Complexity

Sunday, April 30, 2006

 
The Home Stretch

Posted by Lance

If you have an academic job offer, what next? Don't forget to negotiate. I wrote a post on negotiating last fall and in particular you should read the Chronicle article. Worst mistake: Not negotiating.

If you don't have an offer yet, don't panic (at least not too much). We are just entering the home stretch of the CS academic job season. Many of the same few people get the initial interviews and once they get sorted out, more interview and offers are still to come. Don't be afraid to contact departments still in play and remind them of your continued interest.

My first time on the job market in 1989 I didn't get my first offer until June and still had an interview after that. The system has only become even more insane since.

Still you might start getting ready for Plan B. Consider lowering your sights, seeking temporary and/or overseas positions, or thinking about industrial jobs.

Searching for jobs is perhaps the most stressful time in one's academic career. Do your best to keep your spirits up and your options open.

10:10 PM #

Friday, April 28, 2006

 
Kurt Gödel (1906-1978)

Posted by Lance

Kurt Gödel came into our world one hundred years ago today. Gödel's incompleteness theorems changed the way we think about mathematics.

We reprint the translation of the now famous letter he wrote fifty years ago to von Neumann which was rediscovered in 1988. This letter describes something close to the P versus NP problem years before the field Computational Complexity even had its name. SIGACT and EATCS jointly sponsor a prize named after Gödel because of the letter.

Princeton, 20 March 1956

Dear Mr. von Neumann:

With the greatest sorrow I have learned of your illness. The news came to me as quite unexpected. Morgenstern already last summer told me of a bout of weakness you once had, but at that time he thought that this was not of any greater significance. As I hear, in the last months you have undergone a radical treatment and I am happy that this treatment was successful as desired, and that you are now doing better. I hope and wish for you that your condition will soon improve even more and that the newest medical discoveries, if possible, will lead to a complete recovery.

Since you now, as I hear, are feeling stronger, I would like to allow myself to write you about a mathematical problem, of which your opinion would very much interest me: One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let ψ(F,n) be the number of steps the machine requires for this and let φ(n) = max_F ψ(F,n). The question is how fast φ(n) grows for an optimal machine. One can show that φ(n) ≥ k ⋅ n. If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n²), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem. Now it seems to me, however, to be completely within the realm of possibility that φ(n) grows that slowly. Since

1. it seems that φ(n) ≥ k ⋅ n is the only estimation which one can obtain by a generalization of the proof of the undecidability of the Entscheidungsproblem and
2. after all φ(n) ∼ k ⋅ n (or ∼ k ⋅ n²) only means that the number of steps as opposed to trial and error can be reduced from N to log N (or (log N)²).

However, such strong reductions appear in other finite problems, for example in the computation of the quadratic residue symbol using repeated application of the law of reciprocity. It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search.

I do not know if you have heard that "Post's problem", whether there are degrees of unsolvability among problems of the form (∃ y) φ(y,x), where φ is recursive, has been solved in the positive sense by a very young man by the name of Richard Friedberg. The solution is very elegant. Unfortunately, Friedberg does not intend to study mathematics, but rather medicine (apparently under the influence of his father). By the way, what do you think of the attempts to build the foundations of analysis on ramified type theory, which have recently gained momentum? You are probably aware that Paul Lorenzen has pushed ahead with this approach to the theory of Lebesgue measure. However, I believe that in important parts of analysis non-eliminable impredicative proof methods do appear.

I would be very happy to hear something from you personally. Please let me know if there is something that I can do for you. With my best greetings and wishes, as well to your wife,

Sincerely yours,

Kurt Gödel

P.S. I heartily congratulate you on the award that the American government has given to you.

[The text is taken from this page where you can also find the original German text and acknowledgments. John von Neumann, who received the Presidential Medal of Freedom in 1956, had cancer at the time of the letter and passed away in 1957.]

4:56 AM #

Thursday, April 27, 2006

 
Richard Rado (1906-1989)

Posted by Lance

Tomorrow marks the hundredth anniversary of the birth of combinatorialist Richard Rado. Rado is the second most famous mathematician born on April 28, 1906 so we will celebrate him a day early.

In complexity Rado is best known for the Erdös-Rado Sunflower Lemma. A sunflower is a collection of sets S₁,…,S_k such that any two have the same pairwise intersection, i.e., for all 1 ≤ i < j ≤ k, S_i∩S_j=S₁∩S₂. A Venn diagram of these sets would look like a sunflower.

The sunflower lemma states that given any collection of m distinct sets of cardinality s with m>s!(k-1)^s, there is a subcollection of size k that forms a sunflower. The size of the universe plays no role in the statement of the lemma.

The proof is a nice induction once you figure out the right variable to induct on. Try it yourself or read it here.

The sunflower lemma has played a major role in many results in computational complexity, most notably in Razborov's proof that clique does not have small monotone circuits.

5:26 AM #

Wednesday, April 26, 2006

 
Overheard

Posted by Lance

"…which also gives better heuristics for the Traveling Salesman Problem."

"Don't you mean the Traveling Salesperson Problem?"

"No, the Traveling Salesman Problem. A traveling saleswoman would have asked for directions."

7:02 AM #

Monday, April 24, 2006

 
Theory and Systems

Posted by Lance

An anonymous graduate student asks

Why do theory students have to take systems courses?

Most American Ph.D. programs have distributions requirements where every student must take courses and/or exams in many different subfields of computer science. Why have these distribution requirements and in particular why should theory students need to know systems concepts they feel they will never use.

• If a student becomes an academic computer scientist they will have to evaluate systems candidates for hiring and tenure and better they can tell the difference between good systems and bad systems.
• Just like theoretical physicists should do some experimental physics to realize what they do should have some grounding in reality, all computer scientists should do some programming to get a better feeling about the concept of computation.
  The mission of computational complexity is to understand the power of efficient computation and how can one really understand efficient computation if they don't try to do it themselves.
• A good systems class will surprise many theory students by showing that much of systems have a strong theoretical underpinning and basic concepts like abstraction underlies both theory and systems. Some very good theoretical work has arisen from questions from the systems community and vice versa.

Many new Ph.D. students make the mistake of trying to fulfill all of their distribution requirements as soon as possible. But this makes the beginning of the Ph.D. program feel like an extension of undergraduate education. Better to take the courses over time and get involved in research as soon as possible.

I did receive my Ph.D. in Applied Mathematics and didn't have a systems requirement. But I did take systems classes as an undergrad and during my first year at Berkeley and I did extensive programming in high school and during my undergrad days. Programming has helped me tremendously in my research. Putting together old theorems to make new theorems is not unlike making different pieces of code work together.

One might also ask why theory students should take AI courses? I'll leave that to a future post.

8:43 PM #

Thursday, April 20, 2006

 
One Miserable Year

Posted by Lance

Luca and his commentors get dreamy-eyed over Berkeley but not everyone has such fond memories of that place.

I arrived in Berkeley for graduate school in August 1985. When I went to the off-campus housing office, there was dead silence as hundreds of people looked over a small number of listings. A TV news crew arrived to interview some students who had been looking for months for a place. The ridiculous rent-control laws of the city led to an incredible housing shortage. I ended up moving into a dorm at Mills College, thirteen miles from campus.

The city had a horrendous homeless problem which meant you couldn't walk down the street without being constantly asked for money. Berkeley, home of the free speech movement, was in fact the most intolerant place I have ever been to. Many ads for housing, jobs and the school newspaper required applicants to be "politically correct". And my favorite: A man drops garbage on the front lawn of City Hall, calls it art, and there is an actual debate on whether the town has the right to remove it.

Initially I didn't fit in well socially with the other theory students, partly because I lived so far from campus and didn't have an office my first semester, and party because I didn't fit well into their culture. I broke my finger playing touch football with my dormmates. Some theory students thought I made the story up, how could I be so foolish to play such a game. Others said "serves you right".

I nearly dropped out of graduate school that year. When my advisor, Michael Sipser, decided to move back to MIT I happily followed him.

I did have some good experiences from that year in Berkeley. Many of my fellow graduate students at that time are now some of the leaders in their fields and I consider many of them good friends. MSRI had a special year that year on Computational Complexity with many visitors and seminars. Berkeley hosted STOC and the very first Conference on Computational Complexity (then called Structures), a conference that would become an important part of my life. And I can't deny Berkeley has great food.

The following fall at the MIT theory group picnic we played touch football. I found where I belonged.

1:21 PM #

Wednesday, April 19, 2006

 
Student Weblogs

Posted by Lance

A few days ago I put a look of horror into one of our graduate students when I went up to him and simply said "You should be careful about what you write in your weblog."

The number of weblogs continue to grow and more and more students are starting to put their thoughts online. Many of them write brutally honest opinions of some of their academic and non-academic experiences or just write very silly or nasty stuff about themselves or each other.

You might think that only the fellow students you have told about your weblog read your weblog, but chains of links are easily followed. Many of us also have automated searches; if you link to my weblog or use the phrase "Computational Complexity", I'll see what you have said. If you really want to limit your readership you can put in some password protection and I strongly suggest that you do so.

Luckily for the student above, I just laugh off such weblog entries, but they can come back to haunt you. When you apply for jobs, you will get Googled and your odd weblog entries can count against you. Deleting your entries off the internet does not necessarily make them disappear, they might have been downloaded or cached.

Just remember when you write your next post, the Internet never forgets.

11:53 AM #

Tuesday, April 18, 2006

 
Favorite Theorems: Small Sets

Posted by Lance

March Edition

In 1976, Juris Hartmanis and Leonard Berman defined the isomorphism conjecture: For all pairs of NP-complete sets there is a reduction from one set to the other that is 1-1, onto, polynomial-time computable and polynomial-time invertible. As a corollary to the conjecture all NP-complete sets must have many strings in them. They asked whether there could be any NP-complete sparse sets, where a set is sparse if the number of strings of length n is bounded by n^k for some k.

Steve Mahaney in 1982 settled this second question.

Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis by Steve Mahaney, JCSS 1982.

Mahaney's theorem states that if P≠NP then there are no sparse NP-complete sets.

Before Mahaney, Piotr Berman (no relation to Leonard) in 1978 showed that there can't be NP-complete Tally sets, where a tally set is a subset of 1^*. Steve Fortune extended this work to show that co-NP cannot have sparse complete sets. (These results assume P≠NP.)

To adapt Fortune's techniques for NP-complete sets, Mahaney had to find a way to know when strings were not in the sparse set. If one knew how many strings were in the set, and one found all those strings then you knew the rest were not in the set. Mahaney then just showed you could try all possible sizes of sparse sets. This neat idea of finding what's not there by finding everything that is there played a role in many future results in complexity, most notably in the proof that nondeterministic space is closed under complement.

In 1991, Mitsu Ogihara and Osamu Watanabe give a simpler proof using Left Sets, the set of pairs (φ,w) such that w is lexicographically smaller than some witness for φ. Ogihara and Watanabe's paper also extends Mahaney's theorem to show that a reduction from SAT to a sparse set that asks only a constant number of queries would imply P=NP. Whether a reduction using O(log n) queries implies P=NP remains open, even in relativized worlds.

7:09 AM #

Sunday, April 16, 2006

 
Ham Radios, Coding Theory and the Internet

Posted by Lance

Venkat Guruswami talked at TTI last week giving an overview of recent work in list decoding. Someone asked him about practical applications of his work and he mentioned ham radio operators now able to error-correct signals bounced off the moon.

My memories of ham radio go back to summer camp. As one of the activities, we could go to a trailer with the Ham Radio Guy (who looked something like this) and we would try, not always successfully, to reach other ham radio operators around the world using Morse code and occasionally voice. Plastered around the trailer were postcards from other ham radio geeks he did talk to.

Ham radio was sort of a precursor to the Internet, which begs the question—Why hasn't the Internet made ham radio obsolete? You get much better bandwidth over TCP/IP than bouncing signals off the moon and you don't need a license to use the Internet.

8:04 AM #

Friday, April 14, 2006

 
The iCal Effect

Posted by Lance

The iCal standard allows sharing of events and calendars. The standard has been around for many years and has been popular with Apple users but the new Google Calendar will become the first popular cross-platform system to support the standard. While several sharable calendars already exist, we should see a dramatic growth in the use of this standard.

How would I like to see the iCal standard work in our community?

• Academic Departments can put their seminar calendar in the iCal format. No longer would I have to subscribe to email list to see events and then have to enter the events that I care about into my calendar manually.
• Any email that announces an event or meeting should have an attachment I can click that adds it to my calendar.
• Conferences could create calendars listing the important dates (submission, notification, proceedings version, registration) as well as the dates of the conference, perhaps even having the schedule of talks in iCal format with links to the papers. (I don't think iCal supports links but hopefully some later version will).
• One might also want a theory iCal calendar listing all conferences but this would likely have too much information to be useful.
• I have wasted much time trying to schedule meetings. Ideally I'd like a system that searches everyone's calendars and finds a common free time.
• As with many standards there are some great applications not initially anticipated but will develop over times.

Google with this Calendar and also their Talk program embrace standards where other related companies have not. Early standards like FTP, SMTP (email), HTTP, and HTML have allowed the Internet to grow to the force it is today. The RSS standard has allowed sharing of information in unprecedented ways. The iCal standard will help us save time scheduling time.

8:31 AM #

Thursday, April 13, 2006

 
Microsoft Academic Search

Posted by Lance

Microsoft just announced their Academic Search, a direct competitor to Google Scholar. Scholar is incredibly useful at tracking down electronic versions of documents but using it to find bibliographic information can be frustrating. Here Academic Search shines, hold your mouse over an entry and the right pane gives the bibliographic information including abstract and you can also get a Bibtex or Endnote version. But actually downloading a paper requires more clicks than Google.

I tried some random searching and Academic Search is missing many papers. But it does index some Elsevier papers, where Google never got the rights. But there is a back door in Google via ACM. For example, do a Google Scholar search on Occam's Razor, click on the Blumer et. al. paper and it will bring up the ACM Digital Library page that indexes the Information Processing Letters article. Click on the DOI bookmark and it will take you to Elsevier's page.

In short Microsoft has the much nicer interface but not yet the breadth of articles. If your sole goal is to download the paper, better to use Google.

A little less related to academics, you might want to check out Google's just released Calendar. Looks impressive.

6:54 AM #

Wednesday, April 12, 2006

 
Gödel Prize

Posted by Lance

The EATCS has announced the winners of the Gödel Prize: Manindra Agrawal, Neeraj Kayal and Nitin Saxena for their paper Primes in P.

I started this weblog shortly after the announcement of the Primes in P result which was the topic of my third post. Now the result has won the award for best recent journal paper. Either that was a very quick process or I have been writing this weblog too long.

7:09 AM #

Tuesday, April 11, 2006

 
What Math to Take?

Posted by Lance

A good reader question.

I was curious if you had any discussions on what kind of math background new graduate students need to have? For instance, if the undergraduate institution did not have a good math program to support the CS curriculum, what specific topics should students self-study before going to graduate school?

Most importantly you should have some familiarity with mathematical proofs. Mathematical maturity is more important than specific knowledge in any single topic.

Theoretical computer science is mostly discrete mathematics and other areas of discrete math play an important role: Discrete probability, combinatorics, algebra especially group theory, logic and number theory.

Depending on your interests analysis, measure theory, topology and algebraic geometry might be important. Almost every branch of mathematics has played some role in theoretical computer science.

I don't mean to scare you. As I said best to take any real math course (one with proofs, not just Plug-and-Chug Engineering math) and you can later pick up more specific math knowledge when you need it.

6:33 AM #

Sunday, April 09, 2006

 
Reviewer Ethics

Posted by Lance

When you are asked to referee a paper you need to follow a set of ethical guidelines that are rarely spelled out and often ignored. Here are the rules as I see them.

The same ethical rules apply to refereeing papers or reviewing manuscripts for conferences. By "editor" I mean whomever asked you to referee or review the paper.

You should not review a paper co-authored by yourself, a member of your institution, someone you are related to, or having relations with. It is fine to referee papers by recent co-authors or by your former advisor or students. The conflict rules are not transitive, you can referee a paper by someone else at your brother's institution. If for any reason you do not feel you can give an unbiased review of the paper, discuss your issues with the editor or just refuse to referee the paper.

You should only discuss the paper with the editor. The fact that you are a referee, or even that the paper was submitted is confidential information. You should not ask someone else to look at any part of the paper without the editor's permission. You must never ever contact the authors directly.

If the paper has not yet been publicly announced, you must follow Rule Number One

Other than reviewing the paper you must ignore the paper completely for any other purpose, including your own research, until the paper appears.

If you find a simple extension or simplification of the paper: Tell the authors through the editor, they will likely add it to their paper and give you credit through a nice acknowledgment to the "anonymous referee."

If you find a significant extension to the paper: Shame on you, you have already violated Rule Number One. Best thing at this point is to wait until the paper appears and then write your extension. If the authors or someone else beats you to it, or the papers never appears, that's what you get for violating Rule Number One.

You also have put yourself in a messy situation since you are now no longer unbiased in the outcome of the paper. If you think there is a significant extension, mention the possibility in your report or keep it to yourself but don't work on it. It only leads to trouble.

10:33 AM #

Thursday, April 06, 2006

 
The Life of the Party

Posted by Lance

From Jay Leno's monologue on Monday's Tonight Show

Scientists have been working on a device that will tell when you are boring or irritating in social situations. Who really needs this device?…Scientists.

Normally I'd complain about such stereotypes, but social grace is just not one of our strengths.

7:50 AM #

Tuesday, April 04, 2006

 
How Many Students?

Posted by Lance

From an assistant professor comes a question

How many Ph.D. students should a professor advise?

There is no single answer. The usual constraints are time and money. It depends on one's teaching, administrative and other time constrains (such as advising Master's and Bachelor students) as well as the ability to fund such students. Also how do you count part-time students, students not in residence, students you officially or unofficially co-advise and students from other schools who are long-time visitors at your institution.

I ideally like to advise three full-time Ph.D. students at any one time. More and I find it difficult to find interesting research problems for the students and not enough time to properly help their research along.

Some professors can handle more students, some should never advise any students. Particularly in the more applied areas of computer science, professors need a considerable number of slaves graduate students to help them with their projects. It's much easier to tell someone what to code than what to prove.

4:42 PM #

Monday, April 03, 2006

 
The Terror of the Unabomber

Posted by Lance

Ten years ago today federal agents went to a remote cabin outside Lincoln, Montana to arrest one Theodore Kaczynski, also known as the Unabomber.

Just a couple of months before I started graduate school at Berkeley in 1985, one of the students in that department, John Hauser, picked up a package in the computer science lab that detonated and cost him some fingers and his vision. We all had heavy warnings about opening packages during orientation, what a way to start graduate school.

I didn't think much about the Unabomber again until 1993 when Yale University CS professor David Gelernter was injured when a package exploded in his hands. At this point the FBI sent major alerts to all of the CS departments including Chicago and started interviewing faculty about former students. The Unabomber became the main topic of discussion and many of us became very careful about opening any package until his capture in April 1996.

Many students today have never heard of Kaczynski or the Unabomber as he safely spends the rest of his life behind bars. But this mathematician turned bomber made us quite scared and paranoid back in the mid-90's.

7:35 AM #

Sunday, April 02, 2006

 
Baseball is Back and All is Good in the World

Posted by Lance

The Chicago White Sox have raised their championship banner and started a new season with a rain-delayed win.

A team wins the World Series, their first in 88 years, and the main story in the following spring is whether they can win it all again. Similarly, you could prove a major theorem, answering an 88 year-old question, and a few months people will ask what you've done lately.

9:11 PM #

Archives