Snow Days

An unexpected snowstorm hits the city in the middle of a workday. The roads get hopelessly clogged and I'm lucky to get home--many others just abandoned their cars, or slept in them. I'm talking about Valentine's Day, February 14, 1990 in Chicago. But the same story hit Atlanta yesterday. One big difference--Georgia Tech is closed today and tomorrow because the city can't handle the ice. The University of Chicago was open on February 15th. 

When these events happen, people wonder about the planning. Was it wise for all schools and businesses to shut down about the same time, early yesterday afternoon? Lots of blame to go around (and having CNN based in Atlanta guarantees coverage) but it is not clear that any plan would have done much better--how do you get millions of people safely home with dangerous roads and a limited public transit system? One of these times you wish P = NP and you can just find the right algorithm. One of the issues is that freak mid-day snowstorms don't happen that often, the last major one in Atlanta was 1982.

Meanwhile back in Chicago, schools were closed earlier this week, not for snow but for cold. But it was that cold on a regular basis back in the 90's. Global warming has changed expectations, as so brilliantly illustrated in this xkcd. 

Fermat's Last Theorem and Large Cardinals. Really!

A brilliant math ugrad at UMCP, Doug, is also a creative writer who
wants to work on large cardinals. His creative writing may help him there.
We had the following conversation:

DOUG: The proof of Fermat's last theorem depends on the existence
of certain large cardinals and hence is not in ZFC.

BILL: That is not true.
DOUG: Have you read the proof?
BILL: No, however, if that were true I would know it. See this blog entry.
DOUG: Why would you know it?
BILL: If FLT required LCs then

a) Number theorists would be nervous.
b) Logicians would be ecstatic
c) The math community would not have announced to the world that FLT was solved.
d) Wiles would not have collected his prize money for solving it.
e) Again, I would know it.

DOUG: All compelling arguments. Even so, FLT requires LCs.
BILL: I will bet you five dollars that the current proof of FLT does not depend on LCs.
DOUG: Uh. Your counter arguments are compelling.
BILL: So... no bet?
DOUG: Uh. No.

The next day I got an email from Doug with the subject heading

        I cheated myself out of five dollars.

 Doug found this article, What does it take to prove Fermat's Last Theorem? Grothendieck and the logic of number theory by Colin McLarty, from 2009.The article says that YES the  current proof of FLT DOES depend on LCs. Note that the proof is quite long and uses lots of other stuff that is sort of buried in it. So--- whats the catch?Why aren't number theorists nervous and logicians ecstatic? According to the article anyone who reads the proof of FLT and wanted to could unwind it  and get it down to ZFC (and likely down to PA). But nobody has bothered yet.Hence nobody is nervous or ecstatic.

I will take their word for it, but it does make ME nervous. NOT about FLT which I am sure enough people have looked at (and looked at the background literature) that it really can be made to work in ZFC.I am more worried about papers that are not quite so looked at as having LC assumptions that are hidden from the reader that cannot be easily removed.

However KUDOS to Doug for telling me something in math that I did not know and should have.  I will treat him to a more-than-five-dollar-lunch.

