How to Write Up Major Results

First some conference news: FOCS conference and hotel registration available on line, early deadline is September 30. STOC 2011 website is up with the CFP, deadline November 4. For more news follow the SIGACT Twitter or Facebook.

Deolalikar's paper caused a stir in the community partly because it was written better than the usual P versus NP proofs we see. But the right comparison is to papers that have settled major questions, such as Agrawal, Kayal and Saxena's Primes in P and Omer Reingold's Undirected s-t Connectivity in Log Space.

Both those papers needed to be convincing right off the bat and they both were. First notice the algorithms (page 3 in AKS and pages 9-12 in Reingold). No vague outline, no "should be able to", just very specific algorithms that one can analyze. Reingold only uses one "clearly" for the simple initial transformation from an adjacency matrix to  a rotation map.

Both papers have to make two arguments, that the algorithms work in the claimed time/space and that they work correctly. In AKS, Section 4 shows the algorithm works correctly and Section 5 (using Lemma 4.3) show the algorithm runs in polynomial time. Section 4 is broken into a series of lemmas, each easily checkable with a limited knowledge of algebra. In Reingold the tricky part is getting the algorithm exactly right so that is uses logarithmic space which is carefully analyzed in his Sections 3 and 4. The correctness proof (based on earlier work) is a rather short Lemma 3.2 but Reingold does go over much of that background in Section 2.

In both these results it took an amazing ingenuity to discover these algorithms, but it wouldn't take more than an undergraduate math major to check the proofs.

Showing that P ≠ NP will be a much more difficult task, instead of coming up with a single algorithm, one has to show that no possible algorithm can solve some specific problem in NP. But even though the proof will be harder, the write-up needs to be just as understandable and easy to follow as AKS and Reingold. The community needs a proof we can verify step by step so that we can either be convinced of the proof or find the problem in the proof. If there is a jump in logic that one cannot verify the author has failed in his or her write-up.

Proving P  ≠ NP will require pure genius but you shouldn't need a Fields medalist to verify the proof.

CS Happenings

Yesterday I was at a meeting of the CCC Council, add in a couple of emails and I have lots of short notes on CS stuff.

In these meetings I get to hear about CS research beyond theory: High-performance (i.e. very fast) computers, computing at the margins (guess what it is before you click), CS roles in energy and health and the debate on the Venn diagram of robotics and cyber-enabled physical systems. Question of the day: If you walk in a room and a sensor turns on a light, does that count as a robot?

Did you know that you can plug devices into a single spigot and electrical outlet and via machine learning techniques determine water and electrical activity in your home. Sure there are real applications for energy conservation but how about the automated Facebook posts.

Lance has just flushed the toilet but failed to turn off the bathroom lights.

Ed Lazowska send around a 1998 piece by Bob Lucky on electrical engineers with the worry that CS might not be far behind.

Projecting the current trends, future computers will consist of a single chip.  No one will have the foggiest idea what is on that chip.  Somewhere in the basement of Intel or its successor will be a huge computer file with the listing of that chip.  The last electrical engineer will sit beside the file, handcuffed to the disk drive like a scene out of "Ben Hur."  That engineer will be extremely well paid, and his or her every demand will be immediately satisfied.  That engineer will be the last keeper of the secret of the universe: E = IR.

The NRC Graduate Assessment Report will be released on September 28. What will be the top ten CS departments? The report won't tell you, rather giving multiple ranking ranges based on five-year old data. Prepare to be disappointed.

Slides from the Snowbird meeting I posted about in July are now available including a vidcast of Sally Fincher's wonderful talk on CS education. On the topics of talks, you can now watch the video of the STOC tutorial talks and ICM Talks (see also Gowers).

Richard Beigel asked me to pass the following note:

PIs who receive awards or funding increments after January 3, 2010 will be required to upload a Project Outcomes Report within 90 days after their award expires.  These reports are for the general public and will not be edited by NSF.  PIs will be able to follow a link from fastlane in order to upload their reports.  Because public support for science is very important, I would ask PIs to polish these reports and include images (with permission from the owner). To the best of my understanding, NSF PIs can continue to upload all required reports via fastlane and can ignore the login instructions in the link for grants.gov. 

Intelligent questions about the alleged P NE NP proof

People have asked me how much the alleged proof of P NE NP was discussed at Barriers II. Actually, nobody discussed the proof; however, we did discuss the aftermath. Most of the discussion was about the same questions I had posted a few days ago. In fact, here is a direct quote: Your post mixed interesting questions, which were ignored, and stupid thoughts, which is all anyone commented on. Why don't you repost just the interesting questions?

SO, here is that posts questions, minus the stupid things I said, plus things I heard at the conference.

1. Why did this proof get so much attention before it was verified? Because Lipton and Cook took it seriously.
2. Was this all good for the community? YES- more people know what P vs NP is. YES- if Gowers and Tao now begin working on it more. YES- stone soup.
3. Do mathematicians care about complexity theory? The answer is surely yes, but how strongly? Is the answer yes or Yes or YES or HELL YES! ? If you count number-of-mathematicians then its hard to say. If you take a weighted sum based on quality of mathematicians then Gowers and Tao alone make the weighted sum enormous. In any case, when did the change happen? Was it drastic or slow?
4. If someone claims to prove a big result and its public and problems are found with the proof, should they retract? If so then by when? One thing problematic with the question is the word should. Should for the good of the field? Should for the good of ones own career? Should if you want to be taken seriously? If someone has minor mistakes and just needs a little more time to fix them then a retraction is not needed. But the terms minor mistakes and a little more time are not well defined.
5. How much progress has been made on P vs NP? Scott thinks so. (See the talk Has there been progress P vs NP which is on his homepage.)
6. Have there been hard math problems that were solved all-of-a-sudden without any real prior results or plan? Finding and intermediary c.e. degree was such a problem, but it wasn't anywhere near as hard or as important as P vs NP.
7. What criteria SHOULD we use to determine if a proof of a major result is worth looking at?
8. What criteria DO we use to determine if a proof of a major result is worth looking at?
9. Has Descriptive Complexity Theory been ruled out as a way to solve P vs NP (something like oracles or natural proofs)?
10. The story about the story has reached the New York Times: here

Report from Barriers II Part 1

On Thursday Aug 26 Lance stated Bill is at Barriers II in Princeton and promises a full report upon his return. Not quite sure I promised that, or what a full report would entail, but here goes.

