3000 lunches

Last week fortune smiled on two of my friends:

1. Ken Regan made the cover of Chess Life for his work on catching chess cheaters. (See here.)
2. Jacob Lurie who I mentored when he was a high school student 1993-1995 won $3,000,000 for doing pure math. I am not kidding. See here and here. and here.  This is a relatively new award called the breakthrough prize.

The breakthrough prize started a few years ago in Life Sciences and Fundamental Physics (not sure what they mean-possibly Mathematical Physics or Theoretical Physics). This is the first year it is given for Mathematics. The other winners of the Breathrough prize in math are  Simon Donaldson, Maxim Kontsevich, Terence Tao, and Richard Taylor.

$3,000,000 is the largest amount of money for prizes of this sort (the Nobel is a paltry  $1,200,000).  Even so, I had not heard of the award until there was a math one. I wonder if it will become a household name like the Nobel has.

A few weeks ago I told my student Tucker, who is going to Digipen- a 4-year college with a BIG emphasis on programming computer games- that he is more likely to become a millionaire then my student Sam who is going to CMU to study pure math. I could be wrong.

 I taught Jacob lots of recursion theory and he won the Westinghouse Award with a paper on Recursive Surreal Numbers; however, the work was all his own and didn't use much of what I taught him.  After that I made a policy that for every $1000 a high school student of mine wins I get a free lunch.  I emailed Jacob- and while he's not sure he'll give me 3000 lunches, he will treat me to lunch next time I am in Boston.

To quote the article, he won it for

Foundations of higher category theory and derived algebraic geometry for the classification of fully extended topological quantum field theories; and for providing a moduli-theoretic interpretation of elliptic co-homology.

I know what some of those words mean.

Computer Dating

My brother went through his old stuff cleaning out his apartment in New York and stumbled upon the 1981 computer dating questionnaire I wrote in high school. Forgive the dated and adolescent nature of the questions.

The computer science teacher showed us an example of a computer dating form created by some company, a new idea at the time. I decided to run computer dating at the high school, created a questionnaire and passed it around. I did this a few years, the 1981 form must have been the last as that's the year I graduated. In those ancient history days, my fellow students filled out these forms on paper and then I would type the answers into the big teletype machines in the computer lab. I wrote a program to create a matching, I have no idea what algorithm I used but I'm sure it was quite simplistic. I always got matched to the same person, but the pickup line "my computer dating program matched us up" didn't go very far. I did hear of one couple having one (and only one) date because of the program. There's a reason I became a theorist.

My daughters tell me the whole scene has changed with traditional dating quite rare these days. "First you become boyfriend/girlfriend and then you date" which seems so backwards to me.

Now we have websites that use sophisticated machine learning algorithms to connect people. I met my wife the old fashioned way--at a wine and cheese party sponsored by a Boston-area Jewish singles group.

How many ways can you make change of n cents?

