The Value of an Academic Publication

Russell O'Connor's paper was accepted into last years ACM SIGPLAN Workshop on Generic Programming. Russell put the final version of his paper on the ArXiv under a public domain dedication. Russell couldn't transfer author's rights to the ACM since he gave them up. After much discussion the ACM decided not to publish the paper in the proceedings. The abstract in the proceedings states

We note that one of the papers presented in the workshop is not included in the proceedings. This paper, "Functor is to Lens as Applicative is to Biplate: Introducing Multiplate" by Russell O'Connor, is accessible as arXiv:1103.2841v2 [cs.PL].

Russell gives his account but he focuses on ArXiv instead of the public domain aspect. In the STOC CFP we encourage putting your submissions on ArXiv and similar sites. The issue that worried ACM was the loss of rights. ACM could have published the paper, it was in the public domain, but it wouldn't have control of that publication and didn't want to set precedent. Scott Delman of the ACM responded here.

An academic paper you write has little direct value to you (the paper itself not the Intellectual Property within). No one is likely to give you any money for that paper. But your paper does have financial value as part of a collection in a journal or conference proceedings. Commercial and non-profit publishers know how to collect on this value. You might complain that this puts your paper behind a firewall but all the major publishers in CS allow you to post earlier drafts on your homepage and archive sites. As long as you make that effort, people will have access to your papers.

It does take some money (or considerable person hours) to maintain even an electronic journal or conference proceedings. But publishers get more value than that. For the ACM, the DL revenue is a major source of funding for ACM activities and those of the SIGs.

Of course you should never trust the opinion of someone who has a financial interest in a position and as SIGACT chair, we certainly make use of the DL revenue. We are hoarding some in case the DL revenue shrinks in the future.

It seems a shame to leave the monetary value of our papers on the table but also that value shouldn't be exploited. Big discussions will continue on the publications issue, at ACM and other publishers and at all levels of the CS community. There will be a Dagstuhl workshop focused on this topic in the fall. Figuring out the right model for publications will not be an easy one.

My biggest fear is that lack of a plan will lead to a degradation in the quality of our publications and then everyone loses.

Sanjeev Arora wins ACM-Infosys Award

Sanjeev Arora will receive the 2011 ACM-Infosys Foundation Award, the highest honor ACM gives to a mid-career scientist.

Sanjeev Arora is one of the architects of the Probabilistically Checkable Proofs (PCP) theorem, which revolutionized our understanding of complexity and the approximability of NP-hard problems. He helped create new approximation algorithms for fundamental optimization problems such as the Sparsest Cuts problem and the Euclidean Travelling Salesman problem, and contributed to the development of semi-definite programming as a practical algorithmic tool. He has played a pivotal role in some of the deepest and most influential results in theoretical computer science, and continues to inspire colleagues and new generations of researchers.

Congratulations to Sanjeev!

In other news, the IEEE Computer Society W. Wallace McDowell Award is being awarded to Ron Fagin, and the US gives a big push for big data (CCC blog has details).

Another reminder for upcoming deadlines: STOC Posters (3/31), ACM Turing Student Travel (4/2), STOC Student Travel (4/4) and FOCS papers (4/4).

"Math was a mistake- I made it too hard"

(REMINDER- IF you are a STUDENT who wants to GOTO STOC 2012 but needs money to go then you should GOTO the STOC 2012 homepage and click on Travel Support. Deadline to apply: April 4.)

In the movie Oh God Book II God, played by George Burns, says

Math was a mistake, I made it too hard

Or at least I thought he said it. I have repeated this quote both in the blog and as a comment on Scott's blog. As I noted on my blog, if you Google

"Math was a mistake, I made it too hard"