1. When I first heard there would be a BARRIERS II workshop I assumed it would be full of Oracle results, Natural Proofs, Algebrazation, maybe some speculation on independence results (I do not think we have any right now). And indeed, this was at least part of the agenda for Barriers I. (See here for a blog about Barriers I.) Barriers II was (1) Approx algorithms and lower bounds, (2) Crypto, (3) Quantum Computing, (4) Communication Complexity, (5) Geometric Algorithms (NOTE- NOT Ketan's Geometric Complexity Theory program). However I can't say it was false advertising since the program was on the web early enough that one could see what one was getting into. It was misnamed.
2. The organizers told me that it was called Barriers because the speakers were urged to talk about where the field is and where it is stuck. I think talks like that have a name already: Open Problems, or Directions or whatnot.
3. All of that aside, how was it? It was WONDERFUL!. The talks were uniformly good. They were mostly survey-talks so one outside the field could follow them (that was the intent). This also lead to the following oddity: the day on (say) Quantum had very few quantum people at it (except the speakers) since your standard quantum person has probably heard the talks before or at least knows the material.
4. Approx Alg and lower bounds: I was inspired to actually learn what Semi Definite Programming and Iterative Methods are. I finally understand the UGC and its different formulations. Dana Moshkovitz gave a nice rump session about a promising route to PROVE UGC. This was not one of those we doubt it will work but the approach is still interesting talks (this could be a rallying cry for our field) but seemed like a real plan.
5. Crypto: Lattice stuff and also stuff about: If your key leaks slowly can you still do crypto? (yes).
6. Quantum: Scott introduced the speakers and was the first one. He had a slide warning us to NOT PANIC at the mention of Quantum. All of the talks were outreach--- why complexity theorists should learn quantum methods. I blogged about this non-technically here. One key point I will re-iterate: Even if you don't work in quantum computing you will need to learn their methods. (Analog: even if you don't work in prob you need to know the prob method.) Over dinner we noted the following: there are many quantum books for the layperson but there are few (none?) complexity books for the layperson (hurry up Lance!). Why is this? Quantum seems less abstract then Complexity and some laypeople may thinks they have a notion of it. They may be wrong.
7. Communication Complexity: Paul Beame gave an hour long talk where he went over the entire Kushilevitz-Nisan book. (NOTE: This book is on Lance's list of favorite computational complexity books.) How did he do it? He skipped some stuff. (I recommended talking fast. Fortunately he didn't take my advice.) The other talks were applications of Communication Complexity to lower bounds on data structures (not quite- some of the lower bounds didn't use Comm. Comp.), data streams, direct sum problems, and a talk on quantum comm. comp. This raises the question: Is Communication Complexity only interesting when it applies to something else, or it is interesting for its own sake? I proposed the following open problem in a rump session, though it seems like its already out there (that is, its not really MY open problem).
   

   Alice has x, Bob has y, both are n-bits long. We are promised that PARITY(x)=0 and PARITY(y)=1. Alice and Bob want to find i such that x_i ≠ y_i with d rounds (d a constant) and O(log n) bits-per-round. Show they cannot do this. ANSWER: We already know this statement is true since it is equivalent to PARITY ∉ AC₀. (Using Karchmer-Wigderson games, another game that is not much fun.) However, I would like a communication complexity proof of this which would give an alternative proof of PARITY ∉ AC₀. In particular it would give a top-down proof instead of a bottom-up proof.

8. Geometric Algorithms. Paul Beame said that this session would be a nice counterpoint to the communication complexity talks since the Geometric Algorithms session would prove some upper bounds on problems that the Comm. Comp. Session proved lower bounds on. (Mike Sipser once told me It is good to do an algorithm as a sanity check on your lower bounds.). Alas I had to take off that morning so I don't know if this really happened; however, I assume that it did.
9. Not much talk about the alleged P NE NP proof; however, I will discuss what was discussed in my next blog.

New Institute for Theory of Computing

The Simons Foundation has announced a competition to establish a new Institute for the Theory of Computing in the United States.

Computation (and its abstract form, the algorithm) has not only revolutionized science, technology, and society, but also is among the most important scientific concepts discovered and developed in the 20th century. This scientific discipline has enabled numerous technological advances and has forged many connections to mathematics and other sciences, providing fruitful insights and new problems. It has impacted not only computer science and technology, but also parts of mathematics, physics, biology, economics and sociology. Meanwhile, its core scientific agenda is extremely ambitious and challenging. In short, this theoretical field is one of the most exciting and important today, attracting excellent young talent to its ranks at a growing rate. Young people with education and training in this field are well positioned to make central contributions to computer science and science in general.

An institute focused on the theory of computation could bring together a critical mass of researchers from around the world to accelerate fundamental research on computation and to further develop its interactions with other areas of science ranging from mathematics and statistics to biology, physics and engineering. The Simons Foundation invites applications for grants to establish such an Institute.

Letter of intent due by October 27 and full proposals by next June.

It's the funding that catches the eye, $6 million/year for 10 years with possible renewed funding or endowment after that. To understand the scale, that's roughly the budget of TTI-Chicago. This new institute will play a major role in our field.

The institute will be modeled on the Kavli Institute for Theoretical Physics, MSRI and the IMA (also similar to DIMACS) which are located at or near major university campuses and host programs on a given topic for several months to a year with long-term visitors and have several workshops related to those program topics.

This is opposed to the Oberwolfach/Dagstuhl/BIRS model of an isolated location with on-site room and board, weekly workshops but little to no long term programs or visitors. I'm glad the Simons Foundation is going with the former model. While I've enjoyed the many Dagstuhl workshops I've attended, centers like DIMACS tend have a greater long term impact on the field.

Where will this institute be located? We'll find out next fall. Should be exciting.

Theory Journals

I got the following request from a reader.

I have a question about TCS journals. As I am trying to follow your advice on being more diligent about journalizing my papers, I realized that I am surprisingly ignorant about where to send them. A couple of more senior colleagues I asked didn't really have the answers.

What are the journals that accept theory papers? What's their specialization (if any)? What's their relative quality/reputation? What's the expected turn around time for each of them? Anything else I should be asking?

Sounds like a list that should be on a site we can edit in the future like Wikipedia and in fact they have such a list. It can use some additions, links, publishers and specializations if anyone is so inclined to help update it. Most of these journals cover general theory unless their title indicates otherwise.

For reputation I put JACM first, followed by SICOMP, followed by a rough equivalence class of the most of the others. Information Processing Letters has only short papers, good for a result that has a simple proof but still worth writing up.

Turn around time depends more on the editors and the referees than the particular journal. The average time from submission to publication (assuming no major issues found in the referee process) is a bit over a year with a very large variance. Feel free to ask/bug the editor if you need faster publication. 

Another big issue to consider is which publisher to choose. It can affect who can access your paper, where it will be indexed and archived and how and whether the paper will appear in print and/or on the web. I'm a (biased) fan of the ACM with its well-organized low-cost digital library but there is something to be said for open-access journals.

Cryptography if P = NP

Bill is at Barriers II in Princeton and promises a full report upon his return.

Ask many computer scientists what happens if P = NP and you'll get the response that it will kill cryptography. Let's ignore solving all optimization problems, solving AI and learning everything, likely cures to many diseases and many more amazing advances in society, what a disaster it will be that we can't send secret messages to each other.

I don't at all believe P = NP but let's have this hypothetical discussion of what happens to cryptography in that world. We do lose public-key cryptography, the ability for two people who have never met to electronically still send encrypted messages to each other. How will I send my credit card info to Amazon if P = NP?

Amazon will send me a USB key containing a gigabyte worth of a one-time pad, enough to encrypt all my transactions for my entire life (even though I will live much much longer thanks to P=NP). This might work for Amazon but what about tiny mom and pop web stores? We just need a trusted site for a one-time pad registry so my USB key will work for any Internet transaction. Even for public-key cryptography today we need trusted parties to verify sites so we haven't lost much here.

For large financial institutions they can ship huge amounts of one-time pad data through secure couriers (or just ship data this way). Large amounts of compressed data can have a very small footprint these days.

What about cryptographic protocols? Zero-knowledge is uninteresting if P = NP. Many secure multi-party computations can be done with private channels which just need private keys. There are many others, electronic money, secure voting and digital signatures come to mind, that seem difficult to do if P = NP. On the other hand they are also hard to do in practice today even under the usual assumptions.

Certainly P=NP will make cryptography considerably more painful that it is now and many things we thought previously encrypted won't be anymore. But we'll figure out how to meet our crypto needs in any environment. The loss of public-key cryptography shouldn't be our first gut reaction to what happens if P = NP.

***SORELLE*** PHD!!/Workshop on Boolean Threshold Functions/NSF program

Three annoucements (the last two I was asked to post)

ANNOUCEMENT 1: Congrads to fellow blogger ***SORELLE*** who got her PhD recently. I was on her committee. She did a masterful job of presenting it. It looked like theory that can be applied to stuff. At least Google, who hired her, might think so. Or they might think (correctly) that she is smart and knows things so she can help them. See her post about her PhD for more information and a pointer to her actual thesis.

ANNOUCEMENT 2: Rocco Servedio and Ryan O'Donell have requested that I post about upcoming workshop at the Center for Computational Intractability in Princeton.

The topic is Analysis and Geometry of Boolean Threshold Functions. It will take place the Thursday and Friday morning before FOCS, Oct. 21--22. For detailed information, please see: here There is also a poster here.

COMMENT FROM GASARCH: Its right before FOCS but its NOT close to FOCS. It is in Princeton NJ. FOCS is in Las Vegas. Not sure this makes sense but I suppose they will find out.

ANNOUCEMENT 3: Tracy Kimball at NSF has requested this annoucement be posted.

CISE has announced a new funding opportunity administered jointly with the Directorate for Social, Behavioral and Economic Sciences (SBE). The new program is called ICES (Interface between Computer Science and Economics and Social Sciences). You'll find the all the details about ICES here. Be sure to read the whole solicitation and click through to the non-exhaustive list of example topics as well. ICES seeks to fund interdisciplinary work at one particular boundary between computer science and economics & social sciences. As always with anything new at NSF, there will be lots of questions. Email CISE/CCF Program Director Tracy Kimbrel (tkimbrel@nsf.gov), SBE/SES Program Director Nancy Lutz (nlutz@nsf.gov), CISE/IIS Program Director Sven Koenig (skoenig@nsf.gov), or CISE/CNS Program Director Darleen Fisher (dlfisher@nsf.gov) and we will do our best to answer the questions. If you're wondering Is my project suitable for ICES? be sure to include a one or two page description with your email because that will help us with the answer. The deadline for submitting proposals to ICES is October 5, 2010.

NEW math on Futurama

The Aug 19, 2010 episode of Futurama had NEW math in it! It also has some other math refs.

1. This website claims that Ken Keeler, one of the writers who has a PhD in math, devised a NEW theorem for use in the show. The theorem and proof are here. I do not know if it is new but it is correct and interesting.
2. Bender the robot had mind switched with Amy, so he was in a human body. In order to prove that he was really a robot he had to pass the reverse Turing Test.
3. Since PURE MATH lead to a solution of a PRACTICAL PROBLEM The professor exclaimed And they say pure math has no real applications!

This is the first time I know of where some new correct math was introduced on a fictional TV show. NUMB3RS often had new bogus math.

Both The Simpsons and Futurama have websites devoted to math refs in the show: Simpsons Math, Futurama Math.

It is not surprising that The Simpsons and Futurama have math refs since writers Jeff Westbrook, David X. Cohen, and Ken Keeler who write for these shows, are all math folk.

See these two prior posts for more on comedy and math.

Is Scheduling a Solved Problem? (Guest Post)

(Guest Post by Ben Fulton.)

"At first glance, scheduling does not seem like a topic that requires much attention from computer scientists".

This was how I wanted to start my review of a book on scheduling, but Bill Gasarch called me out on it.  "Really?" he said.  "I don't know any computer scientists who think scheduling isn't important."  It's true but computer scientists aren't the ones taking first glances at scheduling problems.

They're curriculum designers trying to determine which instructors are needed to teach all of the classes for the fall semester.  Shop managers wondering how the widgets could be sent through the assembly line more efficiently.  Kids on the playground choosing up sides for a soccer game (a problem identical to partitioning a set of jobs with known running times between two processors).   These are the people with scheduling problems.  They'll think about their problem for a few minutes, and come up with a good solution in each case.

The curriculum designer - possibly Michael Mitzenmacher  - might decide that the most important goal is to keep all instructors at around the same number of teaching hours.   In that case, each next available assignment would be given to the least busy instructor.   In doing so, he'll choose the List scheduling algorithm first proposed by Graham in 1966 and known to be no worse than twice as slow as an optimal schedule.

The kids will choose Greedy.  They'll choose a couple of captains and alternate picking the "best remaining" player, in the same way that a scheduler would choose the "largest remaining" job.   Greedy is a heuristic that runs in polynomial time.  It's not guaranteed to find the best solution it's The Easiest Hard Problem but the kids are interested in having competitive teams, not making sure that all possible sets of children can be perfectly divided in polynomial time.

The shop manager is likely to have a lot of different constraints to take into account, but she might notice that a station can stop working on one widget and start on another one, if the second is likely to be finished more quickly.  She probably won't realize it, but the Shortest Remaining Processing Time algorithm is known to optimize the average time to completion of the widgets.

In all three cases, the algorithms they choose are simple, easy to describe, and should work fairly well in their situations.  The schedulers aren't computer scientists - just people with problems to solve.   They'll take a first glance, and they'll solve them with a minimal amount of effort.  Even if you showed them a way to solve their problems that was twice as efficient, but also much more difficult to understand, they'd probably reject it.

So what's the point of studying scheduling?  The practical problems are solved. 

That's the first glance.  You've got to dig a little deeper to find the interesting problems in scheduling.  For example, the complexity of simply describing scheduling problems is a subject that hasn't fully been explored yet.  Problems are typically broken down three ways: the number of processors available; the constraints on when jobs can be run; and the criteria for determining whether one schedule is better than another.  Even if the first and third items are fairly simple, setting up a job precedence graph, lag times, and perhaps a few rules involving a specific processor needing to run a specific job, will likely generate a description so complex that an engineer trying to solve the problem might not even recognize it.

Scheduling gurus Anne Benoit, Loris Marchal, and Yves Robert also ask this question.  In response, they outline some areas of study involving distributed-memory parallel computing that could give rise to some interesting practical improvements. 

That's where you go when you're past the first glance.   And that's why computer scientists need to pay attention to scheduling.

 

Comments

Bill and I are strong believers in freedom of speech and have long since had an open comment policy, allowing anonymous comments, no moderation (except old posts for spam) and never deleting comments (again except for spam). This has allowed our blog to serve as a public forum for the community giving a place where people can express their opinions openly.

The level of nastiness has dramatically increased in the last couple of months, but we've maintained this policy believing everyone should be allowed to share their opinion, whether it be good, bad or ugly. But some seem to be purposely incendiary instead of giving a real point of view. Please keep comments civil and on topic so this blog can continue its long role where we can have fruitful discussions of the important issues and ideas in computational complexity and theoretical computer science.

NSF Updates

Many changes at the National Science Foundation both in programs and personnel. Some highlights of upcoming CISE programs.

• Expeditions is moving to an 18-month cycle but this year's preproposal deadline is September 10. Last year's awardees have yet to be announced. (Update: Just announced)
• The CCF Core (traditional theory grants) have three deadlines: September 15 (medium), November 28 (large) and December 17 (small).
• A new program Interface between Computer Science and Economics & Social Science (ICES), proposals due October 5. This program came out of a workshop held at Cornell last fall and its report.

Unlike conference deadlines, NSF and other grants change frequently. If you are a US academic you should subscribe to the CISE emails and RSS feeds (see here) or check the Theory Matters Funding Page often.

For personnel, let's work our way up. Richard Beigel, a theory program director, is finishing his term and heading back to Temple. There was a part-time replacement chosen but looks like that will be delayed. Might be a slower turn-around on theory grants this year. Tracy Kimbrel stays on as a program director.

Susanne Hambrusch will become the new director of CCF, the division of CISE that funds most of theory. Susanne replaces Sampath Kannan who is returning to Penn. 

The search for a new CISE head (called Assistant Director) to replace the already departed Jeannette Wing continues but no announcements yet.

MIT Engineering Dean Subra Suresh has been nominated by Obama for NSF Director and awaits congressional approval. 

The NSF budget process for next year looks good so far but there has been talk of a congressional freeze on most domestic activities. The NSF is preparing for both possibilities.

Spielman Receives the Nevanlinna Prize

Dan Spielman wins the Nevanlinna prize for "smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to Numerical Computing." Let's also not forget that as an undergrad Spielman co-authored one of my favorite complexity results, PP is Closed Under Intersection. A nice recognition for just a brilliant career.

Other IMU prizes awarded at the ICM opening ceremonies in Hyderabad, India: The Field medals go to Elon Lindenstrauss (Ergodic Theory), Ngô Bảo Châu (Algebraic Geometry), Stanislav Smirnov (Statistical Physics) and Cédric Villani (Mathematical Physics). The Gauss Prize goes to Yves Meyer (Number Theory) and the first Chern medal goes to Louis Nirenberg (Differential Equations).

Tim Gowers is blogging the meeting and the ICM is offering live streaming of the plenary sessions. The Nevanlinna Prize lecture will be given Saturday at 4:15 AM Eastern time. Also notable is Irit Dinur on PCPs at 12:45 AM Eastern Saturday morning.

Today is Paul Turan's 100th Birthday!

The following conversation is a fictional version of a real conversation.

Lance: Bill, Wed August 18, 2010 is Paul Turan's 100th birthday. We should post on it.

GASARCH: WOW, he's still alive? Will there be a conference in his honor? Will he go to it? Will he enjoy it? (ADDED LATER FOR CLARIFICATION: Noticing that Lance's mention of Paul Turan is actually a pointer to a Wikipedia Entry on him.) Lance, I see you have one of those gizmos that lets you insert pointers into your speech.