Postscript: AH, the article was right: FLT was proven using ordinary set theory last year. (See here) by Colin McLarty (I assume its the same person). I will still take Doug to lunch- in a stupid, pedantic, technical sense I was right- the current (2014) proof of FLT did not use LC. But for the real issue of there being any problem at all, I was clearly wrong. Only a logician would say I was right. Hmm- Doug is a logician. Its up to him. (Hmm- my spell checker allows `Hmm' but not `Hmmm')

What will we wrought?

When I went to college in the early 80's, students protested against college endowments invested in companies that had business in apartheid South Africa. My mother worked as a statistician for one of those companies. An interesting dilemma, do I support a policy that hurts the company that is indirectly helping to put me through college?

Now my daughter is in college and worrying that the computing revolution will make it hard to find a job once she graduates and making her consider those job prospects in the major she chooses. And what am I? Chair of a computer science department that helps push that revolution forward.

Computing gets quite a bit of blame these days for the widening income gap between the have and the have nots, and jobs taken over by automation, but without causing a corresponding need for other types of jobs, other than those that serve computation itself. Are those fears real? We can't answer that question yet, positively or negatively. Time will tell.

For now, we just need to do our jobs, making computing better but also understanding and mitigating the negative effects of computing. We need to make sure that computing technology becomes a growing sea that raises all boats, and not just making the world better for the technological elite.

While I stand in awe in how computer science has changed the world, I hope we don't ever end up with CS leaders getting together and saying "What have we wrought?"

We don't care about Ballroom Dancing. Should we?

YOU got into your undergrad school because not only were you good at Math but you were on
the Fencing Team and in the Latin Club (so you could taunt your opponents in Latin: ouyah allcay athay an alestrabay!). Also you had a letter from your principal who never had you for a class but can comment on your leadership since you organized a pep rally for the football team. Why does UNDERGRAD admissions care about these things? Because, while they want good students, they also want to build a community of scholars of different interests and abilities.

YOU apply to grad school in Computer Science. Hey, it worked once maybe it will work again! You write about being in the ballroom dancing club and you have a letter from the Dean, who never had you in a class,
but you worked in his office and he can attest that you are a good leader and a hard worker.

Does the admissions committee care? NO. The only things we care about are CS, MATH, and RESEARCH. A letter from someone not in math or science is worthless. Some exceptions and thoughts:

1. If you recorded ballroom dancing and made a project out of how to teach it using some interesting new technology this IS good. This is likely an Human-computer-interaction project; however, I would care about this no matter what field you are going into.
2. If you have an interest in Nat Lang Proc and know Linguistics I would care.  I would think that knowing a foreign language would also be good.
3. If you are going to go into Human computer Interaction then Psychology helps.
4. If you are going to do Quantum Computing then Physics is good. However, whatever you do Physics is good as its more evidence of math ability.
5. For ugrad its been said that if your parents are powerful OR donors you may have an easier time getting into some UGRAD schools. What about Grad school? I've honestly never seen a case of this so I honestly don't know. 

I know a student who is an excellent math major but also a creative writer. I doubt this will help him.
but should it?

I once saw in a students application a letter from his preacher attesting to his fine moral character.
Do we care? should we? How about the other way around- if someone was an EXCELLENT programmer and math person but served 8 years for armed robbery would we care? This might not be fair since perhaps he reformed.

but my real question is- for grad admissions we don't care about Ballroom Dancing or other misc.
Is this a mistake? If someone was NOT as good at math BUT a better writer, should we take them?

Favorite Theorems: Introduction

I was invited to give a talk at the FST&TCS conference held in December 1994 in Madras (now Chennai). As I searched for a topic, I realized I was just finishing up my first decade as a computational complexity theorist so I decided to recap the past decade by listing My favorite ten complexity theorems of the past decade (PDF). Not so much to choose winners, but use the theorems to survey the great research during those past ten years.

In 2004, I repeated the exercise in my then young blog for the years 1995-2004. In 2005, I went back in time and chose my favorite theorems from the first decade of complexity (1965-1974) and in 2006 I covered 1975-1984, completing the backlog of the entire history of computational complexity.

Now in 2014 we start again, recapping my favorite theorems from 2005-2014, one a month from February through November with a recap in December. These theorems are chosen by a committee of one, a reward only worth the paper they are not written on. I choose theorems not primarily for technical depth, but because they change the way we think about complexity. I purposely choose theorems with breadth in mind, using each theorem to talk about the progress of a certain area in complexity. I hope you'll be presently surprised by progress we've made in complexity over the past decade.

A short History of Crypto

I taught a 3-week summer course to High School Students called

Computer Science: A Hands Off Approach

which did some theory. One thing I did was the following storyline:

1. Shift Cipher
2. Affine Cipher
3. Gen perm cipher (any perm of a,b,c,...,z
4. PROOF that perm is unbreakable: Eve has to go through all 26! possibilities
5. PROOF that perm IS breakable: Freq analysis. Moral of the story: Any proof that a system is unbreakable makes some assumptions that Eve might not agree to. Hence proving security is tricky.
6. Matrix Ciphers. PROOF that if you use a big enough matrix its unbreakable. Sort-of true for ciphertext only (though I doubt really proven). PROOF that requires going through all possibile nxn matrices that have det rel prime to 26 to crack it using plaintext only. PROOF that this is NOT true (I leave that to my reader).
7. Vig Cipher. Proof that its unbreakble, Proof that you can break it

I was very happy with this since it really instilled in them that proofs of security are nontrivial and always have assumptions. That does not mean they are not worth anything, but you want to get the assumptions explicit to if (or even WHEN) the system is broken, you can see what assumption needs to be attended to for the next iteration. One caution- these were VERY GOOD students so they GOT IT. They didn't mistake the false proofs for real ones.
(NOTE-- I never teach the cows paradox - all cows are the same color- when
doing induction since half the class will think induction can prove anything and the other half will think that all cows are the same color.)

I then encapsulated all of this with what I call A SHORT HISTORY OF CRYPTO:

 For i=1 to infinity
                Alice and Bob: We have a cipher that nobody can crack
                Alice and Bob: We have PROVEN that it can't be cracked
                Eve: I just cracked it
                Alice and Bob: Whoops.


(I later did Diffie-Hellman in the class which I will talk about in a later blog.)

Is Traveling Salesman NP-Complete?

[Nina Balcan asked me to mention that the COLT submission deadline is February 7]

Jean Francois Puget writes a controversial post No, The TSP Isn't NP Complete which I discovered during a lengthy twitter discussion with Puget and Peter Cacioppi.

There is a well-known technicality for the Euclidean Traveling Salesman problem but let's focus instead where we are given a complete graph weighted with positive integers. One version of TSP is truly NP-complete

TSP Decision: Given an integer B, is there a cycle through all the vertices such that the total weight of the edges used is at most B?

TSP Decision is in NP by guessing the cycle and hardness by a simple reduction from Hamiltonian Cycle.

Puget's makes the point that we normally think of the TSP problem as an optimization question

TSP Minimization: Find the cycle through all the vertices that minimizes the total weight used.

TSP Minimization is not even a decision problem. In the 80's, Mark Krentel created a complexity class OptP to capture optimization problems and showed that TSP Minimization is Opt-P-complete.

One can use TSP Decision to solve TSP minimization by doing binary search, so they have effectively have the same complexity.

Puget points out that even if we are given a tour, checking that it is the shortest tour is not believed to be in NP. That problem is in co-NP and I'm guessing co-NP-complete. [Update 3/20: I was right]

Puget doesn't like when people claim TSP is NP-complete when they are talking about the optimization problem. For example from my P v NP survey

The NP-complete traveling salesperson problem asks for the smallest distance tour through a set of specified cities. 

I'm far less bothered than Puget. Those who understand the technicalities of NP-completeness know that one has to convert the optimization problem to an appropriate decision problem to formally get an NP-complete set. Others aren't led too far astray, for we do have an equivalence that P = NP if and only if there is an efficient (polynomial-time) algorithm for TSP Minimization.

Tell me more about Alice and Bob

A while back my parents were in town on a weekend when I was scheduled to give a talk to HS students who had done well on the Maryland math competition. Logistics dictated that my parents goto the talk. (They were both English majors and wouldn't like me using the word `goto' since its not a word. Fortunately they don't read this blog and see what else I do to the English Lang.)
I gave a talk on Communication Complexity (slides are here) where I did the following:

1. I stated the problem: Alice has x, Bob has y, both strings of length n. They want to know if x=y without too much communication.
   
2. I noted that they can easily solve this with n+1 bits of communication and raised the question of Can They Do Better?
   
3. We discussed this. Someone mentioned average case (informally), which helped me clarify the problem. Someone else suggested sending the number-of-1's and if it didn't match they weren't equal, but also noted that if they did--- weren't sure. Most thought that one COULD do better or else I wouldn't be talking about it.
   
4. I tell them that NO you can't do better (I do not prove this).
   
5. I told them about mod arithmetic and how in mod p, p a prime, poly of degree d have at most d roots.
   
6. I presented the O(log n), error 1/n, randomized protocol for equality that uses polynomials mod p.
   
7. I briefly talked about comm complexity in general.
   

The talk went well. It is a good topic for good HS students, and if you want to borrow my slides you can (you may need to update the political reference). Having not understood ANY of the talk Mom had the following question:
MOM: Alice and Bob-- are they married?
BILL: Oh. I'll say no.
MOM: If they are not married then how come they have such a hard time communicating?
DAD: (he didn't say anything but I could tell he agreed).

Two cheers for the Pardon of Turing. But not three.

As I am sure readers of this blog know Alan Turing was prosecuted for homosexuality in 1952, forced into hormone treatment, and committed suicide in 1954 (I had always heard that that was WHY he committed suicide
though the dates don't quite line up--- at that time he seemed to be recovered form the ordeal. So there are some legit questions about this.)

He was recently given a Royal Pardon. While I am glad he was pardoned this does raise some questions. Lets me logical.

1. If we believe the law criminalizing homosexual acts was unjust (as I am sure that all of my readers do) then Turing is a red herring- they should pardon ALL people convicted. AND note that  according to this there are 15,000 men who were convicted of this crime who are still alive.
2. Pardon means that the person didn't do the crime. This is not the case here. However, laws are supposed to promote justice, not block it.

Here is hoping that the Pardon of Turing will lead to a general pardon.

(NOTE- the pointer in item 1 says more of what I wanted to say, but says it
more elegantly than I ever could.)