all of the hits that you get lead back to me. This is still true. (Though it won't be after this post goes up.)

I thought it was a great quote so I am surprised it is not better known. FINALLY Oh God Part II came TV so I watched it just to see if what I've been quoting all these years is really in the movie. (Also, its a pretty good movie, for what it is.)

Alas, that is NOT the quote! What God really said was

"Mathematics, that was a mistake. I should have made the whole thing a little easier"

I think my version is better.

There are other misquoted quotes. My favorite: Stalin never said

The capitalists will sell us the rope with which we will hang them.

He did say:

The capitalists will furnish credits which will serve us for the support of the Communist Party in their countries and, by supplying us materials and technical equipment which we lack, will restore our military industry necessary for our future attacks against our supplier. To put it in other words, they will work on the preparations of their own suicide. (The Yale Book of Quotations (2006))

Both for George Burns and Stalin I am troubled- are we better off using the pithy version of the quotes, which DOES capture what they meant, or the original?

We have a similar issue when we teach- do we teach math the way it was invented or discovered (messy but motivated) or the way it is understood now (clean but unmotivated). Hopefully its not an either-or question and we can do some of both.

What is an Elegant Proof?

What is an elegant proof? I do not know and I doubt it can be well defined; however, we all know it when we see it. I welcome comments on the topic; however, I will give a very simple example for a contrast of elegant and non-elegant. All of the math discussed here informally is done formally here.

Consider the following theorem:

There is no 2-digits number that is the sum of the squares of its digits.

One crude measure of elegance is to minimize the number of numbers that you need to check directly are not the sum of the squares of their digits. With this in mind. With this in mind, here are several proof sketches.

1. One could proof this by enumerating all possible 2-digit numbers. If you wrote a program for this then you could use it on similar problems. Even so, I suspect most of us would call this proof NOT ELEGANT. This requires 89 CHECKS.
2. There is a proof that first easily eliminates 10, 20, 30, 40, 50, 60, 70, 80, 90 and then looks at every interval [11,19], [21,29], ..., [91,99]. More elegant than enumeration and certainly shorter. This required 8 CHECKS.
3. There is a proof that looks at the equation 10a + b = a² + b². We look at it mod 2, mod 4, and mod 10. This gives what I thought was the most elegant proof; however, after writing it down carefully it was about the same length as the interval proof. This required 2 CHECKS.

Consider the following theorem:

There is no x ≥ 2 that is the sum of the squares of its digits.

The cases of 2 ≤ x ≤ 9 and x ≥ 100 can be done with zero checks, so using the best proof of the last theorem, we can do this theorem with 2 checks.

Consider the following theorem.

The only 3-digits number that is the sum of the cubes of its digits is 153. (NOTE ADDED LATER: This is INCORRECT. A commenter pointed out that 370, 371, 407 also work. I will fix the proof and statement later and see if these are the only ones. Score a point for the `do it by a computer enumeration' argument!)

I have a proof of this which is... not quite elegant but not brute force. I get it down to only 21 CHECKS. If you have a better proof in terms of NUMBER OF CHECKS that is not contrived to reduce NUMBER OF CHECKS I would be very interested to see it. Of course, I cannot define contrived rigorously or elegantly.

David Waltz (1943-2012)

David Waltz, head of the Center for Computational Learning Systems at Columbia, passed away yesterday after a battle with a brain tumor at the age of 68.

David Waltz is best known for his research in artificial intelligence but I'll remember him most for his leadership of the NEC Research Institute when I was there. David fought hard and risked his career to protect basic research, particularly theory, at NEC. He would end up losing the presidency of NEC in this conflict. It is a great leader that is willing to risk all to support his people.

A Busy Time of The Year

It's spring break week at Northwestern so life is supposed to be quiet. No such luck.

Endre Szemerédi will receive the 2012 Abel Prize, perhaps the most prestigious annual award in mathematics. Tim Gowers has a nice summary of his work.

With this tweet the head of Yahoo Research officially leaves for Google.

Farewell @YahooLabs it was a fantastic ride. Hello @google
— prabhakar raghavan (@WittedNote) March 20, 2012

This likely marks the beginning of the end for what was a great corporate research environment.

FOCS submission deadline is April 4. There are some minor changes in the submission format from last year.

Registration for the ACM Turing Centenary Event is full but students can still attend through a limited number of ACM SIGACT Student Scholarships.


Registration for STOC is now live. The final program will be posted soon.

• Submit to STOC's second poster session. Deadline March 31.
• Student Travel grants are available Deadline April 4
• This STOC will have the inaugural Student Presentation Award

Even as I write this post, breaking news that U. Illinois president Michael Hogan resigned. Can't wait to see what Jeff has to say about this.

Heading South

Starting in July, I'll be chair of the School of Computer Science in the College of Computing at Georgia Tech. Annie Antón from NC State will chair the School of Interactive Computing. Here's the official announcement. I'm truly excited to be working with Annie, the Dean of Computing Zvi Galil and the incredible faculty there to move Georgia Tech forward.

I can anticipate many of your questions: How does moving from the land of Lincoln to the land of Lipton affect the blog? How do I get a job at Georgia Tech? Wait, does this mean there is a theory opening at Northwestern? Is this really the fourth job you've had since starting the blog ten years ago? All in due time.

Intel Science Talent Search

Last week I went to the Intel Science Talent Search Awards Ceremony in DC, probably the most prestigious math and science competition for American high school students.

I mentored one of the finalists, Adam Kalinich, of the Illinois Math and Science Academy. Adam studied poset games, where each player takes turns picking an element x of a finite poset and removes all y ≥ x. First one to empty the poset wins. The complexity of deciding who wins a poset game is wide open. Adam showed how to convert a game where one players wins to a game where the other wins, a surprisingly tricky task. His paper appeared in IPL (also on ArXiv).

Lots of math and computer science among the finalists and winners. The other Illinois finalist, Jordan Cutler, worked on practical implementations of quantum cryptography with Prem Kumar, another professor in my department. Jordan, who is a cousin of complexity theorist Steve Homer, came in 10th place.

Anirudh Prabhu had the coolest math result on perfect numbers. It's been conjectured that there are no odd perfect numbers. Anirudh showed a non-constant lower bound for odd perfect numbers (if they exist) as a function of the number of factors. Only constant lower bounds were known before. Anirudh came in 7th place.

David Ding got 4th place for his work on representation theory of Cherednik algebras. I don't know what those are either.

First place went to Nitin Tumma for work related to cancer.

The ceremony itself was a great scene. I'm a sucker for the pomp and circumstance. Walter Isaacson gave the keynote address and we all got autographed copies of his biography of Steve Jobs. Great fun was had by all.

I've seen the future of American science and it is awesome.

Judea Pearl wins Turing Award

(In this age of lightenting fast communication I suspect you all already know that Judea Pearl won the Turing Award. Even so, it is worth posting about.)

Judea Pearl has won the 2011 Turing award (given in 2012). (see here for the announcement). He is not a theorist; however, he did champion the use of probability and graph theory in AI.

Strong AI is the attempt to make computers match or exceed human intelligence. People in Strong AI might see how humans do things and try to get a program to mimic that. Putting aside philosophy (are we all just rather complicated DFA's?) the goal of Strong AI seems to just be hard to do even if it is possible (complexity issues?)

Weak AI has more modest goals (and a much shorter Wikipedia Page)- lets get a computer that can do a well defined task (e.g., Medical Diagnosis) well. They want to get things to work and may very well NOT take how humans do it as an inspiration. Do humans do the kinds of probabilistic calculations that Judea Pearl works with? I tend to doubt it.

Once Strong AI produces real results it is called Weak AI. Once Weak AI produces real world products its called something else (Robotics, Nat. Lang Proc, Vision, there are other examples).

I ask all of the following nonrhetorically. NONE of the questions are meant to question the award.

Did Judea Pearl work in Strong AI to Weak AI?

Was Judea Pearl one of the first people to incorporate serious AI on a more rigorous foundation?

Does AI use serious math? (I know that Control theory does, though is that AI?)

Did Judea Pearl (or his group) build software that is actually being used someplace?

What is the criteria for good work in AI?

Who might be the next AI Turing Award Winner?

How do legit fields of knowledge decide between competing theories? How does Astrology?

Euler was born April 15, 1707. Hence by the Western Astrology that we all ignore he is an Aries. However, I recently heard about another way (also worth ignoring) of doing the signs where he is a Pisces (see here). The other system has 13 signs. (There are some other systems, all worth ignoring, here.) For a serious article about what astrology really claims to say and why its worth ignoring see here.

What does a field of study do if there are several competing theories?

1. The Natural Sciences: I would like to think that the truth wins out... eventually. There may be struggles and politics and whatnot but in the very end experiments are performed and the more predictive theory wins out (I know its more complicated then that.) There are some fields where it is hard to do experiments (e.g., String Theory). Others where the theory gives great explanatory power but might be hard to do direct experiments (Evolution). Those cases may be hard to deal with, but they manage. Does String Theory have great explanatory power?
2. Mathematics: Here the question is not WHAT IS TRUE since we can use proofs (Again, I know its more complicated than that) but WHAT IS WORTH STUDYING. Applied Math may still use the real world for a litmus test to some extend. More abstract kinds of math may be harder to test by looking at the real world. Do Large Cardinals exist? Is the Axiom of Determinacy true? Some people claim that they look for internal consistency and also intuitions. And some people live-and-let-live (you want to use AC, fine, I won't) (Again, I know its more complicated than that.)
3. Astrology : What does a field do when its predictions are either vague or no better than chance? If there was a well designed experiment to test which theory has more predicative value then I suspect they would all be found wanting. (Then again, I'm a Sagittarius and we are known to be skeptical.) So what other criteria could they use? Internal Consistency and Intuition? Whichever one makes people feel better (some astrologers might claim that they are really psychologists, telling people what they want to hear to sooth them). Whichever sells more books? Makes more money? Is there some sort of aesthetics involved? I ask this nonrhetorically. (An idea for a scam: The old astrology doesn't work because they don't take into account relativistic effects on the planets. Use my Relativistic Astrology! For people who like what they believe in to have some buzz words from science thrown in!)

This does raise the general question- if there are competing theories in a field where its hard or impossible to do experiments, what does a field do? Whoever yells loudest wins?

March Madness

Once again, America's favorite binary tree, the NCAA Men's National Championship Bracket. The tree seems to get more unbalanced every year. There are four regions, the East has the traditional 16 teams, the West and South have 18 teams each and the Midwest has 19 teams for a total of 68 teams. Single elimination starts tomorrow.

Many Americans participate in office pools where they fill out the bracket to predict which team wins each game. There's lots of math one can use for your bracket. But here is my advice: Pick the higher seeded teams to beat the lower seeded teams. Every time. There will be upsets but you can't predict where they will be so you have the best chances predicting none of them.

The most likely seeds to make the final four are two number 1's, a number 2 and a number 3, 3 times in the last 27 years. So why follow my advice which predicts four number 1's. Because there are 12 ways to get 11 2 3 and only one way to get 1 1 1 1 and you have to pick a specific combination when you fill out your bracket. The four first seeds all went to the final four only once in the last 27 years but given there's only one such combination that makes it more likely than any other possibility. 

May the madness begin.

Scott wins the Waterman

The NSF's most prestigious prize, the Alan T. Waterman award, recognizes an outstanding young scientist (35 or under) in any field of science or engineering. Breaking with tradition this year the NSF picked not one but two winners, computer scientists Scott Aaronson (MIT) and Robert Wood (Harvard).

Most of you readers know Scott well. He's already an established leader in quantum computing and computational complexity and has his own awesome blog. Not sure why NSF decided to use a photo of Scott proving Karp-Lipton wearing a skirt. The CCC blog post points to Scott's TedxCaltech talk. I'll just link to the podcast I had with Scott back in 2005.

Computational complexity has won two Watermans in the last three years as Subhash Khot received the award in 2010.

Robert Wood is the principal investigator of the RoboBees project, which is pretty much as the title suggests, insect-inspired robots. Sweet revenge for being called the number one example of government waste by Sean Hannity.

When a+b is harder than b+a

Is 1+4 a harder calculation than 4+1? It may be if you are 2+3 years old. I asked my 7-2 year old great niece Noelle the following sequence of questions. I include how long it took her to answer.

Bill: How old are you?

Noelle: (2 seconds) 5

Bill: What is 3+2

Noelle: (3 seconds) 5

Bill: What is 2+3

Noelle: (2 seconds) 5

Bill: What is 4+1

Noelle: (1 seconds) 5

Bill: What is 1+4

Noelle: (8 seconds) 5

Bill: What is 7 take away 2

Noelle: (4 seconds) 5

Bill: What is the least d such that there is general dth-degree equation.

Noelle: (11 years) 5

Bill: What is the least k such that the kth Ramsey Number is not known

Noelle: (21 years) 5

The most interesting of these to me was that 1+4 took much longer than 4+1. Why is this? To do 1+4 she starts at 1 and adds 1 to it four times so its 1 + 1+ 1+ 1+ 1. To do 4+1 she starts with 4 and adds 1 once, 4+1. More generally, if we don't use the addition is commutative and we view +1 our basic operation than the complexity of a+b is b.

It is important to realize that concepts such as commutativity of addition which are now obvious to us as adults, there was a time when it was not obvious. Or perhaps not obviously useful for calculations.

Could a model of children's addition be defined and studied? Would this be a Math Project, a Math Ed Project, or a Child-Development Project? Has it already been done? I suspect that how children learn things has been studying extensively, but that well defined questions of complexity-of-children's-addition has not. My ONE data point suggests that the complexity of a+b is b, but to really study this you would of course need more samples. SO, if any of you relatives that are 5 or under (but can talk), and try this out, let me know what you find.

The Internet of the Present

On this blog we rarely get non-spam comments on posts more than a few days old. Sometimes I can bring up a topic I had posted on just a few months ago and no one will notice. When people said they enjoyed my blog I used to ask them what posts they liked. I would just get a blank stare. I don't ask anymore.

In theory you can look at our old posts through the "Blog Archive" section on the left column (if you are reading this on the blog website). I doubt anyone actually does. Occasionally people get to old posts via Google searches but I've come to the realization that most posts I wrote more than a few weeks ago will never be read again.

That's too bad. Many of them are still quite relevant. But we live in the present. I'm just as guilty as everyone else. Sometimes I'll discover a great new blog and subscribe to its posts. But I'll never go back and read the old posts.

Blogs seem to be going out of style. Twitter don't even try, one cannot easily see someone's old tweets, and any brilliant tweet I make will expire in usefulness in a just a few hours. Google+ is similar. Interestingly Facebook with their new Timeline makes it possible to explore someone's early posts. The past remains there just in case someone cares.

I have no great insights or solutions to this problem. But what does it matter. A week from now you'll forget this post even existed. 

Turing's Titanic Machine!

In the March CACM, Barry Cooper writes

We quote Peter J. Denning introducing the ACM Ubiquity Symposium on "What is Computation?" as saying: "Researchers in biology and physics have claimed the discovery of natural computational processes that have nothing to do with computers."

With Lance Fortnow distinctly underwhelmed: "Some people outside of computer science might think that there is a serious debate about the nature of computation. There isn't."

As often happens when experts disagree, the truth lies somewhere in between.

No it doesn't. My extreme point of view: A strong belief in the Church-Turing thesis that Turing machine captures the true notion of computation now and forever.

What's next? Casting doubt on 1+1=2? Sure no one has yet proved 1+1=3 but that doesn't mean it won't happen someday.

The Erdos- de Bruijn theorem

The mathematician Nicolaas Govert de Bruijn passed away on Feb 17, 2012. The number of things named after him is quite large. I will discuss the Erdos-de Bruijn theorem.

Erdos-de Bruijn theorem: An (infinite) graph G is k-colorable iff every finite subgraph is k-colorable.

I will sketch the proof for the case where G is countable. We can assume the vertices are {1,2,3,...}. Let COL_i be a k-coloring of G restricted to {1,...,i}. We will use the COL_i's to obtain a k-coloring of the entire graph G. We can assume the COL_i's use colors {1,...,k} so we can speak of the least color j such that blah blah.

We color node 1 by the least color that an infinite number of the COL_i's color 1. Then REMOVE all of the COL_i's that do not use that color on 1. (We kill all those that disagree with us! as I told my students.) Note that there are still an infinite number of COL_i's left.

We color node 2 by the least color that an infinite number of the COL_i's THAT ARE LEFT color 2. Then REMOVE all of the COL_i's that do not use that color on 2. Note that there are still an infinite number of COL_i's left.

And so on.

End of Sketch of Proof.

1. This type of argument can be used to proof the following:
   1. If we already have the infinite Ramsey Theorem on N, we can obtain the finite Ramsey Theorem and (with a small trick) the Large Ramsey Theorem.
   2. If we already have the finite dilworth theorem (any FINITE partial order of width w can be covered with w chains) then we can obtain the infinite version of Dilworth's theorem: if an INFINITE partial order has width w can be covered with w chains.
2. The method is called compactness argument and is very general. It is related to topological compactness, but I won't to into that here. (If a reader has a short explanation or pointer, please post.)
3. The method is noneffective in that if you are given a Turing machine that tells you, for all i,j, COL_i(j), then the proof does not appear to be able to give you a Turing machine for a coloring of G. There are two ways this has been formalized, though I list three since the third one strengthens the second one. (For details see my survey of recursive combinatorics here.)
   1. (Bean, 1976) There is a computable graph (Vertex set N, Edge set decidable) that is 3-colorable but there is no computable finite coloring whatsoever. (He also made the graph planar, which was not needed but nice.)
   2. (Carstens and Pappinghaus, 1983) For every k ≥ 3 There is a highly computable graph (Vertex set N, the function that, given a graph, outputs its finite set of neighbors is computable) that is k-colorable but not computably k-colorable. (NOTE: if a highly comp. graph is k-col then IT IS computably 2k-1 colorable.)
   3. (Schmerl, 1980) For every k ≥3 There is a highly computable graph (Vertex set N, the function that, given a graph, outputs its finite set of neighbors is computable) that is k-colorable but not computably (2k-2)-colorable.

Nash and the NSA

By now most of you have heard about Nash's recently released letters to the NSA (press release, letters). Not only did John Nash think about computation and cryptography, there are many ideas in these letters that were a bit ahead of their time when Nash sent these letters in 1955.

• Expressing a cryptographic process as a Boolean function with input bits. 
• Breaking the cryptographic system as a function of the key length.
• Exponential in key length as computationally hard and polynomial in key length is computationally easy.

His conjecture is quite striking.

For almost all sufficiently complex types of enciphering, especially where the instruction given by different portions of the key interact complexly with each other in the determination of their ultimate effects on the enciphering, the key computation length increases exponentially with the length of the key, or in other words, with the information content of the key.

The significance of this general conjecture, assuming its truth, is easy to see. It means that it is quite feasible to design ciphers that are effectively unbreakable. As ciphers become more sophisticated the game of cipher breaking by skilled teams, etc. should become a thing of the past.

The nature of this conjecture is such that I cannot prove it, even for a special type of cipher. Nor do I expect it to be proven. 

Nash's conjecture, even for a specific cipher, would imply P ≠ NP, 16 years before Cook defined the problem, and the significance resonates with the Diffie-Hellman article written 21 years later

Theoretical developments in information theory and computer science show promise of providing provable secure cryptosystems, changing this ancient art into a science.

Given Nash's insights, why did the NSA react so cautiously to these letters.

• This was not a letter from Nobel Laureate Nash but from Assistant Professor Nash.
• There is a strong positive correlation between people who claim they are not a crank and those that are.
• Nash's arguments didn't apply that well to the relatively slow digital computers of the time.
• Nash didn't give a particularly useful cryptosystem.
• I don't even believe Nash's conjecture: There are plenty of complex enciphering techniques, such as the Engima machine, which the NSA did know how to break. Hard to break cryptosystems come from more structured ciphers based on algebraic properties like AES and RSA.

Is 99.8% Secure Secure?

Guest post by Janos Simon

A group of researchers (Arjen Lenstra and collaborators  from EPFL Lausanne and James Hughes from Palo Alto) published a study, Ron was wrong Whit is right, of new vulnerabilities of cryptosystems. The New York Times picked up the story. Although Lenstra et al discuss several cryptosystems, their results are particularly relevant to those based on RSA. The title mirrors their conviction that cryptosystems based on a single random element have fewer key generation problems than RSA, that uses two random primes.

The technical problem they identify in RSA is the following: The RSA cryptosystem uses a modulus n that is the product of two large "random" primes p and q. Actual keys may not be truly random, and this may cause several possible problems:

1. Different users may end up with the same n. Since a user knows the factors p, q, she will be able to decrypt the data of any user with the same modulus.

2. If two users share one of the factors, (user A's modulus is pq, user B's is pr) they will be able to decrypt each other's data. Given two moduli, one can use the Euclidean algorithm to determine whether they have a common factor, and find it if it exists.

Note that the second vulnerability is more insidious: in the first only the user with the matching key can decrypt the messages of its mate, while anyone can  explore the web looking for pairs of keys with a common factor.

The lack of randomness in key generation may be caused by bad choices for the seed of a random number generator. As an extreme example, devices may be shipped with a standard common seed. In this case all devices would generate the same n. In general, if the collection of seeds is a low entropy set, with high probability insecure keys will be generated.

The EPFL group collected 11.7 million public keys "while avoiding activities that our  system administrators may have frowned upon" and essentially found that about 99.8% of the keys were not insecure (to the extent that they did not suffer from the vulnerabilities above.)

Is this secure enough?

Note that .2 percent of 11 million is tens of thousands of bad keys.

To make matters murkier, another group with researchers from the University of Michigan and UCSD did a somewhat similar experiment. Their results are not published yet, but one of the authors, Nadia Heninger blogs about their results in Freedom to Tinker. They find a similar proprtion of bad keys, but they claim that the vulnerability mostly occurs with embedded devices like firewalls and routers, so "important" keys like bank certificates are not affected. Lenstra et al disagree.

Perhaps we should be happy that these vulnerabilities are not due to weak Theory, but to bad implementations of good theoretical ideas....

The Envelope Please

The conference that shares its namesake with this blog has announced their accepted papers. The 27th Conference on Computational Complexity itself will be held in Porto, Portugal June 26-29. If you go, stop by England on the way and celebrate the 100th anniversary of Turing's birth (June 23) in either Cambridge or Manchester.

Lots of great papers accepted to the conference. For biased reasons I like Limits on Alternation-Trading Proofs for Time-Space Lower Bounds by Sam Buss and Ryan Williams. They give some compelling logical reasons why we've hit the limit of current techniques in proving time-space tradeoffs for Satisfiability. Alon, Shpilka and Umans found connections between Sunflowers and Matrix Mulitplication. Finally a plug for my student Josh Grochow's first Complexity paper Matrix Lie Algebra Isomorphism.

Presidents Day Poll- what does the youth of american think about....

(In honor of President's day which was two days ago.)

On Presidents Day last year I had my classes fill out a form saying who they thought was the best, second best, third best, and worst president. I gave them a list and asked them to just mark 1,2,3 (for best, second best, third best) , BAD (for worst) on it. I omitted Obama, Bush Jr, Clinton from the list since they are too recent. So, what does the youth of America think? Or at least the youth taking Honors Discrete Math or Automata theory?

Here is the list or presidents ranked by roughly how well they did. (Some are not included since they did not get any voters pos or neg.) I (somewhat arbitrarily) gave 3 points for each ONE, 2 points for each TWO, 1 point for each THREE and -3 points for each BAD. Are these the best weights to use? Is there a way of arguing which weights are best? This is a variant of a standard voting problem. The standard problem does not include the option of BAD for negative points. I don't think there is an optimal answer. Weights that would NOT be good to use would make the ONES's get a lot more than the TWO's since I suspect this gap was not so large in peoples minds. Or I could have had THEM give point values between (say) 1 to 100 for the ONE, TWO, THREE and between -1 and -100 for the BAD. Maybe I'll do that next year.

1. Abraham Lincoln: 15 ones, 10 twos, 10 threes: 75 points.
2. Theodore Roosevelt: 8 ones, 8 twos, 4 three: 44 points.
3. Franklin D. Roosevelt: 11 ones, 7 twos, 7 threes, one B: 51 points.
4. George Washington: 7 ones, 4 twos, 8 threes, one B: 34 points.
5. Thomas Jefferson: 6 ones, 5 twos, 5 threes: 33 points
6. Dwight Eisenhower: 1 one, 3 twos, 5 threes: 14 points.
7. John F Kennedy: 2 ones, 5 twos, 6 ones, 1 B: 14 points.
8. Woodrow Wilson: 1 one, 1 two, 3 threes: 10 points.
9. Harry S Truman: 2 twos. 6 points.
10. James Polk: 1 one, 1 two: 5 points.
11. John Adams: one 1, one 2, one B: 4 points.
12. William Henry Harrison: one 1: 3 points.
13. Lyndon B. Johnson: one 2, one 3, one B: 2 points.
14. Andrew Jackson: 2 ones, 1 two, 2 B's: 2 points.
15. Ulysses S. Grant: 1 two, 2 B's: -4 points.
16. Zachery Taylor, Rutherford B Hayes, Chester Arthur, Millard Fillmore, Warren Harding, Gerald Ford: 1 B: -3 points.
17. Jimmy Carter: 1 one, 1 two, 4 B's: -5 points. CORRECTION ADDED LATER: SHOULD BE -7. ARITHMETIC MISTAKE. MAKES HIM RANK BELOW BUCHANAN AND TAFT!
18. James Buchanan, William Taft: 2 B's: -6 points.
19. Ronald Reagan: 1 one, 3 twos, one 3, 8 B's: -12 points. CORRECTOIN ADDED LATER: SHOULD BE -14. ARITHMETIC MISTAKE. RELATIVE ORDER UNCHANGED.
20. Herbert Hoover: 5 B's: -15 points.
21. George Bush: 6 B's: -18 points.
22. Richard Nixon: 1 one, 1 two, 10 B's: -25 points.

My thoughts

1. I thought George Washington would do better.
2. I'm surprised that Theodore Roosevelt did so well. Bart Simpsons likes him, though Lisa Simpson prefers FDR (From the episode Bart stops and smells the Roosevelt's.
3. The person who ranked Hayes as the worst president of all time either knows much more about the Hayes administration then I do or was just putting things down at random.
4. The vote for William Henry Harrison was a joke- the guy who voted for WHH is named Henry and liked that his first name was WHH's middle name.
5. Dwight Eisenhower did better than I thought he would.
6. Richard Nixon did worse than I thought he would. I thought today's youth didn't know about Watergate. George McGovern (who Nixon beat in 1972 and is still alive) recently said that if he had won in 1972 then Nixon's legacy would be much better (going to China, Detente with Russia, EPA, Okay on Civil Rights.) Nixon would be considered a left wing democrat today.
7. George Bush did so bad that I think people may have confused him with his son W.
8. Some of my opinion: (1) I rank George Washington first since the very act of STEPPING DOWN after two terms set the tone for peaceful transitions of power. Note that young democracies today the most important election is the one where the person in power has to voluntarily step down. (2) For worst prez I wouldn't call someone BAD just because I happen to disagree with their policies. It has to be someone who (in contrast to Washington) did things that undermine our democracy. Two that come to mind are Nixon (Watergate) and John Adams. (Alien and Sedition Acts). George W Bush (Patriot Act) might also qualify but its too early to tell. Other wartime restrictions on freedom (happened in many wars) might also qualify. The corruption of the Grant and Harding's administration were deplorable but I don't think they rise to the level of undermining our democracy. There are probably other presidents who qualify for this honor but not being an expert on Presidents, I don't know who they are.
9. In the book Hail to the Chiefs (a humorous though mostly accurate look at the presidents) in the first edition she said that Buchanan and Andrew Johnson were not looked upon kindly by historians, which is true. In the second edition she made the points many times with many presidents (including those two) that how well you do is VERY MUCH a matter of timing, luck, and History. To paraphrase Buchanan couldn't stop the Civil War. By that point nobody could. Andrew Johnson had to reunite the country and deal with the South after the Civil War. That's pretty hard too. I agree that there are many thing outside a presidents control, and they some blame or praise may be unwarranted.

Aggie for a Day

About 25 years ago I visited a college friend, David Jackson, then a grad student at Texas A&M. He was a Ph.D. student in Food Science doing his doctorate research on starch. He had a tortilla maker in his lab. Made me wonder if I was in the right field. David is now making tortillas in Nebraska.

Last week I made my second trip to College Station this time to visit the CS department, give a talk and meet lots of great researchers.

Landlocked Texas A&M has one of the world's leading Nautical Archaeology programs. We went to visit and a grad student came out, said "Howdy", and gave us a tour of models of the ships they have been excavating.

Robin Murphy arranged a tour for me at Disaster City (that's us pictured above). Disaster City is one of the largest training grounds for emergency responders with collapsed buildings, rubble piles, derailed trains and other sites to train people, dogs and robots, the last of which is Robin's specialty. Some of Robin's students were testing out a flying video drone that day. Robin gets involved in disaster areas such as Fukishima. Saving lives with computer science. Makes me wonder if I got in the right field.

People solve math problems for the prize money! NOT!

Why do people or organizations offer Prize Money for mathematics?

1. Paul Erdos: He offered money to solve problems that he found interesting. I assume he wanted them solved but he also wanted to encourage a line of research beyond the problem. He had a (well deserved) reputation as a brilliant mathematician, so if he couldn't solve a problem it was hard. People would somtimes not cash the check and frame it. I've heard that with color copiers people now copy it, frame the copy, and cash the check. Did he insist that it appear in a journal or just need to be convinced? I don't know but I would think just need to be convinced.
2. Bill Gasarch: He offered $289 dollars for one problem, which, as you know, was recently solved by Steinbach and Posthoff (see here). While Gasarch has nowhere near the reputation of Erdos and his problem was not a deep math problem, this problem caught on as a matter of luck and timing. The blog helped, and Brian Hayes picking up on it helped. Gasarch wanted to get this problem solved, but did not quite know if it would inspire a line of research. It did (according to the solvers) present a problem just on the edge of what is possible to solve of this type. Gasarch used paypal. Hence, alas, Steinbach and Postoff won't be able to frame a check or its copy.
3. Scott Aaronson: His 100,000 offer (see here) for ...demonstration, convincing to me, that scalable quantum computing is impossible in the physical world This is different than most prize offers in seveal ways: (1) He gets to decide, not a ``refereed journal''. (SIDE NOTE-here is an idea: a prize that pays out only if the article appears in a non-elsevier journal.) (2) He does not expect to pay out (but he happily will if someone really convinces him). I believe him on this, though 100,000 is a lot of money. He wants to inspire people to think about these questions. The only thing analagous I can think of is prizes for REAL parapsychology- they don't expect to pay out but would be happy to since the world is more interesting if parapsychology is true.
4. Millienium prizes: I believe these one million dollar prizes are the most ever offered for solving particular math problems by an order of magnitude (if that is not correct, please leave a polite comment correcting me). Clearly the Clay Instuite wants to encourage research in these areas. Why so much money? I assume to REALLY put these problems on the map. There is no mathematician of the stature of Hilbert nowadays who could state problems of importance in a way people would listen. Smale tried (see here) but those problems never got the status of either Hilbert's problems or the Millenium problems.
5. Godel Prize: Best paper in theory published in the last 14 years (used to be 7). I wonder- if someone posted a solution to P vs NP on arXiv and it was correct, would they really not get the Godel prize? I suppose not. A bit awkward in that if your publish in a period of time when many good papers come out you could be out of luck. Why did they extend the window from 7 years to 14 years? Speculation: people are getting worse at getting papers out into journals so they had to extend it. Enablers? Given once a year.
6. Turing Award: I am not quite sure if this is for one paper, a body of work around one idea, or a career. It can go to people who never proved a theorem since its open to all computer scientists. The prize money has gone from $2000 to $250,000. Given once a year.
7. Fields Medal: Given for a body of work. About $15,000. High Prestige, low dollars. How come the Turing Award was able to increase its money value but the Fields medal was not? I honestly want to know. Given once every 4 years to a set (group? locus?) of people.
8. King Faisal prize: I blogged about this here so I'll be brief: High dollars ($400,000), but low prestige. I assume the origin was to try to give glory and prestige to Saudi Arabia who gives out the prize. I don't think it worked. Aside from its origins it also has the problem of being unfocused in that they have awards for Sciene (which is sometimes math) and also for Muslim scholarship, and other areas.
9. Here is a list of other prize. Some thoughts
   1. Some are for solving a particular problem, some are for a body of work in a particular area, some are for a body of work and the area can be anything within mathematics.
   2. Some are restricted to a subset of people, some are not. Thats a tautology!
   3. People do not solve problems for the money. Most of the prizes are too small for that and those that are large are for really hard problems.
   4. There are many of them, more than I thought. I still doubt I'll win one. The closest I ever came was being linked to on the Wikipedia page on the Godel Prize (see this Blog Entry about why that happened.)

Sloans and More

The Alfred P. Sloan Research Fellows were announced today including Northwestern's own Nicole Immorlica. Other winners in theoretical computer science include Xi Chen, Nate Foster and Prasad Raghavendra. A shout out to TTIC who have their second Sloan Fellow in Jinbo Xu.

Computer science did well in the president's budget for FY 2013. CISE head Farnam Jahanian gives the details. Of course now the budget has to get through congress.

Tomorrow there will be a celebration of twenty years of the NITRD (Networking and Information Technologies Research and Development), an interagency program that has heavily supported CS research over the past two decades. Quite an impressive list of speakers. There will be a live webcast of the event.

FOCS call for papers is out. Submission deadline is April 4.

Barney the Evil Dinosaur

This is an old story from before I had a blog, but one of my favorite on when technology goes bad.

In the late 90's, the undergraduate CS coordinator at the time, Don Crabb, also wrote a column on technology for the Chicago Sun-Times and would get tons of tech stuff to review. One of these items was a robotic Barney the Dinosaur that interacted with the Barney and Friends show on PBS. I took Barney home and tried him out with my then 3-year old daughter Annie.

He worked as advertised, singing along with the characters on TV. But at one point Annie said "Let's read a book Barney". Barney replied "Let's watch TV". Annie said "OK". Definitely sending the wrong message here.

Later Annie was playing with Barney in the kitchen. Annie, who was toilet training, said to Barney "I have to go wee-wee". Barney said "Let's play a game". Annie said "OK". Soon I had a mess to clean up.

That was the end of Barney.

STOC 2012 accepts are posted

STOC 2012 paper accepts are posted here. Travel support for grad students (which I am involved with) is posted here. On a quick glance:

1. I tried counting the paper for how many were in which categories. I got dizzy so I stopped. Also, for some its hard to tell the area just from the title. There DO appear to be many papers on complexity.
2. I hope that when the papers are finished there are pointers to all of them on the website.
3. There will be four workshops (see here) Under Tutorials it says TBA, so there may be some of them. What is the difference between a workshop and a Tutorial? I ask nonrhetorically.
4. When I goto an MAA or AMS conference there are (1) invited papers, (2) contributed papers, (3) Math Jeopardy game, (4) demos, (5) other things. When I goto STOC or FOCS or CCC or just about any theory conference its (1) submitted papers that got accepted. There MIGHT be a rump sessions (CCC, Crypto does this) a workshop or tutorial (STOC, FOCS does this- anyone else?) an invited talk (FCRC has these, Sometimes others do) a poster session (FCRC has had these. Have others?) My objection here is NOT that STOC has the submitted paper format and that STOC and FOCS are other conferences are too highly valued. (That is another debate which we've had before.) My objection is that all of the theory conferences only have VERY FEW kinds of activity- talks on papers that were accepted. I would like to see more VARIETY in activities.
5. The word Quantum only appeared in two titles. Are there other Quantum papers (I would guess yes).

The 17x17 problem SOLVED! (also 18x18)

THE 17x17 PROBLEM HAS BEEN SOLVED!!!!!

On Nov 30, 2009 I posted here the following challenge:

If someone emails me a 4-coloring of 17x17 with no monochromatic rectangles then I will give you $289.00

Bernd Steinbach (Institute of Computer Science, Freiberg University of Mining and Technology, Freiberg (Saxony), Germany) and Christian Posthoff (retired from Department of Computing and Information Technology, The University of the West Indies, Trinidad and Tobago, but now in Germany) have found a 4-coloring of 17x17 without monochromatic rectangles!! The coloring is here. I have verified it (actually I asked Daniel Apon and Jim Purtilo to separately verify it, and they have. Also, Semmy Purewal and Brian Hayes did later.) The methods Steinbach and Posthoff used to obtain the coloring will appear in their paper

Most Complex Four-Colored Rectangle-free Grids - Solution of an Open Multiple-Valued Problem (ISMVL 2012. ISMVL stands for International Symposia on Multiple-Valued Logic). They will present this paper on May 14, 2012 during session B1 of ISMVL in Victoria, Canada.)

Once the paper appears there will be a post (with their help, perhaps guest posted by them) on the techniques they used.

Some thoughts:

1. Some very serious people had worked very hard on this. I actually began thinking that 17x17 is NOT 4-colorable.
2. CONGRATULATIONS to Bernd Steinbach and Christian Posthoff!
3. They also found a 4-coloring of 18x18.
4. The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Sorry, no cash on this one. Do it for the glory!
5. If you are going to ISMVL 2012 then find Bernd and Christian and say hello. More important, talk to them about there work. (I won't be there alas.)
6. The reason I thought that 17x17 was 4-colorable is that there is a rectangle free subset of size 74, so I assumed that one of the colors would appear 74 times. WRONG- The max number of times a color appears is 73.
7. I thought that each color would appear 4 or 5 times in each row and column. WRONG- some appear 3 times in a row or column.
8. I am DELIGHTED to pay out the $289.00.
9. I asked them if they did it for the money (which I doubted). No, but the money made them more aware of the problem.
10. How did they do it? I do not know, but I am looking forward to reading their paper in May when it is available and blogging about it.

Competition

A few people have asked me my opinions on Oded Goldreich's essay On Struggle and Competition in Scientific Fields. I read through Oded's essay I expected to highly disagree with Oded, after all he attacks competition, which is just un-American, and he lays some blame on a small number of scientists "especially those holding administrative positions in the field" which as SIGACT chair puts me in that group.

But as I read the essay, I find myself agreeing with much of what he says. Our conferences have become too much more like competitions rather than focusing on distributing knowledge or bringing the community together. I also agree with many of his suggestions including having conference with more plenary talks, that program committees should create a "program" more than just choosing best papers and that hiring/promotion committees should focus more on the research itself rather than the decisions of program committees, awards committees and grant committees.

There is an faulty underlying assumption in Oded's essay that competition within theoretical computer science is a zero-sum game. Theoretical computer science competes within computer science for faculty slots and grant money. Computer science competes with other sciences and science competes with other needs.

SIGACT is not in the business of choosing winners and losers within the community but rather to promote the field to help increase the number of jobs and grants available to theoretical computer science. As I mentioned last week, awards are an important mechanism that lets us highlight the important research in theory.

Competition for grants, jobs, awards and just attention of other computer scientists helps make us all better allowing us to push for more resources for theory. It would be nice to say that we should just all do good self-motivated research, but the reality is we need those resources if we want theoretical computer science to continue to thrive.

Why do we have awards?

You have a month to get in your nominations for the Donald E. Knuth Prize and the SIGACT Distinguished Service Award.

Why do we have these awards and others like the Gödel Prize, The Turing Award, conference best paper awards, ACM Fellows, Nobel prizes and so much more. Are we just creating CV stuffers? Are we giving departments another measure to rank people? Are we trying to encourage good research through competitive awards? Does anyone have the conscious thought, "I wouldn't normally work on this problem but it could win me the Turing award so I'll do it"?

None of the above. We have awards for the publicity. We want to tell the world about the great researchers and work that they produce. A major award rises above the clutter and let's us say "Les Valiant must be a great computer scientist, he won the last Turing Award" or " Håstad's optimal approximation bounds are a great work in theoretical computer science as you can see from the Gödel Prize." Not a surprise that almost every award comes with a press release.

Are all awards fairly given? Of course not, prize committees are full of humans often comparing apples and oranges. But that's not the point. Awards let us celebrate what's great in computer science with ourselves and with the world.

Dusting off my bookshelf I find a book on FORTRAN

The following quote is from the back of a book that I dusted off and took off of my shelf recently:

FORTRAN is one of the oldest high-level languages and remains the premier language for writing code for science and engineering applications. (NOTE- The back of the book uses Fortran but the spell checker I am using insists on FORTRAN. As a fan of capitol letters, I don't mind going along.)

Was this book written in

1. The 1960's
2. the 1970's
3. the 1980's
4. the 1990's
5. the 2000's (meaning 2000-2009)
6. the 2010's (meaning 2010-2012)

Some questions and thoughts about FORTRAN:

1. How much is FORTRAN used? Perhaps more than you might think: Its in packages that have been running smoothly and quickly for a long time. It may not be worth it to swap it out for C or C++ or something else. However, it may be hard to modify.
2. How much new code in FORTRAN is being written? I suspect not much. UMCP does not have a course in it. Does your school?
3. Since people are not learning FORTRAN we will we become like one of those Science Fiction Aliens who says: Our ancestors left us these machines,but over time we only know how to operate them, not how to fix them or build new ones.

So, when was the book written?

The book is Modern Fortran by Clerman and Spector. The book came out in 2012 (I really need to dust my shelves). I doubt that FORTRAN is the premier languages for writing code in science and engineering. But how far off the mark is this? As always I ask non-rhetorically.

A result of Specker in Recursive Combinatorics

Ernst Specker passed away in December. He has 91. He was not the oldest living mathematician. That title likely belongs to Sergey Nikolsky. A former student of Specker's, Martin Furer, posted about his life and his math on this blog here.

In this post I discuss a results of Specker that is not his most famous (that seems to be the Kochen-Specker theorem) but instead a result that I actually know. Hope you like it.

Background: Ramsey's theorem states that if COL is a 2-coloring of pairs of naturals then there exists an infinite homogenous set H (so every pair from H has the same color). The standard proof is non constructive.

More background: What if you were GIVEN a Turing Machine for a 2-coloring. Could you GIVE ME BACK a Turing machine for a homogenous set? The standard proof does not give this to you, so we are really asking if there is a more constructive proof. So, what is known?

Specker showed that there is a computable 2-coloring of pairs of naturals so that there is NO computable Homogenous set. Here is the proof in brief:

1. Let A be a bi-immune set (no subset of A or its complement is decidable) that is decidable with oracle HALT. You can easily construct such by an initial segment argument.
2. By the Shoenfield limit lemma there exists computable f(x,s) such that A(x) = limit_{s→ ∞} f(x,s). (Easy proof of the direction we need: if A is computable in HALT via oracle Turing machine M let f(x,s) be the result of running M for s steps and using as oracle the first s elements of HALT in some enumeration.)
3. Let COL(x,y) = f(x,y), for x< y. (NOTE- This is a correction, I earlier just had COL(x,y)=f(x,y).)
4. Assume, by way of contradiction, that there is an infinite homogenous set
   
   x₁ < x₂ < x₃ < x₄ < x₅ ...
   
   For all L we have f(x_L,x_L+1)= f(x_L,x_L+2) = f(x_L,x_L+3) = f(x_L,x_L+4) = ... (NOTE- I corrected this- I originally had x_1, x_2, x_3, x_4 where I now have x_{L+1}, x_{L+2}, ..)
   
   Since all of these values equal they also equal limit_{→ ∞}f(x_L,s) and hence equals A(x_L). Hence either ALL of the x's are IN A or all of the x's are NOT in A. Hence an infinite homogenous set yields an infinite subset of either A or the complement of A, which contradicts that A is bi-immune.

More has been proven since then:

1. Jockusch showed that (a) there is a 2-coloring of pairs so that no homogenous set is Sigma₂, and (b) every 2-coloring has a Pi₂ set.
2. More is known- see the paper by Cholak, Jockusch, Slaman On the strength of Ramsey's theorem for pairs

Specker's result is probability the first theorem in infinite combinatorics to be proven to be non-constructive.

Guest post on ITCS by Chazelle

(Requested announcement: Calling all Women PhD Students (and a few undergrads) We will be having our bi-annual Women in Theory (WIT) Workshop this year in Princeton. The dates are June 23-27, 2012. Applications are due on: Feb 29, 2012. Go here for all the relevant information. Hoping to see you in June. From: Shubhangi Saraf, Lisa Zhang, Moses Charikar and Tal Rabin.)

(Guest Post by Bernard Chazelle) Why ITCS?

Thanks to Lance and Bill for their kind hospitality. I am delighted to be here. With the third edition of ITCS (formerly ICS) behind us, I thought it would be good to share a few personal, biased thoughts on the subject -- "personal" because I do not claim to speak for the Steering Committee; "biased" because I happen to chair that august body.

First, let me reach for my big bucket of gratitude. Shafi Goldwasser and Silvio Micali did an amazing job as PC & local chairs and I cannot thank them enough. A big shout-out to both. Toda Raba to Yael Kalai, too, for her great help, and to Omer Reingold, Nir Shavit, and their fellow actors for a fabulous "playback" show. If you missed it, fret not. If future organizing committees have any sense, the Nir-Omer show will soon come to a conference near you.

This year's ITCS had about 100 submissions, roughly a 20% growth from previous years, and 118 registrants. Talk attendance never seemed to dip below 90, a heart-warming figure that would be the envy of many conferences. In Shafi's and Silvio's deft hands, innovation came out swinging in all sorts of endearingly creative ways, from session chairs giving annotated previews of the talks to postdocs and graduating students making 5-min pitches to introduce themselves and their research. Brilliant! After watching the new generation of theorists in action, I can tell you that the future of theoretical computer science looks very bright, indeed!



And the future of ITCS, you'll ask, how bright is that? When I chaired the PC last year, a reviewer's comment struck a chord: "This submission would be good for STOC but might not be innovative enough for ICS." Now, that's the spirit! Of course, plenty of ITCS papers would fit in nicely at STOCS/FOCS. (Apparently, more than a few tried to fit in.) That said, it would take an advanced case of color blindness to miss the contrasting hues between ITCS and the rest. All PC members were instructed to add an innovation axis to their evaluation space, and, by golly, they did! (And when I use the word "golly," you know I mean business.)

STOC/FOCS has been accused of all sorts of dastardly deeds unmentionable on a family blog -- from accepting too few papers to boosting trends to rewarding technical wizardry. No less. STOC and FOCS might be four-letter words to some, but to me they're venerable legacy institutions that serve worthy professional functions, such as allowing junior researchers to trade these four-letter words for Theory Club membership cards. Nothing to sneer at. Over at Michael Mitzenmacher's corner, here, Umesh Vazirani bravely suggested merging STOC and FOCS into one mega-conference --- SFOCS, I guess. Much as I love the idea, beginning with the soothing effect of pronouncing the word SFOCS out loud, I didn't come here for a food fight, so I'll fall back on old New Jersey wisdom and say we cross that landfill when we come to it. Yet definitely something to mull over.

ITCS provides a venue for quality outside-the-box thinking. Not without reason, a few have wondered whether the best place outside the box is inside a new conference. On the plus side, conferences provide ideal platforms to publicize new work and, for younger scholars, increase the visibility of their research. With its particular focus on the uncharted, ITCS offers a welcome new outlet for a glut of quality papers. A conference is a big heads-up, a "breaking news" banner flashing on the Theory Channel. It's also a chance to initiate lasting collaborations and meet extraordinary people in pursuit of extraordinary ideas. It's fun.The downside is that a human being can attend only so many conferences before "their budget glares red and their head bursts in air" (as they say before kick-off at the Super Bowl).

This dichotomy, however, isn't quite right. It ignores the tangled web the online revolution has woven into our lives. Whereas in the past I'd have to go to a conference to hear a new result, this is no longer so. The PDF will come to me. It's a given that attendees at many talks will already know the results, perhaps even the proofs. This has diminished the relative importance of attending a conference while at the same time increasing its reach, and hence its influence. Don't get me wrong. I am not saying ITCS is so cool you don't even have to go. I am saying that, in the age of instant downloads, missing this month's Jay-Z & Kanye West "UGC" gig at the Garden ain't gonna be the heartbreak it would have been in the days of old. So, while I recognize that the burden of extra travel is a drawback and the timing always an issue, our wired world alleviates these concerns somewhat. And if you find this argument too subtle for its own good, well, remember, there's always the Umesh option.

Another worry heard on Theory Street is fragmentation. I don't get that. The sociological makeup of all these conferences is pretty much the same, anyway, so the risk of fragmentation is about as high as that of Dr. Jekyll and Mr. Hyde parting ways -- OK, make that Superman and Clark Kent if you prefer. In fact, this has it exactly backwards. Theory has yet to penetrate many geographical markets. Eurotheory shares a name with our kind, and little else. With Asia a promising growth area for our field, it is of more than symbolic value that ITCS was born in China. All theory conferences today are regional (North America, Latin America, Europe, Asia, etc). Maybe ITCS can be the exception. At any rate, to expand both the intellectual footprint and the geographical reach of Theory is a central goal of this conference.

To close on a personal note, let me get my crystal ball out of its dusty case and tell you what I see. As the new sciences of the 21st century further embrace their algorithmic nature, I see ITCS getting enriched with a growing flow of conceptual imports from physics, biology, economics, etc (and vice-versa). While the letter T was added to ICS for mundane reasons -- an ACM conference had a previous claim on the acronym -- I hope ITCS remains unabashedly theoretical. Yes, you heard right. And as you watch me adroitly duck the tomatoes sure to be hurled my way for this impolitic stand, you might even spot a contradiction or two. I mean, how can computing theory reach out to the sciences without losing its theoretical core? Well, well... Leaving aside the fact that math developed with precisely that sort of outreach, the answer is easy. What the "new" sciences (bio, neuro, socio, and all that) lack more than anything is a conceptual framework. Theoretical computer science can do for them what mathematics did for physics. Why? Because algorithms are the differential equations of the 21st c. They are the language of modern science. That's why. At this point, you expect me to clear my throat and indulge in a tasteful round of name dropping: "Moreover, as Newton and Einstein used to say, blah blah..." (I got that from my physicist friends. Works every time.)



But not today. Truth is, delusion won't help our cause one bit. Neither will diffidence or skittishness, however. These are heady times for computing theory, my friends. Hand wringing over fine tactical points should not distract us from our common goal, which is to allow Theory to expand and flourish, to unite and conquer. ITCS aims to do just that. It is an exciting experiment worthy of your support.

Thanks for your attention and, in a nod to ITCS' roots, a happy Year of the Dragon to all!

Bernard Chazelle

Ernst Specker (1920-2011)

Martin Fürer remembers his former advisor. 

While traveling, I received the unexpected sad news that Ernst Specker passed away on December 10, 2011. He was born in Zürich in 1920. After receiving his doctoral degree at ETH Zürich in 1949, he spent a year at the Institute for Advanced Study in Princeton. Then he returned to ETH in 1950 and stayed there with the exception of two visiting appointments at Cornell University.

Ernst Specker was teaching Linear Algebra when I started my studies at ETH Zürich in 1967. His teaching style was different from the typical polished and streamlined presentations of that time. He was looking for interaction, and did not hesitate to interrupt a proof to insert an example when he sensed that the audience was not following.

Outside the classroom, it was a turbulent time. The youth movement started to question many long established rules of society. For a long time, it seems that the majority of people, without ever thinking about it, had accepted the claim that the US with its war in Vietnam was defending western values. Quite suddenly, this consensus was widely questioned.

ETH had its own little problem. A new law governing the ETH (the only federal university in Switzerland) had just been adopted by the parliament. Many students took issue with the idea that the main goal of ETH was not to satisfy a general human right for education, but to prepare the students to serve the interests of business and industries.

Ernst Specker, who always liked discussions, never accepted anything based on authority without asking some critical questions, had quickly established a relationship with the young students at this time of evolving political turmoil.

Here are two examples, typical for Ernst. The mathematics and physics students of each semester had an open discussion about the ETH law. One professors came to our group to tell us, we should not complain, its our fault, we should have had this discussion a year ago, when it was the proper time to voice any opposition. He was not happy, when Ernst disagreed, noticing that this group of students has only been here for half a year.

A more important move was Ernst Specker's engagement for the Manifesto of Zürich, a public declaration against police brutality after some excesses when the "establishment" was shocked and fearful of the demonstrations in downtown Zürich.

During our studies, we all had to give talks in four seminars in different areas of mathematics. This rule was widely followed with one exception. A large group of students participated in the logic seminar, and they came back ever since (naturally in addition to the other seminars). Every semester, there was a different theme. My first subject was the solution of Hilbert's tenth problem, presented with all background information and details. The seminar was conducted with Hans Läuchli. Paul Bernays, who had started the seminar when he came from Göttingen before the second world war, was still a regular participant. He often followed the talks reading the blackboard with a two minute delay.

Ernst conducted the seminar still long after his retirement, because unfortunately ETH no longer had a position for mathematical logic. I participated in Ernst’s last logic seminar during my sabbatical in 2002. We ended the semester with a talk of Ernst that was intended for a general mathematical audience. I reserved the beautiful and rather spacious Aula of the ETH for this purpose. Luckily, we could still switch to the Auditorium Maximum, in the last minute, when we saw the people  arriving.

Scientifically, Ernst Specker has worked in many areas as illustrated in by the Selecta volume published by Birkhäuser on the occasion of his 70th birthday.  In his dissertation with Heinz Hopf, Ernst worked on cohomology groups. Then he moved on to investigate constructively in analysis, and the foundation of set theory, in particular Quine's new foundations. He also solved one of the early Erdős problems. Ernst’s most famous results are the works with Simon Kochen on the foundations of quantum mechanics, proving that certain hidden variable theories are not possible, and thus colliding with the assumptions made in the famous Einstein-Podolsky-Rosen paper. The results of Kochen and Specker are still discussed today in the physics literature. Early on and in his additional weekly seminar with Volker Strassen starting in the early seventies, he reached out to complexity theory.

Ernst Specker will always be remembered for his teaching and his scientific work, but most of all for his friendship, his openness and his engaging discussions.

Martin Fürer
Pennsylvania State University

What should we do?

Time for a post by tweet request.

Is a wave of action against big publishers' practices brewing?gowers.wordpress.com/2012/01/21/els…thecostofknowledge.com Should CS do more? @fortnow
— Tugkan Batu (@tugkanbatu) January 22, 2012

Quite a lot on the Internets on Tim Gowers' promise not to work with Elsevier anymore. I'm not as anti-Elsevier as Gowers or many of my readers but I understand the frustrations.

It's easy to make a promise not to publish, edit or referee papers, especially when you don't need to improve your academic reputation. Still a mathematician of his magnitude really puts a spotlight on that publisher.

Because of the Elsevier stigma we've had for several years, all the theoretical CS journals of Elsevier are not nearly as strong as they have been in the past. So you don't accomplish much more just by boycotting Elsevier.

Making a difference means what you do, not what you don't do. Be sure and support journals that are worthy of support by submitting and refereeing papers and serving on editorial boards. The best attack on publishers that you don't like is to have several strong alternatives. The best way to make them strong is by having your support.

No journals is completely free of cost, they require money or time. Open access journals without page charges generally have no revenue stream and require effort to make to publish the journal. For these journals you can volunteer your time as well as submitting, refereeing and editing.

Remember it's easy to complain and say what you won't do but it is what you do do that makes the difference.

Teaching an Honors Section of Discrete Mathematics

A few years ago I was assigned to teach the HONORS section of Discrete Math (a course for sophomores who have had a year of programming and a year a calculus). They told me it was up to me to figure out what to do to make it an honors course. (My section had 30 students, the non-Honors has about 60.) There were several options:

1. This could be taught separate from the non-honors course. Diff homework, diff exams.
   PRO: the homework and exams can be more interesting since you do not have to worry about how they are for the non-honors student.
   1. CON: If a student would have gotten (say) an A in the non-honors course, but gets a B in the honors section, that is not good. OR the teacher could grade inflate so that the students who got a B in the reg section gets an A in the honors section.
2. You could give the same exams and homework to the honors students but REQUIRE them to do more work- extra problems on the homework, extra problems on the Exams.
   1. PRO: They will get to do more fun problems.
   2. CON: They are being penalized for taking an honors course.
3. Same Exams and homework as the regular class. The regular class meets Tu-Th for 75 minutes. The Honors class meets MWF for 50 minutes each. What the Regular class does on Tu-Th, the honors class does on MW. On FRIDAY the honors class has an HONORS DAY- they work in groups of 3 or 4 on problems of more interest than usual. (example: For Logic devise a way to do do AND, OR, and NOT if the variables take on values BETWEEN 0 and 1 (including 0 and 1)). There is a LIGHT homework on this work just to keep them honest. But its not graded seriously.
   1. PRO: They get to learn more stuff in a fun way.
   2. CON: More work for the professor to make up these kinds of problems. (To brag- this is the sort of thing I am good at so not a problem for me.)

I did the last one and I think it worked, for some definition of worked. That is, the students liked it and found it interesting, but its hard to compare it to other ways of doing it. (Doing real studies that tell you things in the field of Education is hard.)

How have you, or would you, run an honors course in discrete math? How about for a programming course?

How important are the Fib numbers in math? in Nature? In History of Math books?

The following quotes is from In the book Algebra in Ancient and Modern Times by V.S. Varadarajan.

Fibonacci numbers thus grow very fast with N, indeed in geometric progression. This is often called exponential growth. They remained as curiosities till in the 1960's they were found to be crucial in certain studies in mathematical logic.

I suspected they were refering to its use in Hilbert's tenth problem even though that was really 1970 (a quibble) and I would hardly call it crucial (a more substantial objection). In fact Fib Numbers are not even needed in the end. I asked Chris Lastowksi who is a Model Theorist at UMCP and he told me the folowing:

Yes. Matijasec showed that the Fibonacci sequence was diophantine, and this sufficed to solve Hilbert's tenth problem (actually to show it could not be solved), by earlier work of Davis, J. Robinson and Putnam. However, Davis almost immediately showed that the exponential function is diophantine, which yields the solution to H-10 more easily, so I would hardly call that a deep connection.

V.S. Varadarajan wanted to make the Fib numbers interesting and important. The attempt was not quite right.

1. How bad is it for a history-of-math book to exaggerate how important some concept is?
2. How important are the Fib Numbers? Do they come up in Mathematics?
3. Could V.S. Varadarajan have picked a better example of their use in mathematics?
4. It has been said that the Fib Numbers come up in Nature. According to Fib Flim Flam most of the statements made about Fib numbers and nature are suspect.

The Information Flood

Twitter, Facebook, Google+. Information now comes to us as a faucet. If you don't drink it all it disappears forever. Try to find status updates and tweets from even a few days ago. Many of you wouldn't have seen this blog post if you didn't catch it on Twitter or Google+.

I try to keep my faucet turned relatively low. I still like RSS feeds like Google Reader. Stuff stays until you discard it. I try not to have too many Twitter followers or Facebook friends.

But the trend is for people, especially the younger generations, to subscribe to whatever fills their fancy. They get a continual stream of information and ignore what they don't see. So Google and Facebook develop algorithms based heavily on what the crowds and your friends are looking at, to determine the order of what you see. Twitter will surely have to follow. Google even tries to decide which of my emails are important.

As goes the Internet goes so does academic knowledge. How do we cut through the research clutter? Will we have algorithms and the crowds tell us which research papers to look at? That used to be the job of journal editors, conference program committees and my grad students.

Being Random and Trivial in Dagstuhl

This week I'm at the Computability, Complexity and Randomness workshop at Dagstuhl in Germany. This meeting brings together two groups, complexity theorists and computability theorists, who share a common love of Kolmogorov complexity.

From the logicians I learned about K-trivial sets. Let K(x) be the prefix-free Kolmogorov complexity of x, i.e., the size of the smallest program that generates x. There are several equivalent definitions of K-trivial sets, here is two of them. A are K-trivial if

1. For some constant c, for all x, K(x) ≤ K^A(x)+c, where K^A(x) is the smallest program generating x with access to oracle A.
2. For some constant c, for all n, K(A_1:n) ≤ K(n)+c, where A_1:n are the first n bits of the characteristic sequence of A.

Lots of interesting properties about K-trivial sets.

• All computable sets are K-trivial and there are K-trivial sets that are not computable.
• There are only a countable number of K-trivial sets. In fact there are only a finite number of K-trivial sets for each fixed constant c above. 
• Every K-trivial set is super-low, that is the halting problem relative to a K-trivial set is non-adaptively reducible to the halting problem.
• Every K-trivial non-adaptively reduces to a computably-enumerable set.
• Every set reducible to a K-trivial is K-trivial.
• The disjoint union of two K-trivial sets is K-trivial.
• Random sets are still random relative to A.

More about K-trivial sets and everything else computably random in a great book by Downey and Hirschfeldt. 

Us complexity theorists started thinking about polynomial-time versions of K-trivial sets but probably won't have as many nice properties. 

The Conjunction Paradox

In Yesterday's post you were told about Susan:

Susan is 31 years old, single, outspoken and very bright. She majored in philosophy. As a student she was deeply concerned with issues of discrimination and social justice and also participated in anti-nuke demonstrations.

You were asked to rank the probabilities of certain things about Susan. Two of the choices were

a bank teller

a bank teller and an active feminist

LOGICALLY bank teller and feminist would have a HIGHER probability than bank teller and and active feminist. Some people (including me when I first was given this exercise) ranked bank teller lower bank teller and active feminist. Why? I think that either people are not good at logic in real-world situations or people implicitly view bank teller as bank teller and NOT an active feminist. This problem has been extensively studied and there are other opinions.

Of the 30 responses I got before posting this roughly 10 ranked bank teller higher than bank teller and and active feminist (which is correct), 10 ranked bank teller and and active feminist higher than bank teller, and 10 of the answers were not relevant (e.g., clarifications of the question). (One person I blocked since he explained the above and would have given away the game, and one person who left a comment 5 minutes ago I will let through but only after I post this.)

I recommend giving this exercise to students in a class that covers logic and/or probability to see what they say.

Clyde Kruskal told me about this problem. He found it here though its also at other sites. This source credits the following (which I would guess is correct). Tversky, Amos; & Kahneman, Daniel (1983), Extensional Versus Intuitive Reasoning: The Conjunction Fallacy in Probability Judgment", Psychological Review 90(4) (October): 293-315. They are famous for these sorts of psychology questions. The latter won the Nobel prize in economics for joint work with the former.

The notion that A is less likely than A AND B is called The Conjunction Fallacy. The article pointed to only gives the two choices: (1) Bank Teller, and (2) Bank Teller and an active feminist. I think its better to give all of those choices as is done here other presentations of this exercise.

Rank these possibilities by probability

Readers- I want you to answer this question and post your answers as comments. I will tell you WHY I am asking tommorow.

Susan is 28 years old, single, outspoken, and very bright. She majored in philosophy. As a student she was deeply concerned with issues of discrimination and social justice and also participated in anti-nuke demonstrations.

Please rank the following possibilities by their probability. List them LOW to HIGH. (Just post your answers. Other comments I may block so that others can enjoy the question.)

1. a kindergarden teacher
2. works in a bookstore and takes yoga classes
3. an active feminist
4. a psychiatric social worker
5. a member of the Sierra club
6. a bank teller
7. an insurance salesperson
8. a bank teller and an active feminist

Starting the Year with Turing

This week I was in Boston for the Joint Math Meeting, a combined meeting of the AMS, MAA and a couple of other three-letter math societies with 7000 of my closest math buddies. This is the main American meeting of mathematicians one part of which are interviews for math jobs which seem few and far between.

The conference didn't seem large to me because I spent most of the meeting at the AMS-ASL Special Session on the Life and Legacy of Alan Turing. I got to see some exciting speakers I haven't seen before including Martin Davis, Andrew Hodges (who authored the famous Turing biography soon to be re-issued) and my great-grand advisor Marvin Minsky. Minsky talked mostly about the sorry state of AI over the past few decades including how the Watson people were working on the wrong problem. I found myself in the strange position of defending AI before my talk the next day.

Craig Bauer, a math historian, talked about the early days of voice encryption during Work War II, basically digitizing and then applying a one-time pad. Turing developed a mechanism that used a hardware PRG improving the quality of the audio and reducing the space needed from a large room to small box, though it was never deployed in the field.

Ted Slaman send me this link with Turing suggesting that PRG can help in searching. I guess Turing did care about running time after all but we still haven't found his lost letter on P v NP.

Interesting fact: Gödel and Turing both admired each other's work but there is no evidence that they ever met or had any direct communication of any kind.

A fun workshop but I'm all Turing'd out and it is only the first week of the Alan Turing Year though I am still looking forward to June to attending the ACM Turing Celebration in San Francisco and CiE in Cambridge.

Next week I'm off to Dagstuhl for Computability, Complexity and Randomness. The fun also continues in the Boston area with ITCS.

Is there a NICE gadget for showing PLANAR HC is NPC?

(I have already posted this question on CS Theory Stack Exchange.)

If you know that 3-COL is NPC then you can prove that PLANAR 3-COL is NPC by a NICE gadget that removes crossings (see here for some lecture notes on it. They are not mine. The original link is here but I can't figure out the real author, though it is likely whoever taught Algorithms at CMU in Spring of 2004.)

Lets say we know that HAM CYCLE is NPC (we do!). Is there a gadget to remove crossings so you can show that PLANAR HAM CYCLE is NPC? The problem of PLANAR HAM CYCLE is NPC so there sort-of has to be a gadget; but is there a NICE one? (The proof that PLANAR HAM Cycle is NPC is from SAT and I find it rather complicated (see here for the original paper.) I have tried to extract an uncrossing gadget from it but have not been able to it.

SO- I ask you, do you know of a NICE gadget for removing crossings in a graph so that we can easily go from HAM CYCLE NPC to PLANAR HAM CYCLE NPC.

I'll be happy with HAM PATH or HAM CYCLE or DIRECTED HAM PATH or DIRECTED HAM CYCLE.