Lance: Uh, Paul Turan is dead, but if he were alive it would be his 100th birthday. And of course I have one of those gizmos--- I am a firstblocker

GASARCH: Even though he is dead can we still celebrate? Is there cake someplace? How about a free lunch?

Lance: No cake. And the economists I hang out with say there is no such thing as a free lunch. But we should post about it.

GASARCH: Okay. I know a nice proof of Turan's theorem and two applications, so I'll post about it.

When Lance first asked me to do this post my first reaction (after I found out there would be no cake or free lunch) was Paul Turan- Turan's theorem in graph theory. I know a nice proof of it that is not on Wikipedia. I also know two applications of Turan's theorem that I don't think are well known. I'll write those up as part of my post. (I will do this later in the post.) But then I looked at his Wikipedia Entry and I saw that he did so much more than graph theory. He also worked in Analysis, Number Theory, and Analytic Number Theory. Moreover, Wikipedia claims that Number Theory was his main interest. In addition he, along with Paul Erdos, made the Erdos-Turan Conjecture which has inspired so much later work (I will state it later.)

Is it good to have a theorem named after you? While we would mostly think YES, it may overshadow all of your other work in peoples memory of you. On the other hand, if it was not for Turan's theorem I would not know who he was and I doubt Lance would ask me to post on Turan's 100th birthday.

