Complexity Year in Review 2011

Result of the Year goes to the new bounds on Matrix Multiplication by Andrew Stothers and Virginia Vassilevska Williams. It's not every year that we see progress on an important problem where we've had no progress since the 80's. Well there was last year. But not every year.

Some other notable results: Impagliazzo's relativized separation of Algorithmica and Heuristica, The Power of Simple Tabulation Hashing by Pătraşcu and Thorup and Property Testing Lower Bounds via Communication Complexity by Blais, Brody and Matulef

We celebrated Les Valiant's Turing Award. We remember Patrick Fischer, Phillipe Flajolet, Steve Jobs, John McCarthy and Dennis Ritchie.

Thanks to our guest posters Daniel Apon, Lauren Cowles, Annie and Molly Fortnow, Nadia Jones, Samir Khuller, Ryan O'Donnell, John Rogers, Jeffrey Stein, Aaron Sterling and Anonymous.

2011 will go down as a year when computer science started changing the world (again). Watson won on Jeopardy. Social networks brought down dictators and congressmen. Obama opens Robotics Center at Carnegie-Mellon. My daughter's high school had their first computer science class in a very long time and Stanford's AI course goes big time. The New York Times has sections on Computer Science's Sputnik Moment and the Future of Computing. The director of the Mathematical and Physical Sciences at the NSF declares "software is the modern language of science". Is there nothing CS no longer touches?

In 2012 we celebrate the man who started it all with a series of events celebrating the 100th anniversary of the birth of the father of computer science. I'll get it started next week talking on "Turing's Influence on Computational Complexity" during the AMS-ASL Special Session on the Life and Legacy of Alan Turing at the Joint Math Meeting in Boston.

Game Changers

Two announcements on Monday connected to my two Alma Maters mark the changing face of universities.

New York City chooses Cornell and the Technion to create new technology campus on Roosevelt Island

It didn't hurt that Cornell got a $350 million donation and that their main competitor, Stanford, dropped out.

Foreign countries have been creating campuses for some time now, like Northwestern's Qatar campus. Great to see this happening in my own country, a realization of the importance of technology and that New York knows it must make these investments. May this lead to other cities building tech campuses like they build sports arenas. Unlike sports, we can have many winners.

What's going to happen on this tech campus? Education, research, start-up incubators? Will there be a separate CS department in New York or just a branch from Ithaca? I can find very little details on the web, though there is this cool fly-over.

MIT launches online learning initiative

Following up on Stanford's online courses, MIT is creating their own tools for teaching online courses and will share these tools with other universities. Those taking the courses may receive a certificate but will have to pay a small fee to do so and the certificate will not bear the MIT name. According to the FAQ "MIT plans to create a not-for-profit body within the Institute that will offer certification for online learners of MIT coursework. That body will carry a distinct name to avoid confusion. MIT awards MIT degrees only to those admitted to MIT through a highly selective admissions process." Nevertheless these courses will allow people to get access to great MIT courses at little cost.

In the 90's, Newspapers decided they could better serve the public by putting their news stories online. How did that work for them? Are universities starting to go down the same path today?

Romney vs. Aaronson

How are Mitt Romney and Scott Aaronson similar? Different?

Similarities:

1. Both live in Massachusetts. Actually, Scott lives there but its not clear where Mitt lives since he's been running for president for the last four years.
2. Both, deep in their heart and soul, believe that Global Warming is a real problem.
3. Both use money to make a point:
   1. Mitt tried to to bet Rick Perry $10,000 that Mitt was never in favor of the individual mandate here.
   2. Scott blogged that if Deolalikar's proof of P ≠ NP is correct, Scott would give Deolalikar $200,000 here.