(For a related post see  my post on Schur's theorem. The paper THIS post refers to is  here.)

(ADDED LATER: A commenter pointed to Graham-Knuth-Patashnik for a closed form for pennies, nickels, dimes, quarters, half-dollars. I have wriitten up their account and it is available here. I also apply their technique to just get 1,5,10,25.)

How many ways are there to make change of a dollar using pennies, nickels, dimes, and quarters? This is a well known question; however, the answers I found were disappointing. They were of two types

1. There are 242 ways to make change. The author then point to a program he wrote or to the actual list of ways to do it.
2. The number of ways to make n cents change is the coeff of x^n in the power series for 1/(1-x)(1-x^5)(1-x^{10})(1-x^{25}). This can be worked out.  I have never seen it worked out.

The first answer yields an actual number but is not interesting mathematically. The second answer is interesting mathematically but does not easily yield an actual number.

I looked for a closed form on the web but could not find one. So I did it myself. The paper  is pointed to above. I did not use generating functions, just recurrences. I do not know if it is new. Whether it is old or new I hope you enjoy it. The paper actually gives a closed form for the coin sets {1,x,kx} and {1,x,kx,rx}. Along the way we derive the answer for a dollar and the usual currency by hand.

This raises some questions:

1. Is my formula new? I'd be surprised either way. (Is it possible to be surprised at both statement A and statement NOT(A)?).  If  it's new I'll be surprised since the questions has been around for so long and surely someone would have done it. If it's known I'll be surprised since (a) I went to JSTOR and searched for all math journals they had for the words ``change'' and ``coin'', looked at the over 400 such articles (just the titles and abstracts) and didn't find it,  (b) this came up in math.stackexchange here and, true to form, every answer was either a program or a generating function and (c) other searches also did not turn up the result.(ADDED LATER- Since the 1,5,10,25,50 case was known, I guess I AM surprised.)
2. Even if its not new it is clearly not well known. Why is that?  Its a natural problem that people seemed to be interested in. One conjecture: The COMP SCI people interested in it were happy to write a program. The MATH people interested in it were happy to say `its merely the nth coeff of...' So a closed form solution seems to not be of interest to either camp
3. Is it interesting?  (a) Comp Sci: the closed form solution gives an answer in O(1) steps instead of the usual dynamic programming O(n) solution, and (b) Math: the closed form solution tells you the coefficients of the power series of 1/((1-x)(a-x^5)(1-x^{10})(1-x^{25}).

Side Bar: I asked the 10  students in my REU program to just GUESS how many ways there are to make change of a dollar with pennies, nickels, dimes, and quarters. Most made  guesses under 100. The lowest guess was 30. One person guessed 100! and one guessed 100!/2.  I then told them that it was between 30 and 100! and assigned them to derive it themselves by hand. Most were able to.

Favorite Theorem: PCP Simplified

The famous Probabilistically Checkable Proof Theorem due to Arora, Lund, Motwani, Sudan and Szegedy states that every problem in NP has a proof that can be checked efficiently by a verifier using O(log n) random coins and a constant number of queries. Not only amazing in its own right, the PCP theorem has significant implications for hardness of approximation. In its strongest form, no efficient algorithm can maximize the number of satisfying clauses in a formula better than a 7/8 approximation unless P = NP. Both of these results have been on my previous favorite theorems lists so lets add one more.

The PCP Theorem by Gap Amplification by Irit Dinur (PDF)

Dinur's main result doesn't prove a new theorem per se but gives a much simplified and intuitively understandable proof than the original paper. She increases the approximation gap by using an expansion graph though this causes an increase in the alphabet size which she reduces using another transformation. Repeating these steps yields the theorem. Unless you need tight bounds, Dinur's proof is the one to teach or read. 

Dinur's paper followed shortly after Omer Reingold's theorem on undirected connectivity, and while these are very different proofs of different results, together they show the amazing power of expander graphs in computational complexity. 

Ref/info request for an obvious appraoch to GI

Talking about Graphi Isom with some students they came up with the following idea which is certainly not new; however, I couldn't quite find much about it on the web.

ALG(G,H): Let G(0,1) and H(0,1) be the usual adacency matrix using 0 for EDGE NOT THERE and 1 or EDGE IS THERE. Choose n random pairs of numbers (a1,b1), (a2,b2),...,(an,bn) all \le n^2 (happy to change the bound if it will make it work better). For all i see if DET(G(ai,bi))=DET(H(ai,bi)). If there is an i such that they are NOT equal than output NOT ISOM (with complete certainly). If they are ALWAYS equal then output GEE, THOSE GRAPHS ARE PROB ISOMORPHIC.

1. I person who used to work on GI told me that he THINKS there are graphs G, H where the polynomials G(x,y) and H(x,y) are identical yet G and H are not isom. So their are some G,H where the above will definitely fail. Not surprising.
2. Are such graphs rare? Will this work on `almost all pairs of graphs' ? Not clear what that means.
3. If we also checked degree sequences and degrees-of-degrees, would that help? I doubt it since I think that graphs for which this fails are very similar in other ways, but I don't know that.

When I first heard the idea from my students it was new to me. Even so, I knew that it wasn't new and that it there has to be graphs it failes on (item 1 above). How did I know this? If there were no graphs that it failed on then GI would be in R. And if GI was in R, I would know that. And so would you. But this is not a good argument to give to students.

 I think its a good idea and it might work for our purposes (which may be a topic of a later blog).

CCC 2014

I'm returning from the 2014 IEEE Conference on Computational Complexity in Vancouver, unfortunately missing the last day. Several very nice talks including a wonderful survey by Shubhangi Saraf on recent problems on lower bounds in algebraic circuits (addition and multiplication gates). In short, the interesting case is depth-4 algebraic circuits with bottom fan-in √n computing homogeneous polynomials. Kayal, Saha and Saptharishi showed a 2^{Ω(√n log n)} lower bound. Any improvement (changing the Ω to a ω) would separate VNP from VP (the algebraic version of the P v NP problem), or equivalently show the permanent cannot be computed by poly-size algebraic circuits.

At the business meeting, we discussed the plans for independence from IEEE. 60% of 189 voted for independence with open access as the main reason stated. There has been great support from the community both in volunteers to help with an independent conference and money ($42K) raised to get started. Future proceedings will likely be in the Dagstuhl LIPIcs series. Timing and a new conference name are a few of the many issues still to be worked out. Whether or not you support independence, the conference organizers, particularly steering committee chair (and my former student) Dieter van Melkebeek, are doing a strong job coordinating the efforts.

Other highlights from the business meeting.

• 29 accepted papers out of 94 submissions. A good number.
• There was no best paper. The best student paper went to Alexander Belov for Quantum Algorithms for Learning Symmetric Juntas.
• 66 registered participants including 29 students. A bit low probably due to the proximity to STOC in time but not distance.
• 2015 CCC will be June 17-19 as part of the FCRC conference in Portland, Oregon.
• There were three good bids for the 2016 CCC from Tokyo, Saarbrücken and Riga. Tokyo was the overwhelming winner.
• CCC 2017 may be part of a federated theory conference including STOC, EC and SPAA.

Wassily Hoeffding 1914-1991

In honor of the 100th anniversary of the birth of Wassily Hoeffding today, let's recall his incredibly useful inequality.

Prob(|X-pn|>εn) < 2e^-2ε2n
where X is the random variable representing the number of heads from n independent coin flips each with a probability p of being heads. Informally the sum of many independent events will, with extremely high probability, be very close to the expected value. Notice that as long as ε = 1/o(√n) the probability goes down exponentially in n and this is tight as one expects X to be about O(√n) away from pn for constant p.
Back in the 80's, probabilistic computation started to play a major role in algorithms, cryptography, learning theory and interactive proofs. To analyze these computations one needed to deal with Chernoff bounds and it was difficult to find clean and easy statements of the bounds one could use in proofs. One of my officemates in grad school, Bob Sloan, took it upon himself to write up a short document giving Hoeffding's inequality and a few generalizations. Having that write-up was like holding Excalibur in my hands, ready to do battle with probabilistic complexity.
Later Alon and Spencer gave a nice treatment in their Probabilistic Methods text and these days you can get all the formulas you want on Wikipedia.

Fair question? Trick question?

The following problem was on my final for Formal Lang theory (Reg, P, NP, Dec, c.e.)

For this problem you may assume P\ne NP and NP\ne coNP. For each of the following
sets say if it is (1) REG, (2) In P but NOT REG, (3) in NP by not P, (4) Decidable but not in NP,
(5) c.e. but not decidable, or (6) Not c.e.

No explanation needed; however, you get +4 if its right and -2 if you give an answer and its wrong.
You get 0 for a blank. (Hint- DO NOT GUESS!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!)

1.  { G : G is 2-colorable}
2.  { G : G has an ind set of size 12}
3.  { a^nb^ma^{n+m} : n,m\in N }
4.  { (G,rho) : rho IS a proper 3-coloring of G}
5.  { a^{n^2} : n is not a square }

Some thoughts on this:

1. A reader once inquired of Marilyn Vos Savant my teacher said we would be penalized for guessing. How will our teacher know that we guessed?
2.  The above is funny but its a real issue- I really want to give -2 if they GUESSED but give 0 if they honestly thought (say) that a problem was REG when it was P but not REG. Alas we cannot put electrodes into their brains to tell.
3. It was a good question in that how well they did on it did correlate pretty well to how they did on the rest of the course and on the rest of the exam.
4. Problem 4 most people got wrong-- they thought it was NP but not P. One of the best students in the class who got it wrong said that just SEEING the phrase ``3-col'' and not having had a choice that was NP but not P made him just leap to the NP but not P choice.
5. Some students complained to me that having them ALL be ``P but not REG'' was unfair. When I asked him why he told me that since he had 3 of them as ``P but not REG'' his guesses for the rest were NOT that. I reminded him that I didn't just say DO NOT GUESS, I also put LOTS of exclamation points after it.
6. (This point was blogged about before here.) I annouced that if a student gets a negative score on the problem I'll give a 0. Drawback- if they are clueless they SHOULD guess one question.

SO what do you think- is it a fair question? Is it a good question?

Do you support CCC's declaration of Ind? If so...

The steering committee for the CCC recently announced its decision to be independent of IEEE. Here is their open letter to that effect.

1. If you agree with this declaration of independence then you should read the petition here and consider signing it. (I have signed it. Lance didn't.)
2. If you want to read a cleverer blog post on the topic, see Scott's here.

STOC 2014

At the just completed STOC conference I received the 2014 SIGACT Distinguished Service Prize. Part of this citation reads"His blog, and many others that followed, changes the way our field communicates, both with itself and with the outside world." I owe this award to you, my readers and commenters. May the conversations always continue.

The true highlight of the conference happened a day earlier with the Turing award lectures of Silvio Micali and Shafi Goldwasser, two of the better Turing award lectures I've seen in a while. Silvio talked about the nature of proofs and Shafi showed the connections between cryptographic principles and their applications in the broader community. For example, the Goldreich-Levin hard-core bit led to list-decodable codes. The ACM taped both lectures and they should be on-line soon.

Notes from the business meeting

• 372 conference attendees, 46% students. A great attendance.
• 322 submissions, 91 accepts.
• Best Paper: "The matching polytope has exponential extension complexity" by Thomas Rothvoss
• Student Paper: "Online learning of local structure via semidefinite programming" by Paul Christiano
• Gödel Prize (to be awarded at ICALP): "Optimal Aggregation Algorithms for Middleware" by Ronald Fagin, Amnon Lotem and Moni Naor
• Future Conferences:
• FOCS 2014 October 18-21 in Philadelphia. There will be a workshop to discuss ideas for STOC and FOCS moving forward.
• ITCS 2015 January 11-13 at the Weizmann Institute in Israel (CFP)
• STOC 2015 as part of FCRC in Portland, Oregon
• STOC 2016 in Boston likely co-located with SoCG
• Potential federated theory conference in 2017
• NSF
• 2012 Funding: Algorithmic Foundations 52 Smalls, 9 Mediums, 2 Large, 11 CAREER
• New programs (theorists wanted): Brain Initiative, CISE Research Initiation Initiative, XPS
• Keep abreast of new opportunities at Theory Matters
• New ACM Book Series

Law of small numbers and letters

The law of small numbers is that there are not enough small numbers for all of the tasks that are assigned to them. That makes some math cranks find patterns which are really only caused by not enough small numbers around. One such crank kept finding the number 57 in events related to the American Revolutionary war. The fallacy is that if you look hard enough ANY number would work.

At the LLL workshop it was noted that LLL stands for both Local Lovasz Lemma (my wife asked ``an entire workshop about a lemma?'') or the Lensta-Lenstra-Lovasz algorithm. Here we see that there aren't quite enough sequences of letters, hence some get used twice. Of course in this case it helps that Lovasz is brilliant.

The only other example I now of two well known theorems with the same initials of authors is AKS:

AKS primality testing: Agrawal-Kayal-Sazena test of primality in poly time

and

AKS sorting network: Ajtai-Komlos-Szemeredi  O(log n) sorting network.

AKS primality gets 13,500 hits

AKS sorting network gets 39,100 hits

Are there other pairs of well known results where the initials are the same?
(This may depend on what you call ``well known'')

When someone says AKS do you think primality or sorting network?
It may depend on your age and your field. I think of the Ajtai-Komlos-Szemeredi upper bound R(3,k) \le O(k^2/log(k)).  I tend to NOT count that as another collision of initials since its the exact same authors as the other paper.