Is it good to have a conjecture named after you? It is so long as its open. Once someone proves it your name will vanish from the literature. Just ask Baudet or Vazsonyi (Baudet's conjecture is now van der Warden's theorem, and Vazsonyi's conjecture is now the Kruskal Tree Theorem.)

Turan's theorem:

If G is a graph with n vertices and e edges then G has an independent set of size at least n²/(2e+n)

Here is an application:

If S is any set of points in the unit disc (including the boundary) then there exist n²/6 - n/2 pairs of points such that each pair is of points that are ≤ sqrt(2) apart.

Here is my write up of a nice proof of both Turan's theorem and the application. The proof is from the Alon-Spencer book on Prob method. I do not know whose proof it is. (ADDED LATER: The proof is due to Ravi Boppana- see the comments.) I don't know where I read the application; however, it was by Paul Turan. If you know of other applications please leave comments about them.

Here is another application:

Assume you want to find the MAX of n elements and you get to ask k rounds of questions. It is know (without Turan's theorem) that you can do this with O(n^{(1+(1/(2k-1))}) questions-per-round. Using Turan's theorem you can show this is optimal. (The exponent is 1+(1/(2^k-1)) in case its hard to read.)

A write up of the case of k=2 is in the manuscript pointed to above. Once you read that you should be able to generalize it to k rounds easily.

The Erdos-Turan conjecture is the following:

Let A be a set of natural numbers. If Σ_{x ∈ A} 1/x diverges then A has arbitrarily long arithmetic sequences.

Some have suggested that this replace Poincare's conjecture on the list of Millennium prizes. See here for more on the conjecture.

My last post on the alleged P NE NP paper

(This is likely my last post on the alleged P NE NP paper unless more real news on it occurs. The only real news I can see happening at this point is a retraction.)

I have not commented much on the alleged P ≠ NP since I was waiting for better informed or more opinionated people to comment first. Now that the dust has somewhat settled here are some views of points of view and some pointers to points of interest.

1. The best places to read about the technical details of the problems with the proof are Lipton's Blog Entries: here, here, here, here, here, here and the Wikipedia entry here.
2. Some people are saying that Scott's post was nasty. Here is an excerpt from Scott's post:

   What's obvious from even a superficial reading is that Deolalikar's manuscript is well-written, and that it discusses the history, background, and difficulties of the P vs. NP question in a competent way. More importantly (and in contrast to 98% of claimed P ≠ NP proofs), even if this attempt fails, it seems to introduce some thought-provoking new ideas, particularly a connection between statistical physics and the first-order logic characterization of NP. I'll leave it to the commenters to debate whether Deolalikar's paper exhibits one or more of the Ten Signs A Claimed Mathematical Breakthrough Is Wrong.

   Scott, that is downright nasty! Calling a paper well-written!! Accusing it of having thought-provoking new ideas!! Scott, you are just one Nasty dude!!
   
   More seriously, Scotts offer of $200,000 if the proof is correct (more formally, if he wins the Mil prize) was considered nasty by some. Being skeptical and quantifing your skepticism is not nasty.
3. Other posts worth looking at:
   1. Written pre-Deo, Lance now looks like Nostradamus: So you think you've settled P vs NP. (NOTE- personal triumph- I got the spelling of Nostradamus right on my first try!)
   2. A pre-Deo post of Scott's on 10 signs a claimed mathematical breakthrough is wrong. Deolalikar passed most of these.
   3. A post-Deo post of Scott's that was likely inspired by Deo: 8 signs your proof of P ≠ NP is wrong. One of Scott's signs cuts both ways- he says that the use of Descriptive Complexity Theory is one of the signs. He claims (correctly) ... subtle differences in encoding can lead to HUGE differences in computational complexity. Indeed, this was one of the problems with the Deo-Proof. However, I think Descriptive complexity theory is one of the few techniques that has not been proven cannot work. So I take its use as a good sign.
4. Lance was on vacation when all of this happened so he posted on it when he got back. He was skeptical from the beginning and he says why. (See here.) People respond by saying that the paper inspired a lot of interesting discussion, and hence... I'm not sure- Lance shouldn't be skeptical? Lance shouldn't say he is skeptical? Lance should phrase his skepticism more politely? I'm not sure what the objection to his post really is.
5. Is the proof correct? It looks like there are enough serious flaws that the answer for now is no. By now this is old news.
6. I was originally skeptical (see here) since there has been no progress on P vs NP at all so its surprising that there is this much progress so fast. I do not know if this is valid reasoning. Has any serious hard math problem been solved all of a sudden after no progress on it? Has there truly been no progress? We might not know until we solve it in 3000 AD and look back and see which results from 1970-2010 ended up being relevant.
7. Deolalikar should, by Thursday Aug 26, 2010 (the first day of Barriers II) either (1) retract the claim, or (2) post a version that fixes ALL of the flaws found and explains the fixes. If he does neither of these two things then he will cease to be a serious researcher.
8. It would be impossible to have a version that fixes ALL of the flaws by Thursday Aug 26, 2010. Hence he needs to retract by then. (Some would say sooner. Much sooner. Like... now.)
9. Was all of this good for the community? It got some talking and the people who read the proof learned some complexity. If this gets more people interested in the problem, that's got to be a good thing. If some interesting ideas come out of this, even indirectly (e.g., Terry Tao is inspired to read up on finite model theory and comes up with a result of interest) then it will of course be a good thing. However, if more of these proofs come out and the community spends too much time on them, that will be bad.
10. Why did people take this paper so seriously?
    1. It was in LaTeX!
    2. It was long!
    3. It was by a respectable researcher. (More on that later.)
    4. It used familiar notation.
    5. It seemed to have some good ideas in. It may still. (More on that later.)
    6. It was on Slashdot and on Lipton's blog. But this begs the question: why was it on slashdot and why did Lipton take it seriously? Dick- I am not asking this rhetorically- if you read this please leave a comment about why you took it seriously. I am not asking this sarcastically or in any other nasty way. (I know YOU won't think so but other readers might.)
    7. Others took it seriously. Chicken and egg problem here.
    8. It had very few of the usual trademarks of papers written by cranks.
    9. It was a proof in the correct direction (a proof that P=NP would be taken less seriously, though the result, if true, would be more awesome!!!)
    10. In the age of the web, news travels fast (I know of 3 other serious people claiming to have shown P ≠ NP; however, that was pre-web so they were debunked before it got very far. I'm not quite sure which ones went public so I decline to mention their names.)
11. How respectable a researcher is Deolalikar? I do not know any other work that he is done. He is not someone you've heard about as having done excellent work. The fact that some in the community took his work seriously is an excellent sign that our community is not elitist. They took it seriously based on its merits. (The fact that some did not take it seriously is irrelevant.) ADDED LATER: The above was badly written and hence misunderstood. My point is that Deolalikar is not well known to the complexity community and hence the fact that many in the community took his work seriously speaks well of the community (or at least of those people) as not being elitist. Some of us WILL look at ideas from outside of the community.)
12. Are there interesting ideas in it? The answer from the latest comments by knowledgeable people on Lipton's blogs seems to be no. Oh well.
13. In the midst of all of this came the DUMBEST comment on a post of mine EVER!! In a recent post I noted that a recent (2007) article on number theory still referred to factoring as being easy. I meant to imply that this was bad- they should at least acknowledge the issues involved even if they don't care. One of the comments was

    Since when do mathematicians care about the notion of polynomial time?

    Note that this is the same week when Gowers and Tao, two Fields Medal winners, are carefully looking over an alleged proof that P ≠ NP. Other mathematicians were looking at it also. The notion that mathematicians do not care about polynomial time is just so 1990's.

But This One Is Different...

This summer I took a two part vacation: Touring Ireland July 26-August 5, with my wife to celebrate twenty years of marriage and a short trip to Santa Fe, Augut 9-12, to catch opera with my elder daughter. Let's talk about what happened in between.

On Friday, August 6, Vinay Deolalikar sent me and 21 of my closest frinds an email entitled "Proof announcement: P is not equal to NP". I took a quick look and white it did look better that most P/NP proof attempts (in the sense that Deolalikar doesn't make up his own notation), I spotted the following line in his write-up:

Distributions computed by LFP must satisfy this model.

Many P versus NP attempts work by claiming that a polynomial-time algorithm must act a certain way forgetting that an algorithm can completely ignore any semantic meaning in the problem. Since LFP is just a fancy way of saying "polynomial-time algorithm", it looked like Deolalikar fell into the same trap. So I filed the paper into my Why Me? folder as I have with many many others and figured that was the end of that.

As you readers all know, on Sunday the 8th the paper was slashdotted and Lipton, impressed that Deolalikar worked on infinite Turing machines (whatever they are), posted on the proof saying he was "certainly hopeful". People then flooded with me with emails, tweets and instant messages asking me about the paper.

I read over Lipton's post and took another look at the paper and still didn't see the semantic approach outlined in the paper as a viable attack on the P versus NP problem. At this point I knew people I trust would look over the paper carefully so I wouldn't have too. I couldn't keep completely quiet so I tweeted

Much ado about an unverified proof. The word "must" is troubling. I'll let others check it carefully.

In retrospect I should have been more negative. Kudos to Scott for taking a strong and risky stance.

The emails kept coming but I remembered my vacation message was still active and I didn't have to answer them. I went to Santa Fe and didn't check email until I returned.

There are two camps in our community on Deolalikar's paper. Those of us who saw Deolalikar's paper as just another in a long series of bad attempts at P v NP and wondering what all the fuss was about. And those who thought Deolalikar hit upon a new proof paradigm and despite the numerous problems, big and small, with the paper still hold hope something important will come out of it.

Deolalikar at this point should retract his P ≠ NP claim until he can address all these issues. In an email Deolalikar sent out to the gang of 22 on Friday the 13th, he restates his claim and overview of the proof and says he "fixed the issues in the finite model theory portion of the proof". He promises a revised version on his homepage in a couple of days.

Deolalikar is following the script, currently at stage 5 of the 12 stage process. Stage 6 will happen sooner than he expects.

P vs NP vs IEEE (Guest post by Paul Beame)

(Update on P vs NP: The proof uses Finite Model Theory which is sometimes called That stuff that Neil Immerman does.. Neil Immerman has found a flaw in it. See Lipton's Blog for more information. My prediction is still that something interesting will come out of this but NOT P ≠ NP. And for those of you who read my blog but do not follow Lance on Twitter (the empty set?) note that Lance tweeted Much ado about an unverified proof.. Of course, if we all felt that way then who would verify it? A PCP?)

Guest Post from Paul Beame!

While the complexity world is debating how much to invest in trying to extract useful information from the recent attempt at resolving P vs NP, there is another item that may be useful to complexity blog readers who also happen to be members of the IEEE Computer Society which sponsors the CCC, LICS, and FOCS conferences. Voting just opened in the election for IEEE CS officers including the President.

I'd like to alert voters to a write-in campaign for Joe Bumblis for president of the IEEE Computer Society.

As anyone who has run a CCC, FOCS, or LICS knows, the IEEE CS has had a lot of very bureaucratic rules for running conferences. Conferences are run by the IEEE CS Technical Committees (like the TC on Mathematical Foundations of Computing which does CCC, LICS, and FOCS and which I currently chair). These TCs are groups of volunteers who have little power in the current organization of the IEEE CS. These TC volunteers have long chafed against the bureaucracy, often with little response from the main organization. The main officers of the IEEE CS have been from the Publications and Standards part of the organization and these groups dominate the nominating committees. The TC side of the organization has been shut out. IEEE CS ran into financial difficulty for a variety of reasons unrelated to conferences and the result has been more bureaucracy based on the Standards mentality that the way to fix things is to set up more rules, which pit CS staff in opposition to TC and conference volunteers.

This year we finally succeeded in getting the IEEE CS to allow an option that should substantially reduce bureaucracy for conferences like CCC, LICS, and FOCS but the organization still resists anything like the flexibility for TCs that SIGs have within ACM and still is tied to bureaucratic rules. Many of the most active and thoughtful TC chairs have agreed that we need to push a write-in campaign to finally get someone from the TC side in a position of authority and Joe has agreed to serve. Joe has been vice-chair of the board of TC chairs and would bring a very different perspective that has a chance of shaking things up. By comparison one of the other candidates for president recently refused to authorize the LICS 2010 budget as part of the Federated Logic Conference (long after registrations had opened) because it was charging $10 too little for non-IEEE-members (or $8 too much for members, depending on how you count). It took my intervention to expose the ridiculousness of this position before he was overruled.

We need your vote now!

(NOTE FROM GASARCH- as someone who has run a CCC I can VERIFY what Paul is saying without pointing to Lipton's blog or using a PCP.)

Factoring in P ?

(Update on alleged P NE NP proof: There are some issues with it. See these posts on Lipton's blog: here and here and also see a Wikipedia site that (I think) Terry Tao set up here. )

I recently read the following: (Backdrop- the author had already defined p(n) to be the number of partitions of n.) NOTE- I use ki where the actual quote uses k_i. Looks better in html, though I am sure a better htmler than I could handle this.

For a positive integer n let d(n) be the sum of the divisors of n. For example

1. d(4) = 1 + 2 + 4 = 7
2. d(1000)=1+2+4+5+8+10+20+25+40+50+100+125+200+250+500+1000 = 2340
3. d(1001)=1+7+11+13+77+91+143+1001=1344

Unlike the numbers p(n), the numbers d(n) are easy to compute. There is a simple explicit formula for them. Namely, if n=2^k23^k3 ... p^kp then

d(n)=(2^k2+1-1)((3^k3+1-1)/2)...((p^kp+1-1)/(p-1))

They are assuming factoring is easy. Or perhaps they are assuming you are given the number already factored. There are no comments on what easy to compute might really mean, though they seem to think that having a simple explicit formula implies easy to compute.

To be fair, this book was written a while back before people in math really took these notions seriously. The book is Mathematical Omnibus: Thirty Lectures on Classic Mathematics by Fuchs and Tabachnikov. Copyright 2007.

Disclosure: I got my copy for free in my capacity as SIGACT NEWS book review editor.

That P ne NP proof- whats up with that?

Let me be he last on the block to tell you that an alleged proof of P ≠ NP is out there. NOT posting on it would be absurd; however, I cannot do any better than what Richard Lipton already posted so I point you to his post.

So what are my uninformed views? If I was a betting man I would bet that it won't pan out. I would bet that he proved something very interesting, but not P ≠ NP. Why do I think this? This is NOT based on the author who seems to be a person to be taken seriously. Its just that the problem is so hard and we've made no progress on it since... . Hmmm, when is the last time we made progress on it? Parity not in constant depth? Other bounds on weak models? Oracles? Natural Proofs? Something from Mulmuley's program? Fagin's theorem connecting the problem to finite model theory (which is used in the alleged proof)? I would have thought we would make slow progress at first. Not sure what type- Maybe SAT ∉ DTIME(n^k) for small values of k. Maybe something else.

Scott Aaronson apparently IS a betting man. See his post on the problem.

I was going to go to the Barriers in Computational Complexity II workshop. If the proof is correct I hope Amtrak gives refunds.

Actually- looking over the schedule, much of it will still be relevant. If the proof is CORRECT how will that change what we teach? What we work on? Lance's book-for-the-layperson on complexity theory? (I recently proofread a chapter on what the world would be like if P=NP. He may have to remove it. Too bad, it was awesome!)

The Solution to the Mark-Betty Game

RECALL from my last post the following game:

Let f(n) be a non-decreasing function from naturals to naturals. Consider the following game:

Let n be a large natural number. Mark and Betty alternate (Mark goes first) putting M's and B's on an n by n checkerboard. No square can have two markers on it. They play until all squares are covered; hence the game will end after n² moves. If at the end there is some row or column A where the number of M's in A is at least n/2 + f(n) then Mark wins! If not then Betty wins! (NOTE- the M's in A do not have to be adjacent.)

I asked for your intuitions on when Mark or Betty have a winning strategy. Here are the answers and a pointer to my writeup of it. NONE of this is my work- it is all the work of J.Beck (the reference is in the writeup). Here are the results:

1. If f(n) ≤ O(\sqrt(n)) then Mark has a winning strategy.
2. If f(n) ≥ Ω(\sqrt(n log n)) then Betty has a winning strategy.
3. My writeup is here. If I fill in more details it may change.

(NOTE- html's sqrt sign is pathetic. Here is what square root of n looks like: √ n. The sqrt sign has no top! That's why I use `sqrt')

My writeup of the first result is complete. I included more detail then you usually get in a math paper. I do not know if this is good or bad; however, I really wanted to check it all for myself. My writeup of the second result is much sketchier; however, it is essentially Beck's proof.

Beck has a book on games of this nature entitled Combinatorial Games: Tic Tac Toe Theory. Will children buy it thinking it is about tic-tac-toe? Maybe Bill Gates' kids: the book costs $146.00 new and $107.00 used.

I want your intuitions on this, so the less you know the more I want you to post

Let f(n) be a monotone increasing function from N to N. (CLARIFICATION ADDED LATER: N is the naturals., f is non-decreasing) Consider the following game:

Let n be a natural number which we thing of as being large. Mark and Betty alternate (Mark goes first) putting M's and B's on an n by n checkerboard. No square can have two markers on it; hence the game will end after n² moves. If at the end there is some row or column A where the number of M's in A is at least n/2 + f(n) then Mark wins! If not then Betty wins! (NOTE- the M's in A do not have to be adjacent.)

For which f(n) does Mark have a winning strategy? For which f(n) does Betty have a winning strategy? Much is known on this problem. I have written up some notes that I will post on Wednesday. (None of this is my work.)

What are your intuitions and why? If you already know the answers then please do not post. SO, paradoxically, the less you know the more I want you to post. I want to know what the intuitions of someone who does not know the problem are.

What is the complexity of these problems and metaproblems?

The following problem is from Doctor Eco's Cyberpuzzles. I have shortened and generalized it.

We are going to put numbers into boxes. If x,y,z are in a box then it CANNOT be the case that x+y=z. If you put the numbers 1,2,...,n into boxes, what is the smallest number of boxes you will need?

(CLARIFICATION ADDED LATER: I mean that x,y,z are ANY three numbers in a box. For example, 10,11, and 21 CANNOT all be in the same box. One of the comments thought they could by letting z=10, x=11, y=21. This is NOT what I intended.)

You can use a simple greedy algorithm to get some partition, but it might not be optimal. The following set is not NPC (by Mahaney's theorem) but also seems to not be in P: I suspect that the following set is not NPC and not in P:

{ (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x,y,z with x+y=z }

There are many variants.

{ (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x,y,z with x+y=2z }

This one I know is thought to be hard- it is asking for the min number of colors so that you can color {1,...,n} and not have any Monochromatic arithmetic sequences of length 3. This is an inverse van der Warden numbers; hence I am sure that it is not in P, and that there is no proof of this, and its not NPC.

Let E be a linear equation like x+y-z=0. We represent E by its coefficients., so E would be (1,1,-1). The statement E(a,b,c)=0 means a+b-c=0. Fix E on a fixed number of variables, say a. How hard is

{ (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x₁, ..., x_a with E(x₁,...,x_a)=0 }

If we do not insist the set being partitioned was {1,..,n} we get more problems:

{ (a₁,...,a_n,k,E) : there exists a way to partition {a₁,...,a_n} into at most k boxes so that no box has x₁,...,x_m with E(x₁,...,x_m)=0 } I suspect this is NPC.

One can always use the Greedy Algorithm on the above problem, though it may not give the optimal answer. Consider the following meta problems: (``the problem'' can either refer to the version where we are partitioning {1,...,n} or a given set. Hence below there are eight problems, not four.)

1. { E : For the problem with E, Greedy gives optimal }. This is in co-NP.
2. { (E,a) : For the problem with E, Greedy gives within a*optimal }. This is in co-NP.
3. { E : the problem with E is in P }
4. { E : the problem with E is NPC }

For the last two I don't even know if they are decidable.

This Post is Quite Different from any you've ever read!!

I recently a letter from WETA (public TV) which I quote from:

This letter is quite different from any we've ever sent to you. For years we wrote to you about WETA's great programs and the need they filled in your life. Today, I must write to you about WETA's needs. And if friends like you don't respond to them, there will be far less programs to enjoy.

There is something wrong with this letter: I have gotten the exact same letter from them for about 4 years now. Hence the statement This letter is quite different from any we've send to you is not just false but verifiably false.

While I expect letters to exaggerate I do not expect to have easily verifiable lies that do not even help their cause. So why did they do this? I do not know. But whatever the reason, it is sheer incompetency. Hence I will not give to them. This raises the following question:

If a charity (or whatever Public TV is) asks for money they can exaggerate how much they need it. Should they?

1. Some readers will say GOSH, they really need the money! I better give!
2. Some readers will say They always need money. I am not going to bother.

We also have here a societal problem. Since many (legitimate) charities exaggerate about how dire their situation is or how serious their problem is, after a while it all gets tuned out. We have here a  Prisoners Dilemma problem- each one thinks (correctly?) that if they exaggerate their problems they will get more money. But if they all do it the public gets cynical and gives less money overall. (NOTE- I do not know this to be true, but I am curious. If anyone does know then let me know.)

How can they get out of this trap? I do not know. However, the least they can do is to not say things that are obviously false. There may be a well defined Game Theory or EC problem here. Or it may be a public policy problem. We won't know until its solved.

UPDATE IN May 2016: I keep getting these letters and got one today.

UPDATE IN July 2017: Got another letter today

UPDATE IN Sept 2017: Got another letter today

UPDATE IN March 2018: Got two in the month.

(I got some in between March 2018 and now but now I report it)

UPDATE IN JUNE 2022: Got one this month. 

A Seventh Mil. Problem

Richard Lipton had a wonderful post asking for a seventh Millennium Prize now that Poincare's conjecture has been solved. I posted a suggestion on his blog but got no comments. I'll expand on it and see if I get any comments here.

HISTORY: The original proof of VDW's theorem , in 1927, yields INSANE (not primitive recursive ) bounds on the VDW numbers. (Shelah (1988) later got primitive recursive bounds and Gowers (2001) got bounds you can actually write down!) Inspired by VDW's proof Erdos and Turan (1936), made two conjectures:

1. If A is a subset of N of positive upper density then A has arbitrarily long arithmetic sequences. Proven by Szemeredi in 1975 (see here for more.)
2. If &Sigma_{x ∈ A} 1/x diverges then A has arbitrarily long arithmetic sequences. (This conjecture implies the first one.)

A proof of either of these yields a proof of VDW theorem. The hope was that it would lead to a proof with better bounds. Szemeredi's proof of the first conjecture did not yield better bounds; however, Gowers proved the first conjecture a different way that did yield better bounds on the VDW numbers.

The second conjecture is still worthwhile since it may yield even better bounds and because it is interesting in its own right. So, I propose the second conjecture of Erdos-Turan as the 7th Millennium problem. (It might need a snazzier name. The Divergence Conjecture? The k-AP Conjecture? Suggestions are welcome!)

1. Greene and Tao have already shown that the primes have arbitrarily large arithmetic progressions.
2. The work that has gone into Szemeredi's theorem and the Greene-Tao theorem spanned many areas of mathematics. Hence this is not just an isolated problem.
3. The problem has been open since 1936. Hence it is a hard problem.
4. Will more connections to other parts of math be made? Is the problem too hard? A NO answer to both of these would make it not that good a problem.
5. The converse to the conjecture is not true. Note the following set:
   
   A = &cup_{k&isin N} {2^k + i : 0 &le i < k }
   
   The set A has arbitrarily long arithmetic sequences but If &Sigma_{x ∈ A} 1/x converges.
6. Is there a plausible condition that characterizes the sets that have arbitrarily long arithmetic sequences?
7. There is already (I think) a 3000 dollar bounty on the second conjecture. So the Clay Math Institute will have to just give 997,000 dollars.

CRA Snowbird Part II

Considerable discussion about funding at CRA Snowbird. Ken Gabriel, Deputy Director of DARPA, talked about how DARPA is restructuring its programs to become more university-friendly. They've made great progress though there are still some sticky issues of project-oriented proposals and security clearances. On a related note DARPA recently announced a new Crypto Program that may be of interest to the theory community.

Peter Harsha, the CRA director of public affairs, talked about NSF funding and how the renewal of the COMPETES act almost got derailed over pornography. NSF and CISE in particular did well in the administration's budget request but there is some uncertainty as we head into the fall elections.

The best part of the snowbird meeting is networking, talking to a number of CS leaders especially at the meals and breaks. The last session was small group meetings with current deans on how to deal with our own deans. Even though I'm not a chair I do find myself dealing with my dean and his staff quite often and we were able to get some good advice on quite a range of specific issues. Our group got lucky in matching up with  Dan Huttenlocher, Dean of Computing and Information Science at Cornell, and Martha Pollack, former Dean of the School of Information at Michigan. The best general advice: have a good working relationship with your dean and don't just ask or complain but really make the case on how the particular resource you need will benefit your school.

I'll be mostly on vacation and off the net for the next couple of weeks. Be nice to Bill while I'm gone.

CRA Snowbird Part I

I just returned home from my first trip to the CRA Snowbird Conference, the biennial meeting of CS chairs and other leaders in the CS community. I really enjoyed the short meeting and saw many old friends who are now chairs, some people I've only known by email and many I've talked to for the first time. There are a few theorists who have become chairs and deans, and, in the case of Jeff Vitter, provost at Kansas. Unlike theory conferences where I am usually one of the old people, most CS chairs are just about my age.

I, as I had to remind most people I met, am not a chair. I attended as a speaker on the Peer Review in Computing Research panel giving my usual spiel on how the current publication culture hurts the community-building aspects of conferences. Jeannette Wing made a great argument of how our deadline-driven research and conservative program committees may lead our field to lose its "vibrancy, excitement and relevance". 

A number of people talked about the big projects they work on which make me almost rethink having gone into theory. Almost. The need for better algorithms shows up in many of these talks. Yoky Matsuoka from U. Washington talked about the artificial hand her group developed that has the full range of motions of a human hand but they lack the algorithms to have the hand do even some simple natural tasks. Illah Nourbakhsh from CMU talked about building electric cars and his ideas of using a supercapacitor as an energy cache for batteries so the batteries become smaller and cheaper but hits challenging cache optimizing issues. The group is running a contest, best algorithm wins an electric car. 

Sally Fincher from the University of Kent gave a surprisingly strong talk Why Can't Teaching Be More Like Research? We get judged by our research based on how we compare to the global community but teaching is much more local and Sally talked about the implications of this distinction.

Most disappointing was the discussion on the NRC Rankings. Charlotte Kuh, who served on the NRC committee putting together the "soon" to be released report, said it will not give a specific ranking of each department but rather a range, like University of Southern North Dakota is ranked between 8th and 36th. And not just one range but five ranges based on different weights of the various criteria. And you can create other rankings based on your own choice of weights. All based on 2005-6 data. And they used citation data from the ISI which doesn't include most CS conferences. The CRA board talked them out of that but now the CS data and rankings will use no citation information at all. But even outside of CS, with multiple ranking ranges and old data, the NRC report will be of little value.

Do you want to review a book

I will be sending my next book review column for SIGACT NEWS off on July 28, 2010. It has LOTS of books on its BOOKS I WANT REVIEWED list. YOU get a chance to look at the book list and request one to review before the list goes out (if you do this then I will modify the list).

Here is a link to the list of books I want reviewed HERE. If you see a book you want then email me at gasarch@cs.umd.edu the name of the book and your postal address. We will then work out details over email- when the review is due, and whether me or the publisher sends it to you. I would like you to email me before July 28 so I can take those books off the list, but if you email after that date and the book you want is still available, that will be fine.

Before volunteering you should read my advice for reviewers.

Here is a LaTeX Template.

Factors for getting a job- Arbitrary, random, and complex

The Job Market in Theory (likely in all of academia) has more randomness and arbitrariness (are those the same?) then people may realize. Especially young PhD's who have never been to a faculty meeting where these things are discussed. The process is quite complex (is that the same as random and arbitrary?). I am NOT saying that merit plays no role. I am saying that its very hard to make a clean statement like Person X got a job an school Y because of Z.

With that in mind, I list out some criteria I have heard played a role in a hiring decision. My point is NOT to help you game the system (note that some of the factors I've heard cut both ways) nor to argue that the system is good, bad, or ugly. My point is only that the process is more arbitrary-random-complex then you might think. While its not all merit, its also not all who-you-know or politics.

I invite you to give leave comments on factors you have heard of, but to keep it civil please do not mention the people or schools involved.

1. Merit: This is itself ambiguous. More papers? Longer papers? Co-authors? How about take a sum where each summand is (number of citations)*(importance of paper)*(number of pages)/(number of coauthors). And then there is grant potential.
2. Does a postdoc have a better chance then a fresh PhD? A postdoc has had more time to increase his weighted sum mentioned under Merit, but the school KNOWS he has had more time.
3. Two-body-problems can be GOOD or BAD. Often a school does not have two positions.
4. Being a women can be GOOD or BAD (for getting a job).
5. I would like to say Being black can be GOOD or BAD (for getting a job) however since there are so few black PhD's in computer scientists applying for academic jobs, I have not heard any stories about this. (NOTE- I use the term black instead of African American since they need not be American.)
6. Being socially inept can be GOOD or BAD. How could it be good? It plays to the stereotype. He's so socially inept, he must be a genius. I DO NOT recommend pretending you are socially inept.
7. Speaking your mind can be GOOD or BAD. He'll be a leader in the community or He'll be a pain in the ass
8. Having a Blog- the jury is still out on this one. I have heard of a case where having a blog helped someone get an interview. (It was a serious blog about the field he was in. I can't imagine that complexity blog would help me get a job if I was looking.)
9. Spending too much time deciding what to have for lunch can be a negative. If he can't figure out what to have for lunch then how can he formulate a coherent research plan.
10. Area can be a factor- does a school need or want someone doing area X? This is sometimes formalized, for example the school has money targeted to hire someone who does, a particular area. (Side topic- Targeted positions- Good or Bad? Good in that you are not going to have to compare people in diff areas. Bad in that there may be someone really good in another area who you want to hire but can't.)
11. Subarea is a factor- for example, we want the kind of theorist who can talk to our people in systems.
12. Having a champion in the dept who is helping push your case HELPS unless the person doing the pushing is a jerk or not good at pushing a case.
13. Being an ex-convict probably hurts. If there was a theory genius who served 10 years in jail, that might be a negative. Might be mitigated if he could pull in some serious grant money. However, if the jail term was for embezzling grant money, then maybe not. Actually, the whole question might depend on what he was in jail for and is he now reformed.
14. A very big factor is how good is the job market when you get out. This may be a much bigger factor than anything else on this list.

How I Find Homework Problems

What do you get out of this paragraph (from Charlie Stross' The Atrocity Archives via Daniel Lemire)

The [Turing] theorem is a hack on discrete number theory that simultaneously disproves the Church-Turing hypothesis (wave if you understood that) and worse, permits NP-complete problems to be converted into P-complete ones. This has several consequences, starting with screwing over most cryptography algorithms—translation: all your bank account are belong to us—and ending with the ability to computationally generate a Dho-Nha geometry curve in real time.

I get a new homework question.

Show that NP-complete = P-complete if and only if NP = L.

Wave if you solve it.

Sparse problems in NP thought to not be in P

(This post is similar to this old post. I am posting this anyway since when I first posted I made fundamental mistake. I fixed it the point I was trying to make get lost.)

About once a semester I get asked

What are the natural problems that are in NP, not known to be in P, and not known to be NPC? What is known about them?

And I give the standard answers:

1. Graph Isomorphism. If its NPC then PH collapses so it is though to NOT be NPC. There is no real consensus about its status with respect to P.
2. Factoring. If its NPC then NP=coNP so it is thought to NOT be NPC. Most people think that it is NOT in P since people really want to solve this one and have not been able to. This is not a rigorous argument. Factoring is in QP. If quantum computers are ever practical then we may need to rethink how we think about these things.
3. Discrete Log. Actually, are there reasons to think this is NOT NPC?

The answer above are standard and I suspect most of my readers know them. However, there is a large source of problems that are in NP, likely not NPC, likely not in P, that people don't seem to talk about much: SPARSE PROBLEMS that are thought to be hard. The ones I know about are from Ramsey Theory. I give one example but there are many like it:

{(1ⁿ,1^m,c) : the n×m grid can be c-colored and not have any mono squares}

1. This is clearly in NP since the coloring itself is the witness.
2. Since this is a sparse set it is not NPC unless P=NP. (Actually it can be coded as a tally set.)
3. I want to say People think this is hard. You may ask Name Three of Them! Indeed, the number of people who work on Computational Ramsey Theory is fairly small. However, Ramsey Theory itself has many people working on it and nobody has anything close to a result indicating that this problem is in P. I personally think that it is hard.
4. For a fixed c there is a finite number of grids G1,...,Gp such that the n×m grid is c-colorable iff none of G1,...,Gp can fit inside the n×m grid. Hence, for fixed c, the problem is in P. (So the problem is Fixed Parameter Tractable.)
5. Everything said above holds if you replace squares with rectangles or other configurations in the above.

Questions:

1. Are there other sparse problems in NP that we think are NOT in P? (that is, ones that DO NOT come from Ramsey Theory).
2. Should we be teaching these in our complexity classes as examples of possible intermediary problems? The proof that they are likely not NPC is easy. However, to argue that these problems are likely not in P is hard. Also, these problems may appear unnatural to some students. (They may appear unnatural to some of my readers.)
3. It is easy to argue that Factoring is probably not in P since you can point to the fact that people REALLY want to solve it quickly and so far have not. This is not a rigorous argument but I do count it as evidence. Is there a similar argument for GI? Is there a similar argument for my Ramsey Problems?
4. Is there a mathematical reason to think that Factoring, GI, or my Ramsey Problems are not in P?

GCT Workshop (Guest Post by Josh Grochow)

Last week, the Center for Computational Intractability hosted a Geometric Complexity Theory Workshop. Geometric complexity theory (GCT) is an approach to P vs NP and related problems proposed by Ketan Mulmuley and Milind Sohoni, in which they were naturally led to using techniques in algebraic geometry and representation theory. This workshop was the most recent attempt to explicate GCT to both mathematicians and computer scientists, and discuss recent related results. Without looking at the attendance list, my impression was that the workshop was approximately 3/8 complexity theorists and 3/4 classical mathematicians (meaning that about 1/8 fell into both camps), and was about 1/3 students and 2/3 postdocs/professors. This turned out to be a pretty good mix.

The first two days were scheduled to be all Ketan all the time. Despite the fact that Ketan is an excellent presenter, talking for two days straight and keeping the audience interested would be a tough task for anyone. Not everyone made it to the end, but a significant fraction of the audience did. Ketan's lectures were interspersed with a lot of discussion and debate, including a couple short impromptu guest lectures from audience members on some background topics. Pointed questions came from both classical mathematicians and complexity theorists, and as often as not were answered by audience members from the other field. It was refreshing to see the humility of the giants of multiple fields: great classical mathematicians asked complexity theory questions that a complexity undergrad could answer, and vice versa. I think this is one of the few times I have ever heard of serious classical mathematicians mingling with complexity theorists, and I think it worked quite well. This type of interaction and more seems necessary for the GCT program, and can only be a Good Thing for both fields.

And now for two technical items from the workshop.

Avi Wigderson and others (sorry to the others, but Avi sticks out most in my memory, and I didn't learn everyone's names!) repeatedly suggested applying the techniques of GCT to easier problems than P vs NP and see if they can be pushed through to fruition for easier lower bounds. At the moment, GCT reduces P vs NP to certain hard conjectures in algebraic geometry and representation theory. The corresponding conjectures arising in easier lower bound problems would hopefully be easier, maybe even easy enough to solve in our lifetimes! Peter Burgisser has been looking at matrix multiplication using these techniques (an idea originally suggested by his adviser, Volker Strassen, long before GCT came along), and his student Christian Ikenmeyer gave a presentation on their results as one of the research talks on the third day.

Christian's talk was probably the most salient for complexity theorists not intimately familiar with GCT, so I'll mention a bit more about it to finish off the post. GCT introduces the idea of a "geometric obstruction" (=some type of representation-theoretic object) to "there are circuits of size n^c for SAT up to length n" (NP vs P/poly). If a geometric obstruction exists for all (or infinitely many) input lengths n, then P is not equal to NP. The conjectures arising in GCT imply that such obstructions exist. But even in smaller problems, such as matrix multiplication, no one had ever seen such geometric obstructions! Peter Burgisser and Christian Ikenmeyer did computer calculations and found geometric obstructions to the border-rank of 2x2 matrix multiplication. (The border-rank of 2x2 matrix multiplication roughly captures how many multiplications are needed to approximate 2x2 matrix multiplication, in a specific sense.) The geometric obstructions they found show that the border rank is at least 6 (it is known to be 7, by a significant algebro-geometric result of Joseph Landsberg). Although this only proved a weaker result than what was already known, for a comparatively easy lower bound (compared to P vs NP), this is an important proof-of-concept for the GCT approach of using geometric obstructions to prove complexity-theoretic lower bounds. This work also raises the intriguing possibility (also suggested in the GCT series of papers) that one might be able to "verify P neq NP up to length n" for larger and larger n, the same way people verify the Goldbach Conjecture or Riemann Hypothesis up to a certain numbers of integers/zeroes. Unfortunately, doing this in the GCT setting even up to n=10 seems to take too much time (whereas Goldbach and Riemann have been verified for millions of integers/zeroes).

Finally, I should mention even in the case of 2x2 matrix multiplication, the conjectures that arise seem almost as difficult as the ones arising in the P vs NP problem. Avi and others suggested we look at even easier problems.

UPDATE 7/20: Slides of the research talks are now available here, and videos will be added soon.

Can you ever be denied Full Prof? Can you ever really fail a PhD defense.?

1. Is it possible for someone to be denied Full Prof? Yes, but it is rare.
2. Is it possible for someone to fail a PhD defense? Yes, but it is rare.

These questions are similar. Why might either happen?

1. I suspect that the most common reason for someone to be denied Full Prof is that they went up without the Chairman's or the Departments approval. That is, they insisted on going up. I really cannot see a reason for a professor to do this except some sort of bad logic which I will discuss later.
2. I suspect that the most common reason for someone to fail a PhD defense is that they insisted on defending even though the advisor didn't think they were ready. While the advisor should have stopped it there may be other reasons (e.g., a job offer to the student has been made so he really needs the PhD NOW, or some deadline is coming up) that came into play. Could also be bad logic which I will discuss later.
3. Could also be because of politics. I've heard of this happening but never really saw a case I could verify myself. One problem: Everyone who is ever denied Tenure or Full Prof says that it was political. Hence its hard to tell when it really is.

BAD LOGIC:

1. A prof might think Everyone who I've ever seen go up for Full Prof has gotten it, so all I need to do is go up for it.
2. A student may think Everyone who I've ever seen defend their thesis has passed so all I need to do is get a defense scheduled. I have seen the following: nobody fails a defense for several years because the adviser don't put you up until you defend. Then the mentality sets in that all you need to do is defend and you'll pass. Then someone pushes this and ends up failing. THEN people are scared for the next few years, until its forgotten. That is why someone fails a PhD defense every 6 years or so.

WHY DENY SOMEONE FULL PROF? If you deny someone TENURE they LEAVE. Hence something is accomplished. But if you deny someone Full Prof they are still there, just annoyed. Hence it seems like a really bad idea to deny someone Full Prof.

WHY DO YOU WANT TO BE A FULL PROF? Salary increase? My school is now not giving raises. You get to write letters for more people. Is this really a good thing? You get to be on more committees. Is this really a good thing? You get more respect? This is questionable. People stop asking So, are you a full prof yet? This is a good thing.

HOW BAD IS IT: In both cases you can re-do. That is, you can come up for full prof later and you can fix your thesis and defend later. Even so, it can be a trauma.

FYI: I passed my PhD defense first try in May of 1985. I got Assistant prof in 1985, Associate Prof (Tenure) in 1991, and Full Prof in 1998.

Conflicts of Interest

a conflict-of-interest? Some thoughts.

Thought One

PROF: I can't vote on Professor X's Full Prof case since I have a conflict.

CHAIRMAN: (There are not that many Full Profs around so he is concerned about having a quorum.) Really? Whats your conflict?

PROF: My wife works as an F.R.A (Faculty Research Assistant) for Prof X.

CHAIRMAN: Is that really a conflict?

PROF: (Surprised) Uh--- I really think it is.

CHAIRMAN: Which way would it bias you?

PROF: (Even more surprised) I don't think that matters.

The odd thing is that it really is hard to say which direction it would bias PROF in. Does the wife like her job? Does she know that the prof is really good at what he does? Really bad at what he does? It could go in any direction.

Thought Two

I have reviewed two books that my advisor wrote in my SIGACT NEWS column. For his excellent books BLOWN TO BITS I have at the beginning of the review:

Disclaimer: Harry Lewis, one of the authors, was my PhD advisor.

That seems fair. However, the reader may wonder which direction the bias goes. In my case I thought Harry was an excellent advisor (Disclaimer: I also know that he reads this blog). But what if I thought he was a terrible advisor? I wonder if the reader has a right to know which direction the conflict goes in. Perhaps disclaimers should be of the following form.

Disclaimer: Harry Lewis, one of the authors, was my PhD advisor; however, I believe this review is unbiased.

Disclaimer: Harry Lewis, one of the authors, was my PhD advisor; He was an AWESOME advisor. Hence this review may be positively biased.

Disclaimer: Harry Lewis, one of the authors, was my PhD advisor; He was a TERRIBLE advisor. Hence this review may be negatively biased.

(The advantage of the last one is that if it is a positive review then the book must be really really good.)

Thought Three

Lets say I was having the NSF theory director over to my house for dinner on his birthday. Since he may give me a grant someday, should I charge him for it? How about a compromise- he pays for the dinner but I pay for desert. I think the rule may be that I can spend less than ten dollars over the course of the year. (Richard- I hope you enjoyed your birthday desert, since that's it for the year.)

Drowning in Data

At a CCC Council meeting last week, a common theme emerged. The Army is "swimming with sensors and drowning in data". Biologists are considering trashing some of the DNA sequences they have already acquired because it will likely be cheaper to resequence in the future maintain the current data. We've been collecting tons of information, what should we do with it and if we don't have the tools yet to deal with all this data, should we bother keep it?

This reminds me of one of my favorite homework problems in complexity: Given two log-space computable functions f and g (the read-only input tape and write-only output tape don't count for space), show that the composition f(g(x)) is also log-space computable. The direct approach doesn't work for you don't have the space to store g(x).

The solution is to recompute the bits of g(x) as you need them. The lesson: When storage is expensive, it is cheaper to recompute what you've already computed. And that's the world we now live in: Storage is pretty cheap but data acquisition and computation are even cheaper.

So who says complexity has nothing to say about the real world?