4. Both were somewhat misinterpreted: Some thought that Scott was insulting Deolalikar. He was not. He was just expressing his certainly the proof was not correct. Some thought Mitt showed he was out of touch with Middle Class American (who normally can't afford to casually bet $10,000 on anything). While Mitt might be out of touch, I think this was more of a way to forcibly express that there is no evidence that he was in favor of the individual mandate.
5. Both Mitt and Scott seem to be right. Deolalikar's proof is no longer believed to be correct, and fact check says that Mitt never supported the individual mandate.
6. There exists people who say Scott is smart. There exists people who say Mitt is smart. I don't know if this means anything since there exists people who say Newt is smart.
7. They both seem smarter than Michelle Bachmann, Herman Cain, and uh,uh, I can't think of the third candidate they both seem smarter than. Oops.

Differences:

1. Scott believes his belief that Deolalikar didn't prove P ≠ NP. Mitt has no beliefs.
2. Mitt can easily afford $10,000. Scott would have to struggle to raise $200,000.
3. Mitt's bet made him look bad. Scott's offer made him look good. He put-his-money-where-his-mouth-is unlike other bloggers who just asserted the proof was likely not correct.
4. Mitt made a bet partially in jest- it is unlikely to really involve an exchange of money. Scott made a real offer- if Deolalikar's proof had been correct he really would have paid out.
5. There is one of them that I would vote for. The other was once Governor of Massachusetts.
6. Scott knows a bit more about Quantum Computing than Mitt.

I emailed the Romney Campaign this post (without this paragraph), and the information that I would post it on Monday Dec 19, in case they had a comment. They did not respond. Perhaps Mitt is miffed about my saying Scott knows a bit more about Quantum Computing.

Algorithmic Driving

In my post last week, my commentors took me to task on my prediction that cars will drive us in ten years. Some thought Americans would wise up and learn to love mass transit. They don't know Americans.

Others thought the hardware cost would even in ten years remain out of reach. Google did not build an autonomous car by creating the hardware but by harnessing and training good machine learning algorithms. No amount of hardware would have given you a car able to navigate the streets of San Francisco five years ago.

What hardware do you need for an autonomous car, beyond the car itself? A good camera, a GPS device, wireless Internet access, gigabytes of RAM and a fast processor. I carry all that in my pocket. Google does use other sensors including lasers and radar but as the algorithms get better, the cost and need for this hardware can be reduced. Wiring the car to drive itself won't be difficult, already the steering wheel and pedals are mostly just a user interface into a computer that is controlling the car.

I have no doubts that technologically we will have autonomous cars in ten years adding at most a couple of hundred dollars over the cost of the car itself.

Other problems could get in the way. One is legal but Nevada is already changing their laws that will allow a testbed for autonomous cars in that state. Once the cars are viewed as safe one would expect the law to expand and other states to open up as well.

The other issue is social. As with every technological change we will have the usual technological life cycle: Innovators willing to pay the big bucks to try stuff first, Early Adopters who love to jump on new technology (where I usually sit), the early and late majorities following the crowd and finally the laggards who still insist on manual transmission and pumping their own brakes.

There are other issues like patents and industries, like auto insurance companies, that will try to fight autonomous cars. Autonomous cars will be too much of a win, in terms of parking, fuel efficiency, shorter and more productive travel time and most of all safety, not to prevail.

Solution to the reciprocals problem

In my last blog I asked you to look at this problem, try to solve it, and tell me if you think it is too hard for a HS competition. (I meant to post this on WED so I posted it at 12:06AM East Coast Time. I didn't know that the blog is on Chicago Time. So it got posted on Tuesday. Oh well.) Here is the problem:

Prove or disprove: there exist natural numbers x₁,...,x₁₀ such that

1. 2011=x₁+... +x₁₀ and
2. 1=1/x₁+... +1/x₁₀.

Several solutions and some other points of interest about this problem are here. The answer is YES and here are the solutions that I know of -- both my solution and the ones emailed to me. (The explanation of how they were obtained are at the paper pointed to above.)

1. My Solution: 2,4,5,80,80,80,160,320,640,640. This used known theorems.
2. Sam Solution: 2,4,5,40,120,160,300,300,480,600. Sam is a HS senior who is very good at these contests. It took him 30 minutes,
3. David Eppstein Solution: 3,4,7,16,16,16,20,43,80,1806. This used a bit of advanced knowledge and some hand computations that were probably above what you want for a UMCP Math Competition.
4. Matt Howell Solution: 2,4,5,50,100,100,250,500,500,500 This solution could have been found by a HS student (it is similar to Sam's solution.) Matt has a BS in Math and Engineering and did the problem in 20 minutes.
5. An anonymous commenter send me 6,6,10,10,12,15,15,15,62,1860. This solution could have been found by a HS student (it is similar to Sam's solution.)
6. Another one from same anon: 6,8,8,8,12,15,16,16,62,1860 This solution could have been found by a HS student (it is similar to Sam's solution.)
7. Mike Roman Solution: 5,5,6,8,8,12,15,32,960,960

So what to make of this?

1. Much to my surprise, enough people got it right and in ways that a HS student could have gotten it. And one did- Sam took the real exam.
2. The systematic solution that I got required very little hand calculation. All of the others, which includes the one I think a HS student could have or did get, required quite a bit of hand calculation. That may be a reason to not ask it.
3. I wonder how many solutions there are. This could be figured out by a Dynamic Program but there may be issues with large ints. (See later in this blog.)
4. I wonder if there are any that have distinct numbers. This can also be figured out by a Dynamic Program, though there may be an easier way.
5. I wonder about the computational complexity of the following problems:
   1. Problem 1 Given a,b in N, does there exist x₁,...,x_a such that x₁+...+x_a=b and 1/x₁+...+1/x_a=1. (Can also ask with the stipulation that the x's are distinct.)
   2. Problem 2 Given a,b in N and r in Q, does there exist x₁,...,x_a such that x₁+...+x_a=b and 1/x₁+...+1/x_a=r. (Can also ask with the stipulation that the x's are distinct.)

Possible Dynamic Program (more likely you would do it as a recurrence but save all answers found and check to see if you have already computed it, to avoid recomputing.) Let f(a,b,c,r) (where a,b,c are naturals and r is rational) be

num of sols to x₁+...+x_a=b and 1/x₁+...+1/x_a=r. where c ≤ x₁ ≤ ... ≤ x_a.

Note that

1. f(1,b,c,r) = 1 if r=1/b and r ≥ c
2. f(a,b,c,r) = sum as x in {c,c+1,..., min(b,floor(a/r)) } of f(a-1,b-x,x,r-1/x)

(NOTE- Use f(a-1,b-x,x+1,r-1/x) if you want to enforce distinct solutions.)

A math point: Ronald Graham showed that, for all n ≥ 78, n can be written as a sum of natural numbers whose reciprocals sum to 1. The lower bound of 78 is tight: 77 cannot be. A sketch of a proof of this is in the file pointed to. (The proof I give is inspired by one of the comments on the blog. YEAH BLOG COMMENTERS!) (ADDED LATER- Ronald Graham actually proved that for all n &ge 78 n can be written as the sum of DISTINCT natural numbers such that... . The proof I presented in the pointed to document just gives nat numbers, not necc distinct ones.)

Is this problem too hard for a HS Math Competition

The Univ of MD HS Math Competition has two parts. Part I is 25 multiple choice questions in 2 hours (4 points for a correct answer, -2 for an incorrect answer). If you do well on it (the threshold changes from year to year) then you can do Part II which is 5 problems in 2 hours, 30 points each. The winner is the person who does best on the sum of the two parts.

This year I submitted a problem for Part II. The people on the committee who tried it couldn't do it so we decided to NOT put it on the exam. I only knew the answer because I read a theorem and build a problem around it. The people who couldn't do it are very sharp. Since they could not do it the problem was too hard. But... lets see what you think?

I would like YOU to try it without consulting any resources, (and don't look at the comments- someone might post questions that lead to a hint, or the answer) and keep in mind that you can't use advanced techniques (I'm do not think they would help anyway). See if you can do it so I can get a sense if it really is too hard. Post your opinion on if its too hard for a HIGH SCHOOL math competition. Here is the problem:

Prove or disprove: there exist natural numbers x₁,...,x₁₀ such that

1. 2011=x₁+... +x₁₀ and
2. 1=1/x₁+... +1/x₁₀

(ADDED LATER- A commenter thought that the x_i's in the first and second condition could be different. They are not. We want x₁,...,x₁₀ that satisfy both of these simultaneously.)

I'll post a pointer to the solution next time I post. (Probably Wednesday.) ADDED LATER- a commenter wants to know if there is a solution or not and can't wait until WED. Also wants to know if there is a solution is it constructive or proof of existence. To answer the question but NOT ruin it for others, I put it in a file you can click on (or NOT) over here: here.)

A Great Time to be a Computer Scientist

Ask your friends if they'll be driving an electric car in ten years. The answer: No, cars will be driving us.

Today is the 105th anniversary of the birth of computing pioneer Grace Murray Hopper and Computer Science Education Week is being held this week in her honor. If only she could see what we have reaped from what she has sown.

The New York Times this week devoted Tuesday's Science Times to the Future of Computing. The section includes a series of essays from CS researchers including Daphne Koller, Stefan Savage, David Patterson, Kai-Fu Lee and fellow theory blogger Scott Aaronson. Scott also blogged about the experience. Though what would you do with a quantum computer on your desk? The factoring number thing could get boring pretty quick.

The Times also has a crowdsourced interactive timeline of future computing events. Try to guess which one I submitted. Almost all the advances listed are realistic and should keep CS very active for the long future. The most exciting future computer science advances will be the ones we haven't even thought of.

Finally the new class of ACM Fellows includes many theorists including Serge Abiteboul, Guy Blelloch, David Eppstein, Howard Karloff, Susan Landau, Joe Mitchell, Janos Pach and Diane Souvaine. A great year to be an ACM Fellow because the awards ceremony in June will follow a workshop celebrating the Turing Centenary featuring over 30 former Turing award winners.

What is a Breakthrough?

The recent discussion on Matrix Mult inspires the general question of WHAT IS A BREAKTHROUGH? Last year I tried to get an intelligent discussion on this topic but I failed. After saying what some criteria were I applied them in a silly way to several results. This derailed the discussion. My bad, my fault. SO, I'll try again to get an INTELLIGENT discussion on this topic. (NOTE- some of this post is a reworking of the old post.)

Here are some criteria. The first three are extracted from a comment Gowers made on Scott's Blog. I do not know how many a result has to have to be a breakthrough or even if such a threshold makes sense. Perhaps some sort of weighted sum, but would be hard to define.

1. The result breaks a long standing barrier.
2. The techniques introduce a fundamentally different method.
3. The result is practical (or close to it).
4. The problem being discussed is important. This may be a bit circular in that it then depends on What is Important?
5. The result has to make substantial progress on the problem. This may depend on What is substantial? That notion may depend on how long the problem has been open.
6. There has to be a reason why the problem was thought to be hard. E.g., a proof that a new technique is needed, problem has been open for a long time, people in the field say its hard.
7. A paper that STARTS an important field could be a breakthrough. Cook's Theorem and Valiant's PAC learning qualify here.
8. A paper that FINISHES a field could be a breakthrough if the field is important. Again this may be a bit circular in that it then depends on What is Important?
9. The techniques are new. One might end up debating what is new.
10. The techniques can be used on other problems.
11. The paper inspires other papers. For this criteria you need to wait a few years. Some papers are not appreciated for a while.

The notions of important, substantial, new are not Boolean. As Gowers pointed out in his comment, the notion of breakthrough is not Boolean.

Do you have other criteria, examples, counterexamples, constructive criticism of my criteria, or anything that is an intelligent contribution to this topic? Is so, please post a comment!

Probability

On Saturday, Terrence Fine gave a talk on probability at a workshop at Northwestern. Before the talk he asked who thought probability was subjective (an individual's belief in the chance of an event) or a frequentist (a probability represents what happens if an experiment can be repeated many times). Someone noticed I didn't raise my hand either time so I said that I had a computational point of view of probability, since I have a computational point of view of everything.

I didn't mean computation as in Turing machine but as a process. A process that creates events according to some distribution. How does this process work? I don't care. That's the beauty of computational thinking, we abstract out the notion of probability and just make use of it. I've written papers on quantum computation having no idea of the physical processes that create entanglement. I study nondeterministic computation where we have no physical counterpart. Probability works the same way, at least for me.

My contribution to the workshop was to explain Kolmogorov complexity, the universal distribution and its relationship to inductive learning to the mostly economics crowd. Perhaps I could have explained things a bit more clearly as one econ student said to me afterwards "You lost me at prefix free". 

Analysis of Boolean Functions blog/book (Guest post by Ryan O'Donnell)

(Guest post by Ryan O'Donnell)

Lance and Bill have graciously let me plug my recently begun book/blog project, analysis of boolean functions. I am writing a textbook on analysis of Boolean functions and serializing it on the blog as I go. When I'm done, the book will be available online; hopefully it will also be published in the conventional format. (NOTE FROM BILL- its also linked to off of our blog page.)

The topic is sometimes called Boolean Fourier analysis, though my perspective is a bit more from probability theory than harmonic analysis. I hope the book will be accessible and of interest to grad students and researchers in theoretical computer science and other areas of mathematics. Each chapter will end with a "highlight" illustrating the use of Boolean analysis in problems where you might not necessarily expect it. To give you a flavor of the contents, my planned list of highlights is:

• Testing linearity (the Blum-Luby-Rubinfeld Theorem)
• Arrow's Theorem from Social Choice (and Kalai's "approximate" version)
• The Goldreich-Levin Algorithm from cryptography
• Constant-depth circuits (Linial-Mansour-Nisan's work)
• Noise sensitivity of threshold functions (Peres's Theorem)
• Pseudorandomness for F_2-polynomials (Viola's Theorem)
• NP-hardness of approximately solving linear systems (Hastad's Theorem)
• Randomized query complexity of monotone graph properties
• The (almost-)Polynomial Freiman-Ruzsa Theorem (i.e., Sanders's Theorem)
• The Kahn-Kalai-Linial Theorem on influences
• The Gaussian Isoperimetric Inequality (Bobkov's proof)
• Sharp threshold phenomena (Friedgut and Bourgain's theorems)
• Majority Is Stablest Theorem
• Unique Games-hardness from SDP gaps (work of Raghavendra and others)

If you're interested, you can think of it like an online course -- I've been publishing Mondays, Wednesdays, and Fridays, and there are even exercises. (Also like a course, I'll go on break for a few weeks around the new year.) Come see why "juntas" are important, what hypercontractivity "really" means, and why functions on Gaussian space are the "easy special case" of Boolean functions...

PS: I'm using MathJax for the posts; if anyone has suggestions for me or for readers on how to make it look nicer or load better, please do let me know.

Matrix Mult (you heard it here... third?)

(INNOVATIONS CONFERENCE: here)

(While preparing this two other bloggers wrote on the same topic, Scott here and Lipton/Regan here. Our slogan: Complexity Blog: You heard it here THIRD.)

Let w be the exponent for matrix mult. A very brief history of Matrix Multiplication (years given are years of publication, though it is odd to say Pan in 1978 showed that w < 2.796 since, for all I know, he did it in 1977 or even earlier.)

1. The obvious way to do this shows w ≤ 3. This is obvious to us; however, I wonder when it was first stated.
2. Strassen in 1969 showed w ≤ 2.808. This is important since it shows that Gaussian Elimination is not optimal (that is the name of the paper) and also because it is a cautionary tale for lower bounds- w=3 seems optimal... but its not!
3. Pan in 1978 showed that w < 2.796.
4. Bini, Capovani, Romani, Lotti in 1979 showed w < 2.78.
5. Schonhage in 1981 showed w < 2.522 This was significant since it used a brand new technique.
6. Romani in 1982 showed w < 2.517.
7. Coppersmith and Winograd in 1981 obtained w < 2.496. This was significant in that it broke the 2.5 barrier.
8. Strassen in 1986, using a very diff technique, obtained w < 2.479.
9. Coppersmith and Winograd in 1987 obtained w < 2.376. (See here for the Journal Version.) This paper uses the large 3-free sets of Behrend. (See here for Behrends article (it might now work- its the Proceedings of Nat Academy of Sciences website and I don't know if its free to ALL or just to some schools.) or here for my survey of large 3-free sets.)
10. Cohn and Umans in 2003 proposed a group theoretic approach which had the potential for new algorithms. Kleinberg and Szegedy in 2005 obtained new algorithms using the approach, but couldn't beat 2.376.
11. Elkin in 2008 (here) obtained larger 3-free sets than Behrends. Elkin in 2010 (here) used these sets to get a log^v improvement over CW for some v > 0.
12. Andy Stothers 2010 PhD thesis (here) claims to have w ≤ 2.374. The result was not stated in the abstract. He didn't post a preprint or email a blogger so this work was relatively unknown. He did tell some experts in the field. (See the comments on Scott's blog for what might be the full story on that).

Virginia Vassilevska Williams has obtained (ind of Stothers) w < 2.3727 (see here) with a very sophisticated analysis. How do I know its sophisticated? Because the paper is 71 pages long and looks scary.

1. This is clearly a breakthrough! There had been NO improvement in two decades!
2. The improvement is small; however, it may lead to more improvements (this seems to be common in this field).
3. Can Elkin's 3-free sets be used to get a log improvement over Virginia's result? Not sure we care- from what I understand (which is not much) (1) the current techniques can likely be pushed further, and (2) Elkin's 3-free sets will only give a log-ish improvement, no more. (Is log-ish a new word? Should it be?)
4. Is the algorithm practical? I suspect not.
5. Two breakthroughs in theory within a year from the same family. Impressive!

The Death of Complexity Classes?

In the 2011 Complexity proceedings there are three papers that analyze complexity classes, Ryan Williams' great paper on ACC, Russell Impagliazzo's paper on average versus worst case for NP and a Hartmut Klauck's paper on AM in communication complexity. That's the complexity conference. At STOC, there was only the Aaronson-Arkhipov paper on linear optics.

Complexity classes capture important aspects of problems based on how they can use various resources. The complexity zoo has nearly 500 classes. Many of the greatest theorems in theoretical computer science relate classes like NPSPACE = PSPACE, NL = co-NL, PH ⊆ P^#P, IP = PSPACE, NP = PCP(log n,1), SL = L, NEXP not in ACC and many others. The most important open question in our field (and maybe any field) is the relationships of the classes P and NP.

So why do we see so few papers about complexity classes these days? We are victims of our own successes and failures. We have succeeded in classifying and relating most of the connections between classes where we don't have relativizable counterexamples and have failed, outside of interactive proofs, to develop many tools that let us get around relativization and other barriers.

So here we sit, still putting out the occasional paper on complexity classes but mostly hitting a wall. Occasionally we see a nice breakthrough like Ryan's paper but mostly we are just clawing at that wall waiting for someone to create a wrecking ball so we can make real progress. 

The Jobs Bio

I just finished the Walter Isaacson biography of Steve Jobs. Seems like everyone in the blogosphere has analyzed every sentence in the book, so I won't do that.

Instead I viewed the book as a trip down memory lane. The Apple II was my second computer and while I never owned a Mac you can't avoid them in the CS community. My family has by now gone through a dozen or so iPod/iPhone/iPad devices.

The biography opens up the curtain and you get to see the man behind these devices. Jobs was not a computer scientist or even a computer engineer. He was a designer who understood computers enough to make them beautiful and make them work better. His simplicity sometimes goes too far, I like the context-sensitive menus from a right mouse button and often double click the one button on my iPhone instead of single click or vice-versa.

I found myself least interested in Jobs' personal life, most of the problems he dealt with were of his own doing. He wasn't a nice guy and often got upset with people who don't share his values. But he also knew how good technology should work and we're better off for it.

I love reading biographies of successful people, you really get to see a fuller picture both the good and the bad. Walter Isaacson's book is rather unique, rarely do we get such a complete picture so soon after his untimely death.

If Steve Jobs isn't your thing, try Isaacson's bio on Einstein instead, another great read.

Short Bits

Because some things are too long to tweet and too short for their own blog post.

What's the algorithm for the perfect sushi? Enjoy it with some cool refreshing SODA in Kyoto. Early registration deadline is December 20th and lots of travel support still available (apply by Nov 29).

What's new for STOC 2012 in New York City? An open call for workshops (apply by Dec 2) and a best student presentation award. Practice up. Please also nominate people for Gödel, Knuth and SIGACT Distinguished Service prizes.

Google scholar citations now open to all. Now you can see my papers at Google, Microsoft, ACM, DBLP and my own papers page. Google has the best stats and ranking, DBLP the best links, my page the most accessible downloads and Microsoft has the coolest graphics.

Google gives all the stats so we can rank job applicants. Why stop there? Google can use their magic algorithms to tell us who to hire. No more messy recommendation letters and awkward interviews.

Are these journals real?

Consider the following email I got:

Dear Professor,
 1. Antarctica Journal of Mathematics
 2. ArchimedesJournal of Mathematics
 3. BesselJournal of Mathematics
 We are charging only $3 per page,
 which is very cheap when compared to
 other money oriented journals.
 Further we request you to withdraw your paper,
 if you have already submitted it to any money
 oriented journal.  You can submit your research
 papers to our online journals.
 We also consider paper from
 Statistics and Computer Science.

What is going on here? Possibilities:

1. The journals are fake. They are part of an April Fool's Day joke. Using BesselJournal and ArchimedesJournal, with no space in the obvious place, (not typos by me- this is what the email said) might have been a clue that they were jokes.
2. The Antarctica journal is real and is a reaction to the notion that we shouldn't hold conferences or workshops in places where there are human rights violations. (See here.)
3. The Antarctica journal is real and is a reaction to the notion that whenever you have a conference the locals get to go cheap; this conference will be equally expensive to all (or to most). (See here.)
4. The journals are real. The Antarctica Journal of Mathematics was founded because all continents except Antarctica had journals and the founders thought this was unfair.

The last option is the correct one. I am not surprised- the journals have to be real since the titles are not quite funny enough to be a joke. Antarctica Journal of Mathematics sounds fictional, like The University of Southern North Dakota at Hoople, but it is not. The Antarctica Journal's website has real articles on it and seems to have been publishing since 2004.

In some fields it is standard to pay-to-publish. Older faculty used to tell me about page-charges for journals in our field, in much older times, (and I think grants mostly paid for it) but I have never seen them in my academic lifetime (in math and TCS). (Exception: a few conferences, though not many.) Different fields evolve in different ways, and I do not claim to know what the best approach is. However, since in our field (Math, TCS) it is standard to NOT have page-charges (I do not know of any journal that does this, and I know of only a few conferences that do) it seems odd to ask you to compare their journal with other money oriented journals. Are there other ones in mathematics?

Penn State

Take the state of Pennsylvania and draw the two diagonals. Where they cross is the small town of State College, home of the Pennsylvania State University. I first traveled to Penn State in 1989 on an interview trip. We went to dinner at the only nice restaurant near campus. The conversation turned to Joe Paterno, Penn State football coach. The waitress, a Penn State undergrad, said "Oh, you mean God."

As many of you know, Paterno and Penn State president Graham Spanier were fired last week in the wake of the Jerry Sandusky child sexual abuse scandal.

I have a certain affinity for Penn State.I have worked with researchers there from experimental economics to pure logic and they have a number of people there connected to my NEC days. I have been back to that campus several times most recently in the spring of 2010. The changes in those two decades have been amazing.

Quite a bit of new building on campus and off. There are now a number of nice restaurants near campus. There are plenty of new buildings on campus too including a beautiful IST (Information Sciences and Technology) building that houses the IST and CSE departments. Just in theoretical computer science, Penn State made some recent strong hires and had a rare double PECASE win of Adam Smith and Sean Hallgren.

Paterno helped build the Penn State brand through football which he coached at Penn State since I was a toddler. Paterno also knew that Penn State meant academics as well, he had a large number of academic all-Americans on his team and donated money for a library on campus that bears his name. Spanier build on this brand to develop real growth in the university and the town it lives in.

Paterno and Spanier should have done more to protect the children but I hated to see them leave under these circumstances. They have both done much for Penn State and not just on the football field.

My response to the Gasarch P vs NP poll

A while back GASARCH solicited responses to a P vs NP poll and gave Oct 31 as the deadline. Now that the deadline is passed I post my answers.

1. Does P=NP? I think P is NOT NP. However, I am not dogmatic on this. When I first saw the Graph Minor Theorem used to get Vertex Cover for fixed k into O(n³) times I thought that a different very-hard-math-thing-that-I-don't-understand might be able to get SAT in P. Also, I am more convinced that separating the two is hard then I am convinced that they are different. Litmus test: If someone told me that the problem had been solved, but not which direction, I would guess P=NP. SIDE NOTE: My wife thinks P is NOT NP since If P=NP then they would have proven it by now. This argument may become more compelling as time goes on.
2. When do you think it will be resolved? Between 200 and 400 years from now. Jon Katz told me: If its not solved within 200 years its not going to be solved..
3. What kinds of techniques will be used?
   1. Fermat didn't know about Elliptic Curves. Similarly, we do not know the techniques.
   2. I hope its Ramsey Theory and Logic so I might understand the proof.
   3. If it comes out of Geometric Complexity Theory I will not understand the proof.
   4. We will show that P ≠ NP by showing that FACTORING is not in P. SAT might not be a good candidate for separation. This kind of thing has happened before (once): The proof that AC₀ ≠ NC₁ was done by showing PARITY not in AC₀. PARITY is not complete for NC₁ under AC₀ reduction. The word problem for S₅ is, but was not useful for separation. Factoring may be a better candidate for separation since you can generate instances that seem hard, where for SAT this seems hard to do.
   5. Ryan Williams great result shows that there are still things we can do with what we know now. Is P vs NP one of them? NO.
4. Will the problem still be relevant given advances in SAT solvers? YES. Sat Solvers are GREAT and can solve lots of things- perhaps more than we had thought. But there are still lots that are not. The 17x17 problems has resisted attempts by SAT solvers to solve it (or so I've been told). The problem is a 4-CNF with 4 × 17² vars (not that many), and roughly 4 × 17⁴clauses (too many).
5. Feel Free to comment on other things:
   1. Graph Isomorphism: We will show P ≠ NP but still not know the status of GI. OR we could find that GI is in P tomorrow.
   2. As noted above, we will show Factoring is NOT in P.
   3. Quantum Computers will never be practical; however, see next note.
   4. Just as the Prob Method is now a STANDARD thing to know even if you are not working on probability, Quantum methods will be a standard thing to know even if you don't work on quantum computing.
   5. We will show L=RL before I do this poll again.
   6. Within 10 years all supermarkets will have self-checkouts that work nicely and that you are expected to use--- except in New Jersey which will outlaw them to create more jobs (as they do now for self-service gas).

Making Money the (Computationally) Hard Way

Digital cash systems have come and gone but Bitcoin seems to be doing okay. By request I am giving a lecture about Bitcoin in my crypto class. Most of the material I find about Bitcoin is either very high level for a typical user or very low-level detail for the implementer. In this post I'll try to hit the middle ground.

Bitcoin tries a different approach to digital case. Their goal is not anonymity but more a cash system that works in a peer-to-peer network without a central authority.

The basics of Bitcoin come from a paper by the mysterious Satoshi Nakamoto. The Bitcoin systems doesn't use encryption but it does make strong use of secure hash functions and digital signatures. A user establishes an account by creating public and private keys for an elliptic-curve based signature scheme. A hash of the public key serves as the account number.

A transaction from person A to B roughly consists of the amount, a link to an earlier transaction where A received bitcoins, B's account number, A's public key and A's signature of all of the above. Transactions are transmitted to everyone. More general transactions are also possible.

Transactions aren't accepted until they appear in a block. A block consists of a hash-tree of transactions, an extra transaction giving 50 bitcoins to the block creator (this will decrease over time), a hash of the previous block, a time stamp and something called a nonce. The nonce is just an extra number chosen so that the hash of the block has a certain number of zeros in the right place.

You create money by creating blocks which requires finding the right nonce, a computationally difficult task. The number of zeros is set so that a new block is created on average every ten minutes. A transaction is accepted when there is a chain of six block starting with the one where the transaction occurs. This prevents double spending as that firmly establishes this chain as the "official" one.

There's a lot more details but the idea is a clever use of computation to mine money like one can mine gold with considerable effort. Or you can get money by trading goods or services (or real currency).

Not clear to me that it could scale for wide-spread use but still quite a clever and so far working system.

The Annual Fall Jobs Post

For these looking for an academic job in computer science next year, best to start on the jobs pages of the CRA and the ACM. Both lists seem long this year, perhaps the job market is finally beginning to pick up.
Also check out the postdoc opportunities on Theory Announcements.

Feel free to list other job opportunities in the comments.

My department has two faculty positions for next year. Neither one specifically in theoretical computer science but we do plan to treat the areas broadly.

My advice: Apply widely, the job market is quite unpredictable. Put real effort into your research statement and be sure your CV is informative yet concise. Most importantly: Choose your letter writers well.

Journals

What is the purpose of an academic journal? To provide a permanent vetted record of a specific research endeavor.

The ways we communicate scientific research has vastly improved, particularly with the advent of the Internet, but the need for that basic mission will never go away.

Noam Nisan laments that journals do not provide a quick form of dissemination or do the proper amount of vetting. He's correct on both points. Computer scientists need to take journals more seriously to improve the vetting process and the speed to publication. But also journals have never played the role of quick dissemination in computer science. That role has been taken by conferences, departmental technical reports and more recently on-line archives. Journals don't compete with sites like ArXiv, they play different roles.

Tim Gowers suggests a commenting/scoring system for reviewing papers. I'd love to see such a system built into ArXiv and ECCC. But it won't supplant the need for academic journals. Most papers won't get reviewed and most researchers won't review papers. Collaborative projects like Wikipedia, Polymath, Math Overflow (and the TCS descendant) are incredible resources but just a small number of researchers are significantly involved. If you reward people for reviewing papers (through reputation or otherwise) then people can decide not to review guilt free. 

We are moving to a world where we rank research papers not on where they appear but by how many citations they achieve, a statistic the Internet has made easier to measure. One can cite an ArXiv paper just as easily as a JACM paper. The incentives for an author to do more than throw up a paper on an on-line site are going away. We will no longer fulfill the mission of journals and future scientists will struggle understanding the how and why of what we did. Is this the gift we want to leave to the next generation?

The Digital Random Bit Generator

I started this month asking about the nature of randomness and how we generate it for our computers. Let me end the month talking about Intel's clever new digital approach to creating random bits.

Intel chips used to have an analog random bit generator based on noise in the circuits. But improved circuits reduced the noise limiting the effectiveness of these generators.

In the September IEEE Spectrum, Intel Architects Greg Taylor and George Cox give an overview of a digital random bit generator will sit in future Intel chips. The article is a short and fun read.

The heart of the article describe a simple digital circuit.

Initially when both transistors cause full voltage at both Nodes A and B. Intel had to use special inverters (NOT gates) that can withstand not being able to invert at this point. A clock signal slowly turns off the transistors and the inverters go to work reducing A and B to an equilibrium of half voltage each.

The magic now happens. This isn't a stable equilibrium so even the slightest noise quickly drives one of the nodes to full voltage and the other to no voltage. Which node goes to one depends on the direction of the noise and that's how you get your random bit.

Taylor and Cox find an idea that they might have sketched on a napkin and yet gives an incredible simple and elegant solution to an important problem. This is why I love computer science.

John McCarthy (1927-2011)

First Steve and then Dennis and now we have the death of a third computing pioneer this month. John McCarthy passed away earlier this week at the age of 84.

McCarthy was one of the founders and early promoters of Artificial Intelligence and gave the field its name. He developed Lisp for the same reason Newton invented calculus, he needed a system to do his research so he created his own. Lisp, built on Church's λ-calculus, was the first popular example of a functional programming language, an entirely different way to think about programming than the more structured languages. McCarthy received the ACM Turing Award in 1971.

McCarthy truly believed a computer could capture human intelligence and his pioneering work may yet help make that happen.

It's Open Access Week

Open Access Week starts today. Interestingly a number of traditional journal publishers, like Springer, are sponsors as they try to figure out how to modify their business model in a changing publication environment.

We'd love all our papers to be as widely available as possible but no journals are truly free. They either need a revenue stream whether that comes from authors, readers, libraries or some other outside source, or require a considerable amount of volunteer effort and coordination beyond just editing and reviewing.

I found out about Open Access Week from the ACM as they are promoting their Author-ize service that lets authors give a link on their home pages that allows their readers to freely download the ACM version of their papers. I consider ACM one of the good publishers, reasonably priced, and they've already allowed us to publish our own papers on their website and use them in other publications. David Rosenthal has other opinions.

There is a pledge Research Without Walls going around to "assist in the peer review process (as a reviewer, board/committee member, chair, editor, etc.) only for conferences, journals, and other publication venues that make all accepted publications available to the public for free via the web." Are you signers willing to forgo serving on a STOC or FOCS PC?

I heard a great (though hard to parse) quote second hand from an economist about the ethics of illegally downloading music.

If if I had to pay for it I would pay for it then I will pay for it.

The iTunes model addressed this concern by pricing music so cheaply that one would feel better paying for it than not. Academic publishers should learn this lesson and also price downloads of research papers at $0.99.

My biggest fear of the open access movement is that without a strong alternative model it will just lead to even less CS papers getting published in journals. Even open access won't give access to a paper never written.

The Cup Holder Principle

The story goes that when Toyota engineers started to design the first cup holders in the 80's, they went to a local 7-11 and got every different cup 7-11 had to make sure their design would work on all the cups in current use. These days the cup designers have to make sure their cups will work in today's cup holders.

This is one of the starkest examples of initial Technology for A being driven by B and now the technology for A drives the technology for B.

How much does this happen in theoretical computer science? Do we design algorithms to use an already established data structure? Do we modify our definitions of some object to make it group or a field? Do we create a cryptographic protocol so that some "standard assumption" makes it secure?

Are these good or bad things? Sometimes it is really useful to make square pegs fit into round holes and other times we miss new opportunities.

Theorems that are impressive at first but then....

Mission Impossible was my favorite show as a kid. As an adult it would not make my top 20, and I wonder why I liked it so much as a kid. (Actually I do know- at the beginning they are given a well defined problem and they solve it, which is how Math works.)

This inspired this post: Is there some theorem that you were initially impressed with but are now far less impressed? I list things I have heard of for this category. I request that you submit your own examples.

1. Every number is the sum of 4 squares. This is impressive and still is. Number theorist must use this all the time! Alas, aside from its use in Hilbert's 10th problem, and maybe a few few other places, I has never seen it used and is now less impressed. However, this may be unwarranted. Some theorems in math are impressive for the achievement, others for their use later. This one IS impressive for its achievement. But, as far as I can tell (and I could be wrong), not for its uses.
2. Every group is a group of permutations. Group Theorists must use this all the time! Alas the proof makes you realize its more of a tautology. Rarely used by Group Theorists. It is used in some of the proofs of Sylow's theorem. I do not know of any others uses. And this one is not impressive for its achievement.
3. The Prime Number Theorem. Since results that are very very close to it can be gotten with much much much less effort, getting the actual constant down to 1 seems like too much sugar for a cent. (For more on PNT and a link to an easy proof of a weaker version see an old post of mine here.) However, this one is an achievement certainly. And it inspired other great mathematics.
4. Poincare's Conjecture says that if something looks, feels, and smells like a sphere, then its a sphere. Is that really worth $1,000,000? Perhaps Perelman didn't think so either.

Teaching PCPs to Undergrads

The last few times I've taught undergraduate theory I cover the PCP theorem. It's not complicated if you state it the right way:

PCP Theorem: For any constant α > 7/8, there is a polynomial-time computable function f mapping 3-CNFs to 3-CNFs such that for all formula φ,

• If φ is satisfiable then f(φ) is satisfiable.
• If φ is not satisfiable then every assignment to f(φ) satisfies at most an α-fraction of the clauses.

I point out to the class you can satisfy 7/8 of the clauses by just choosing a random assignment.

Also I show how the PCP theorem gives some (weak) approximation bounds for Clique. For each variable in each clause of f(φ) create a node of a graph and connect two nodes as long as they aren't in the same clause or connect a node representing a variable with one representing its negation. That gets you an 8/7-ε approximation lower bound for clique. I give showing a constant approximation lower bound for Vertex cover as a homework assignment.

I don't even try to give an idea of the proof of the PCP theorem. I just say it would take an entire graduate class to cover the proof in its full detail. That's probably a lie, one of our ten-week quarter-long classes is not enough time to prove the very strong version of the PCP theorem stated above. 

Dennis Ritchie (1941-2011)

We lost another computing pioneer of a very different kind. Dennis Ritchie, who developed C and co-developed Unix, passed away last weekend. Ritchie and Ken Thompson received the 1983 Turing Award for their development of Unix.

In the early 80's I programmed extensively in assembly language on the Apple II and IBM 370. In both cases we needed speed a high-level language couldn't get us. C and Unix let us take advantage of high-level constructs and abstraction and yet retain the full power of the underlying machine. Ritchie changed the way we did computing.

If there is a moment that captures both Jobs and Ritchie, it was in 2002 when the Mac moved to the Unix-based OS X from which also the Apple iOS was later derived. As you play with the new iOS 5, you can't help but think of these great pioneers that made it possible.

If Bill Tweeted what would he tweet (Steve Jobs Edition)

1. A more nuanced view of Steve Jobs: here.
2. A less nuanced view of Steve Jobs: here.
3. The next Steve Jobs: here
4. A very nice NON-Steve Jobs post here.
5. Is this an appropriate use of logarithms? From Andrew Sullivan's Blog (the boldface is mine):

   In some ways, the emergence of a Republican candidate (Rick Perry) who takes every single aspect of George W. Bush's political persona and adds a logarithm, is a healthy sign. I'd rather have a candidate who is explicitly saying that his politics is based on religion and his political rallies are actually spiritual rallies, than one whose theocratically-driven conservatism is on the downlow.

6. A type of Math Anxiety
7. Should people learn math?
8. The president invokes math: here
9. A bad idea for a TV series: The intuitionist defense attorney: Just because you proved that A OR B did the crime, and then you showed NOT(A did it), does not mean that you have proven B did it.

More than East and West

The Obama Campaign is creating a Campaign Analytics Team.

Love Data, Predictive Analytics, Social Media and Politics? The Analytics team for the Obama Campaign is hiring full-time analytics engineers and scientists at our headquarters in Chicago!

To find out more, come meet us at the Stanford campus ...

To find good computer scientists, the Obama campaign feels the need to look 1850 miles away. A stark  reminder that especially in the tech world, people often forget that there is an America between Oakland and Philadelphia. Google, IBM, Microsoft and Yahoo have research labs around the globe but generally ignore middle America. Chicago is often considered at best a place to change planes.

Chicago has amazing arts, music, food, sports and architecture, everything you'd want in a city and considerably cheaper than the coasts. We know we have great universities and a strong intellectual core. How many cities have a battle for the minds between the Chicago Ideas Week starting today and the Chicago Humanities Festival beginning next week?

Chicago isn't as well known for its high tech. Computer science in Chicago is good but not yet as strong as it should be. We do have some very strong CS departments nearby at Illinois, Wisconsin, Michigan and Purdue. Chicago has had its successful startups most notably Groupon. Chicago should be a major high tech hub but we need to sell ourselves better.

Next time you are stranded at O'Hare, take the El to the Loop and check out our great city. Prepare to be amazed.

Steve Jobs 1955-2011

It's one of those events. You'll always remember where you were when you heard that Steve Jobs passed away. I was at dinner with several visiting computer scientists, holdovers from the CCC council meeting earlier in the day. Our iPhones started buzzing and the news quickly spread. We gave a toast to the great Mr. Jobs.

Steve Jobs put the algorithm in our pocket. Computation moved from big rooms to the desktop to something we carry with us every waking minute. Jobs make it happen not just for us tech heads but for everyone. Jobs did it without an algorithm that analyzes data to see what the public wants. Jobs realized it takes an inner vision, a true artist to make the power of computation something we all can use.

If you find a mistake in someone elses paper you should....

What do you do if you read a paper or book and find mistakes in it? My first impulse is to say: Email the author. Always be polite and admit (which is true) that you may be misunderstanding something. A few thoughts:

1. If you offer a suggested correction then MAKE SURE IT IS CORRECT. The author may say Oh, I guess that's a mistake, I better make the correction having thought that you read it carefully. While that may well be the authors responsibility, be very careful. The first rule of proofreading is DO NO HARM.
2. If the paper is a preprint then the author should be VERY GRATEFUL since they will be able to make the correction before it becomes official. But see next point.
3. If the paper is already in a journal the author might want to correct the version on their own website. I can picture a day when the version on the authors website or arXiv are BETTER than the so-called official version. So the author should be grateful here as well.
4. For arguments sake, lets say that in Karp's classic paper Reducibility Among Combinatorial Problems, where he proves 21 problems NP-compete, he made a mistake on 0-1 programming. The problem IS NP-complete and the correct proof is in many textbooks (also, anyone reading this blog can probably do it themselves). Is it worth wasting Karp's time with this?
5. Most authors will be surprised and delighted that someone read their paper.
6. Some authors won't care. Either they left the field or they don't care about the constant they got wrong or they don't want to be bothered. That is their right; however, what to do? You can't publish an erratum for them.
7. In High School while studying some Combinatorics I came across the following passage.

   The number of ways to arrange n distinct objects is n × (n-1) × ... × 1. For example, the number of ways to arrange 5 distinct objects is 5!.

   I did not understand why they were so excited about the answer. Using an exclamation point seemed over the top. And CLEARLY there were two mistakes!
   1. The answer of 5 is WRONG. The answer should be 5 × 4 × 3 × 2 × 1 = 120.
   2. There is a spurious period after the exclamation point.
   Unfortunately I did not contact them. The mistakes are still there.

What is Random?

One can get into great philosophical debates on what is randomness. Information that we can't compress. Information that's unpredictable. Information that we are willing to bet on. 

When I define a probabilistic Turing machine I give it a special "coin state" which it enters and magically lands in a special "heads" state and "tails" state uniformly and independently each time. I imagine a computer hooked up to a little box with a coin inside that gets flipped and some sensor or camera determines whether it landed heads or tails.

I have no problems thinking about probabilistic computation just like I have no issues with quantum machines which haven't been built yet or nondeterministic machines which will never exist.

We don't care where those random bits come from as long as they fulfill the right properties. Of course our computers don't have little coin boxes so they generate randomness using pseudorandom generators which don't fulfill all the properties we expect from true randomness. So we developed theories of PRGs and under what assumptions good PRGs exist. Whether we can use them depends on whether we use randomness for searching or hiding.

We can't disprove that BPP = NEXP (everything in nondeterministic exponential time can be solved in probabilistic polynomial time). Then true randomness will give us the secrets of the universe and PRGs won't help much. Random bits would be worth their weight in gold but can we get them? I'd make a fortune selling little coin boxes. 

Bibliographies

Lots of buzz about Princeton's new policy that prevents faculty from giving away the right to publish papers on their own web pages. Never seen faculty so happy to have their rights restricted.

Princeton is behind the game for Computer Science.  All the major publishers I use explicitly give the right to authors to publish their own versions of papers on their web pages including ACM, IEEE, Springer and Elsevier. Even before, publishers rarely went after authors' pages. I have posted FOCS and Complexity papers for years and IEEE just updated their policy last November. Also see this discussion about ACM giving authors links so their visitors can freely download the official ACM versions of their papers.

We have these rights so EXERCISE THEM. No computer scientist has any excuse not to maintain a page of their papers with downloadable versions.

It gets harder to maintain these pages. I have to keep an old bibtex-to-html system running and at some point I should redo the whole page. Sites like DBLP and Google Scholar let people find my papers easily without my intervention. But if I want anyone to see all of my papers I have little choice but to keep the page going.

A candidate for a new Millenium Problem

In a prior post I wrote that the Erdos-Turan Conjecture should be a Millennium problem. Today I am going to (1) suggest a generalization of the Erdos-Turan Conjecture should be a Millennium problem instead, and also suggest (2) a far harder problem be another candidate. For some history see here. (This is an excerpt from my still-being-written book on VDW stuff- so if you find a mistake or suggestions please comment or email me.)

Recall the poly VDW theorem:

Let p₁,...,p_k ∈ Z[x] such that p_i(0)=0. Let c ∈ N. There exists W=W(p₁,...,p_{_k};c) such that for any c-coloring of {1,...,W} there exists a,d such that a, a+p₁(d), ..., a+p_k(d) are all the same color.

Much like VDW's theorem was before Gowers result, (1) there is a proof that gives bounds that are not primitive recursive (Walters proof) (2) there is a density-type theorem that does not give good bounds, (3) there is a proof by Shelah that gives primitive recursive bounds, but they are still quite large.

We make the following conjecture which we hope will lead to better bounds on the poly VDW numbers.

CONJ: Let p₁,...,p_k ∈ Z[x] such that p_i(0)=0. If Σ_{x ∈ A} 1/x diverges then there exists a,d such that

a, a+p₁(d), ..., a+p_k(d) are all in A.

1. The case where all of the polynomials are linear is often called the Erdos-Turan Conjecture. It is still open.
2. The following is a subcase that is orthogonal to the Erdos-Turan Conj: If Σ_{x ∈ A} 1/x diverges then there exists two elements of A that are a square apart.
3. Green and Tao showed that the set of primes have arb. large AP's. Then Tao and Ziegler showed the following: Let p₁,...,p_k ∈ Z[x] such that p_i(0)=0. There exists a, d such that
   
   a, a+p₁(d), ..., a+p_k(d) are all primes.
   
   SO the CONJ is true for a particular set of interest.

We also pose a question which is more interesting but likely much harder:

If A is a set then let d_A(n) =|A ∩ {1,...,n}|/n. The lim sup_{n → ∞} d_A(n) is the upper positive density. We will be interested in the function d_A(n).

QUESTION: Let p₁,...,p_k ∈ Z[x] such that p_i(0)=0. Find functions e₁(n) and e₂(n) (not that far apart) such that e₁(n) ≥ e₂(n), and the following occurs:

1. If for almost all n, d_A(n) ≥ e₁(n) then there exists a,d such that a, p₁(d),...,p_k(d) ∈ A.
2. There exists A such that, for almost all n, d_A(n) ≥ e₂(n), and there is NO a,d such that a, p₁(d),...,p_k(d) ∈ A.

For the case of 3-AP's the following are known:

1. If for almost all n d_A(n) ≥ (log log n)⁵/log n then A has a 3-AP. (See this Tom Sanders paper.)
2. There exists a set A such that, for almost all n d_A(n) ≥ 1/n^{\sqrt(log n)} and A has no 3-APs (See Michael Elkin's paper for a slightly better result that I didn't have the energy to typeset.)

These two functions are NOT close together. So even in the case of 3-AP's we do not know the answer. I want to know the e1,e2 for ALL finite sets of polynomials with 0 constant term. We've got our work cut out for us.

It is my hope that progress on the question will lead to better bounds on some poly VDW numbers. A similar question DID lead to better bounds on the VDW numbers.

Moneyball

I saw Moneyball over the weekend. This movie gives a fictionalized account of the how the general manager of the 2002 Oakland A's used the right kind of statistics to build a strong team with a low budget. This article on the GM Billy Beane gives a nice follow-up to the movie.

A bit surprising one can get a good movie about the math in baseball. Moneyball was based on the book by Michael Lewis with a screenplay co-written by Aaron Sorkin who also wrote the screenplay to the Social Network. Sorkin writes nerdy things well.

Moneyball is really a computer science movie. It's not about the computers themselves which play a small role, but its about taking a large amount of data and deriving the conclusions that help make the crucial decisions in developing the team.

You can also see the difference in computer science over the last decade. At the time of Moneyball, people would try many statistical models and test them out. These days via Machine Learning we give the computer the data and the results and the computer determines the right models.

Oddly enough Billy Beane's actions led to an even greater separation between the large and small market teams. The statistical ideas that Beane pushed have been adopted by the other teams. Now we've hit an equilibrium so the teams that spend more win more as well.

Oddly the New York Times ran an editorial piece Not-So-Smart Cities by Greg Lindsey yesterday arguing that cities shouldn't rely on these kinds of statistics for planning because of a failed project from the 60's. Sounds like Lindsey needs to see Moneyball.

Mahaney's Theorem

Bill has a lot of posts where he questions whether to teach Mahaney's theorem in a graduate complexity class. Since it is one of my favorite theorems and most of you young folk won't see a proof in your complexity classes, I'll give it here. This proof is not the original of Mahaney but based on a paper by Ogihara and Watanabe.

Mahaney's Theorem: Let c be a constant and A be set such that for all n, A has at most n^c strings of length n. If A is NP-complete then P=NP.

Proof: We define the left-set of SAT as follows: Let B = { (φ,w) | φ has a satisfying assignment a with a ≤ w in lexicographic order}. We'll restrict ourselves to w that are (not necessary satisfying) assignments for φ.

Assume φ is satisfiable and let a' be the lexicographically smallest satisfying assignment. We have (φ,w) is in B iff w ≥ a'.

Since B is in NP by assumption B reduces to A via some function f computable in polynomial-time, (φ,w) is in B iff f(φ,w) is in A.

Fix φ and n and let m=n^k bound the number of strings in A of any length that f(φ,w) could query. Pick w₀ < w₁ < w₂ < … < w_m+1 evenly spaced from each other.

Let z_i = f(φ,w_i) for each i. Note that if z_i is in A then z_j is also in A for all j ≥ i.

Case 1: z_i = z_j for some j > i. We know a' cannot be between w_i and w_j.

Case 2: All the z_i are distinct. There are only m elements in A so z₁ is not in A and a' cannot be between w₀ and w₁.

Either way we have eliminated a 1/(m+1) fraction of the possible assignments.

We repeat the process choosing the w_i equally spaced among the remaining possibilities and eliminate another 1/(m+1) fraction of those assignments. We continue O(mn) times until we narrow down to a set S of m+1 possible assignments.

If φ is satisfiable then a' is in S so at least one assignment in S and will satisfy φ. If φ is not satisfiable then none of the assignments in S satisfy φ.

By trying all the assignments of S and seeing if they satisfy φ, we get a polynomial-time algorithm to determine if φ is satisfiable. Since Satisfiability is NP-complete we have P = NP.

Where do theorems go to die?

(Joint post by Bill Gasarch and Daniel Apon)

Recently I (Daniel) reviewed Dexter Kozen's Theory of Computation (it was AWESOME). You can find the review here. Many of the topics were standard but some we (Bill and Daniel) suspect are not covered in any complexity class (well... maybe in Dexter's). This DOES NOT detract from the book, however we now raise the question:

Where do Theorems go to die?

In some eras there are some theorems that are taught in EVERY basic grad complexity courses Then all of a sudden, they are NOT taught at all. (Both the EVERY and the NOT are exaggerations.)

1. The Blum Speedup theorem: In the 1970's EVERY comp sci grad student knew it. In the 1980's EVERY theorist knew it. In the 1990's EVERY complexity theorist knew it. In the 2000's (that sounds like it means 2000-3000) EVERY... Actually NOBODY knew it, except maybe students who took Dexter's class. I doubt Blum teaches it anymore. Blum's speedup theorem was proven before Cook's theorem when people were still trying to get complexity right. Blum has since said Cook got it right! Even so, Blum's Speedup theorem should be in the preface to God's book of algorithms (See here) as a warning that there might not be an optimal algorithm.
2. The Complexity of Decidable theories (e.g, Presburger, WS1S, S1S, S2S). We all know that by Godel's theorem the theory of (N,+,times) is undecidable. There are some subtheories that are decidable. However, the decision procedures are complete in various rather high up classes (WS1S is provably not primitive recursive). This material I (Bill) learned from Michael Rabin (who himself proved S2S undecidable) in 1981 but my impression is that it is not taught anymore. Was it ever widely? We think that students should know the STATEMENTS of these results, because these are NATURAL problems (Bill did the capitalization) that are complete in classes strictly larger than P. (See the second conversation here for comment on that.) One of us thinks they should also know the proofs.
3. omega-Automata. This is used to prove S1S decidable and we've heard it is used in fair termination of concurrent programs. Sounds like it should be more well known. But it is rare to find it in a complexity cousre. It may well be taught in other classes. (I (Bill) touch on it in undergrad automata theory.)
4. Jon Katz is pondering not teaching Ladner's theorem!!! The students should surely know the result (YES, and stop calling me Shirley) however, should they know the proof?
5. Spare Sets: Bill Blogged about no longer doing Mahaney's Theorem Karp-Lipton is still used A LOT, but Mahaney's theorem is not really used at all. Daniel thinks Mahaney's Theorem is AWESOME, however Daniel is bright eyed and bushy tailed and thinks ALL of this stuff is AWESOME.
6. Computability Theory: Friedberg-Muchnik, Arithmetic Hierarchy, Analytic hierarchy, Recursion Theorem. This is like Blum Speedup- this material used to be better known to complexity theorists but is hardly taught to them anymore. It IS of course taught in courses in computability theory. But such courses are taken by complexity theorists far less often then they were. When I (Bill) tell someone there are c.e. sets that are not decidable and not complete! they say Oh, just like Ladner's theorem. Its the other way around, Ladner's result came far later.
7. Part of this is that Complexity theory has changed from Logic-Based to Combinatorics-Based (see post on CCC Call for papers) We don't teach Blum Speedup (and other things) any more because we have better things to teach. However, are there results that the students should know even if the fields they come from are dead? YES, and Ladner's theorem is one of them.

Who decides such things? Textbook writers for one. A Proof Theorist who worked on lower bounds for Resolution told me he hopes that Arora-Barak's book would include this material. He even said If it does not, the field will die. Is this true? If so then Arora and Barak have more power than they realize.

Conferences Again

Lots of conference news and views going around. Let's sort it out.

FOCS early registration deadline is September 29th, fast approaching. Deadline for applying for student support is this Thursday September 22. Apply even if you don't have a paper there and take the opportunity to attend one of theory's most important meetings.

Also the STOC 2012 submission deadline is still November 2. There was a mistaken deadline listed on a theory events site.

The SODA 2012 accepted papers (and links to Arxiv) are out. Program Committee Chair Yuval Rabani explained the PC process. Seems pretty much along the lines of PCs I've been apart of. I wished they did penalize people who had poorly written papers, otherwise there's little incentive to write well. I'm also not a big fan of the "pet paper" idea, people tend to choose papers of their friends and colleagues.

Michael Mitzenmacher posted about the number of good papers not accepted and whether SODA should accept more (an issue at most of our major conferences). In this blog, Sami Khuller guest posted about whether it makes sense to have SODA in Japan. There are a handful of SODA accepts with primarily Japanese and other Asian authors but the vast majority of the authors are US-based.

Some of the comments on Khuller's post talked about having a virtual conference. How about this idea: We don't bother meeting and just collect the accepted papers into a single volume. We can give this idea an innovative name like a "journal".

In this month's CACM article, Moshe Vardi complains about the quality of conference talks. (I like the "journal  that meets in a hotel" quote but it didn't originate with me). You see this at STOC and FOCS too, people giving a talk only to other specialists in their field instead of aiming for a general audience.

Most of you readers know my position on conferences, that we need to get conferences out of the ranking business in CS so conferences can instead play their role of bringing community together and escape from the explosion of conferences just to give people who were rejected from another conference a place to submit their papers.

Happy Constitution Day

September 17th officially is known in the United States as "Constitution Day and Citizenship Day" but is celebrated today because the 17th this year falls on a weekend. I  have nothing but love for the our Constitution. Not only does the Constitution and its amendments provide the great freedoms we have in America but it also shows how to balance states of different sizes with a strong central government. The EU could do worse than by following its example.

What bothers me is a law that Robert Byrd snuck into an omnibus spending bill in 2004.

Each educational institution that receives Federal funds for a fiscal year shall hold an educational program on the United States Constitution on September 17 of such year for the students served by the educational institution.

With a few exceptions like the military academies, US universities are either run by the states, municipalities or are private institutions. It defeats the whole point of the Constitution for the Federal government to be dictating to US universities what educational programs must be held when.

Most universities do the minimum. Northwestern just points students to a website with Constitution related information and videos.

To help all of you celebrate Constitution Day here is the great preamble as I learned it as a kid.

Conventions in Math- just to make the rules work or more?

1. Why is

   a^1/2 = sqrt(a)?

   true? To make the rule

   a^x+y=a^x a ^y

   work out.
2. Why is

   (∀ x ∈ ∅)[P(x)]

   true? To make the rule

   (∀ x ∈ A ∪ B)[P(x)] iff (∀ x ∈ A)[P(x)] AND (∀ x ∈ B)[P(x)]

   work out.
3. Why is the sum over an empty index set equal to 0 and the product over an empty index set equal to 1? Same reason- it makes various math laws work out.

For the second and third item on the above list I would say its not JUST to make some rule work out, it also makes sense. But the first item, that a^1/2 = sqrt(a), seems to only make sense in terms of making a rule work out and not for any other reason. I have no objection to the rule; however, if you have a REASON other than it makes the rules work for this convention, please leave a comment.

Imagine

Looking back, it's pretty amazing how new technologies like Google, cell phones, Facebook and Twitter have changed society in completely unexpected ways. Let's play a game with an up and coming technology that will surely change society but it is not clear yet how.

We already have the technology for autonomous cars, cars that can drive themselves with no needed changes to roads or other cars. By 2020, this technology will be cheap enough to be built into most new cars.

1. When will society and laws be accepting of autonomous driving? Will we ever be able to get rid of the drivers seat?
2. What will cars look like when there is no driving seat?
3. Will there be a major elimination of jobs of taxi and truck drivers? Is this a bad thing?
4. Will we still need parking right near our destination? Will driveways disappear?
5. Once most cars are autonomous will they be networked for better coordination? Will we see the elimination of now unneeded street lights and signs? Will there be privacy concerns?
6. These cars will stop or serve around obstacles. How do we stop pedestrians from just walking out in front of cars knowing they will stop?
7. Will people mostly own cars or just rent one that happens to be close by?
8. Suburbia exists because of the automobile. Will an autonomous car change the nature of suburban life?
9. Most importantly, what is the big societal change that will occur that we can't imagine right now.

Guest Post on Conference Locations

(Samir Khuller Guest Post.)

On Conference Locations:

I recently looked at Orbitz for fares to Japan for SODA 2012 in Jan. The round trip fare from DC to Tokyo is close to $1700. Together with the train to Kyoto, we are looking at a $2000 travel cost to attend SODA for 3-4 days. Together with the registration and hotel, I am sure the cost will exceed $3000. I wonder how many people will be able to attend this conference? In times of declining budgets, we should make these decisions after careful thought since our travel budgets are only shrinking. In 2012, all conferences are likely to be expensive to attend -- SODA in Kyoto, CATS in Melbourne, STACS in Paris, Complexity in Porto, ESA in Slovenia, ISMP in Berlin, ICALP in UK, SWAT in Finland, LATIN in Peru, SIGMETRICS in UK, FST&TCS in India, not to mention all those exciting Bertinoro and Dagstuhl meetings. At least STOC is in NYC!

I am sure that the same dilemma is faced by people in the far east when we hold conferences in the US. However, I will be curious to know what the numbers look like. Are we going to reduce costs for 25 students who otherwise might not be able to attend SODA because its not in Japan (I hope this NOT the case, and the numbers look much better)? However, at the same time we might be making the cost prohibitively high for 100 students who could have attended the conference, but are not going due to the high cost. Wait, we did this once. We had FOCS in Rome! According to this blogpost it looks like only 172 people registered for FOCS 2004. Given that most likely 100 of the attendees were authors, the drop in attendance of non-authors is by a factor of 50% since FOCS most likely gets close to 230 attendees.

I am for the argument that once in a while its not bad to move a conference around to help people attend who normally might not; but we could explore other ways of helping such people attend. Once we move a conference to a place where not much local population will attend, its a problem (FOCS 1991 in Puerto Rico). SODA in Israel or Germany makes more sense to me since a large part of the algorithms community is from those places. One way to help defray the costs is to use part of the conference funds to help provide travel support for people whose cost to attend would be too high. Co-locating meetings might benefit us more (FCRC, ICALP-STOC 2001 in Crete). If we want to maximize interaction among people we should aim to have one large meeting as opposed to lots of small ones - the ISMB and ISMP conferences do this very well. More edges in a clique of 1000 nodes than 10 cliques of 100 nodes each. ALGO in Saarbrucken makes sense to me. High density of researchers, several meetings are combined into one along with ESA. Frankfurt is easy to get to from a lot of places in the world (except for the folks in Australia, NZ and Hawaii), and there is great train service from the airport to Saarbrucken.

One of the cheapest conferences I attended was the SIAM Conf. on Discrete Math at the University of Toronto campus. Very low registration cost and we could stay on campus in the dorms for $20/day. Having looked into (and having organized) conferences recently, I know that the dinner can cost $100/person, and the coffee break $20/person. Do we really need to have academic conferences at such large hotels and hard to reach places? Why not have a conference that encourages participation, as opposed to one that discourages it? Even I would not mind a conference in space, lets see if NSF would approve "foreign travel" for that one.

I am going to have to start a new US "regional" conference, that I can afford to send my students to! It will be held on a university campus and the reg fee will be $100/student; and it will be cheap to get to. At least for the years when SODA is not in the US, such a meeting might be a success.

NOTE: I have nothing against Kyoto and Rome, they are among my favorite places in world.

Next in the sequence

When I posted on sequence problems here some people said that they did not have unique answers. Many problems FORMALLY do not have a unique answer, but common sense and simplicity lead to a unique answer. This recently happened on Jeopardy. The topic was Next In The Series. I'll give the questions here and pointers to the answers (actually the answers here and pointers to the questions since Jeopardy is an answer-and-question game.) Do you think some of these have non-unique solutions? If so, what are the other solutions? Are those problems unfair? As always I ask nonrhetorically. (my spell checker wanted me to put a space between non and rhetorically. I disagree.)

1. FA, SOL, ... NEXT
2. In the US Army: First Lt, Captain, ... NEXT
3. XXXVIII, XXXIX,... NEXT
4. FEDERAL HOLIDAYS: Memorial Day, Independence Day, ... NEXT
5. Orange, Yellow, (Wavelength around 510 nanometers)... NEXT