RaTLoCC (Ramsey Theory in...)

I was at RatLoCC last week which stands for Ramsey Theory in Logic, Combinatorics and Complexity. The idea was to bring in researchers for all three areas (actually its more than three) and have them learn about each others areas.

1. During Szemeredi's talk he said I am not an expert on Ramsey Theory. He meant to say I am not an expert on Ramsey Numbers, e.g., the current upper and lower bounds on R(5).
2. An anagram of Banach-Tarski is Banach-Tarski Banach-Tarski.
3. Bertinoro hosted both RaTLoCC and SUBLINEAR (a workshop on ... SUBLINEAR things) at the same time. We had some shared activities with them. They were a younger, hipper crowd. Ronitt Rubinfeld (who was there) told me they had LESS women than they thought they would have- only 4. We had MORE women then we thought we would have- 2 (we had 0 last time).
4. There were several blogs about the SUBLINEAR workshop: Day 1a Day 1b Day 2a Day 2b Day 3 Day 4a Day 4b
5. One measure of how much you get out of a workshop or conference is how many papers you are inspired to read when you get back home (or perhaps how many pages-of-papers or theorems, or some measure.) With that in mind, here is a list of some of the papers that inspired me. (Slides and abstracts are posted at the workshop's website.)
   1. Szemeredi talked on Arithmetic progressions in sumsets. Here is a sample theorem. Throughout A is a subset of {1,...,n} and n is large. A+A is the set of all sums of two elements of A. LA is A+A+...+A (L times). Sample theorem: For all C there exists c such that if |LA| > Cn then LA has a cn-AP (an arithmetic progression of length cn.) These theorems look HARD but it inspires me to read some papers on Alon's website on this topic, and also my own writeup of sum-product theorems (He used C and c in his talk- though some of them looked the same.)
   2. Noga Alon talked on List Coloring and Euclidean Ramsey Theory. A graph is L-List colorable if there is a way to assign each vertex L colors so that there IS a coloring of the graph where each vertex uses on of the colors assigned to it. Let G be the unit distance graph in the plane: vertices are points in the plane and two points are connected if they are distance one apart. This graph is known to be 7 colorable, known to NOT be 3-colorable. All else is open. Noga talked about his proof (co-author Kostochka) that G is NOT list-s-colorable for any s. The paper is on his website and I am INSPIRED to read it. (ADDED LATER- THE DEFINITION I GAVE ABOVE IS NOT CORRECT. SEE COMMENT BELOW.)
   3. Peter Cholak talked on Reverse Mathematics of Ramsey Theory. Reverse mathematics is a field where they have set up several axiom systems for mathematics (in a hierarchy) and, for MANY theorems of math, they know EXACTLY which system is needed. Infinite Ramsey Theory for PAIRS seems to be stubborn- it is not in any of the usual systems. (formally: RCA cannot prove it, but ACA is too much). It is provably DIFFERENT from Infinite Ramsey for TRIPLETS (which is equivalent to the theorem for 4-tuples, 5-tuples, etc, and for all of them ACA is exact.) My question: when I prove Ramsey for triples I do not feel the earth move or think MY GOODNESS- THAT STEP WAS NONCONSTRUCTIVE!!!! or anything else that is different from Ramsey for pairs. They told me that there IS a proof of Ramsey for pairs that, once you see it, you DO NOT know how to generalize to triples. I may try to look into this. I may not. The paper is at Peter Cholak's webpage and is titled On the strength of Ramsey's theorem for pairs. (co-authored by Jockusch and Slaman)
   4. David Conlon's talk Hypergraph Ramsey Numbers was about Ramsey's theorem for triples. For this case the upper bound is double-exp but the lower bound is single-exp. They made some progress on this, but the upper and lower bounds are still, pretty much, what they were. Still- proofs look very interesting. Progress here is unpredictable--- Conlon said that the problem could be solved next week or next month or not for one hundred years. Also, the proofs are clever- so Erdos COULD HAVE done them. (As opposed to results that use mathematics unknown to anyone in Math at the time.) I am INSPIRED to read this paper by Conlon, Fox, and Sudakov. The case of 3-hypergraph is interesting because, if the lower bound can be gotten up to double exp then for k-hypergraphs we will know that upper and lower bounds are roughly tower(k-1). (Uses the STEPPING UP Lemma.)
   5. Swastik Kopparty talked on The complexity of computing roots and residuosity in finite fields. Say you are in a ints mod p and you want to know whether x is a cube root or not by a constant depth circuit. This will take exp number of gates. Framework is the same as the Parity not in ACC_0 proof, but requires lots more math. MIGHT want to read it. MIGHT be too hard.
   6. Imre Leader gave an excellent talk on Euclidean Ramsey Theory. Here is the basic problem: Let S be a set of points in Rⁿ. IS it the case that, for all c there exists a finite set T in R^m. (m \ge n) such that, no matter how you c-color T there will be a CONGRUENT copy of S? The unit line has this property. If so then S is RAMSEY. It is known that if S is Ramsey then S lies on the surface of some (many dim) sphere. The Main conjecture is that the converse is true. NO says Imre! He has an alternative conjecture here. This paper I am INSPIRED to read.
   7. Jan-Christoph Schlage-Puchta (that is one person) gave an application of VDW's theorem to Completely Multiplicative Automatic Functions This one I NEED to read to put in my book on VDW's theorem. Its here
6. The best talks were those that really TOLD YOU WHAT THE PROBLEM WAS so that the no-specialist could at least here that and then TOLD YOU WHY THEY CARE (even if you don't care you should know why they care) and TOLD YOU SOMETHING ABOUT THE TECHNIQUES. Not all of the talks did this. Also, the best talks were on BLACKBOARD- it forces you to go slower. Not possible at STOC/FOCS etc since the audience is too big, but quite possible here. Only drawback- can't put blackboard talks on the web so easily (though you can if you videotape).
7. The youngest participant: James Pinkerton, my High School Student, gave his talk on Duplicator Spoiler Games that go on an ordinal number of moves. The talk was AWESOME! Before hand he was not scared. He said Whats the worst they can do? Throw red and blue tomatoes at me?
8. One of the people there wore a T-shirt that said Stand back, I'm doing SCIENCE! that had a picture (stick figure really) of a scientists with a test tube. He wore it two days in a row. I commented: Nonconstructive proof that you are a supernerd. Either (1) You wore the same T-shirt two days in a row, so you are a supernerd, OR (2) you have two copies of the same nerdy T-shirt, so you are a supernerd. Of course, in these surroundings, being called a nerd or a supernerd is not an insult.

75 Years of Computer Science

As Lipton and Felten note, today is the 75th anniversary of Turing's On Computable Numbers, With an Application to The Entscheidungsproblem, the seminal paper of seminal papers in computer science.

If you read any part of it, read Section 9, his justification of why the Turing Machine model captures computation, an argument that still resonates today.

No attempt has yet been made to show that the “computable” numbers include all numbers which would naturally be regarded as computable. All arguments which can be given are bound to be, fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically. The real question at issue is “What are the possible processes which can be carried out in computing a number?”

The arguments which I shall use are of three kinds.

1. A direct appeal to intuition.
2. A proof of the equivalence of two definitions (in case the new definition has a greater intuitive appeal).
3. Giving examples of large classes of numbers which are computable.

Once it is granted that computable numbers are all “computable” several other propositions of the same character follow. In particular, it follows that, if there is a general process for determining whether a formula of the Hilbert function calculus is provable, then the determination can be carried out by a machine.

Cell Phones versus Drunk Driving

Most of you are familiar with the research that using a cell phone is just as dangerous as driving drunk.

Method: We used a high-fidelity driving simulator to compare the performance of cell phone drivers with drivers who were intoxicated from ethanol (i.e., blood alcohol concentration at 0.08% weight/volume). Results: When drivers were conversing on either a handheld or hands-free cell phone, their braking reactions were delayed and they were involved in more traffic accidents than when they were not conversing on a cell phone. By contrast, when drivers were intoxicated from ethanol they exhibited a more aggressive driving style, following closer to the vehicle immediately in front of them and applying more force while braking. Conclusion: When driving conditions and time on task were controlled for, the impairments associated with using a cell phone while driving can be as profound as those associated with driving while drunk

That and similar research has led to bans on hand-held (though usually not hands-free) cell phone use in many locations. Statistics are hard to come by but there are more alcohol-related accidents and many more alcohol-related deaths than those due to cell phones. Yet there are far more people talking on cell phones than driving drunk. This contradiction bugged me. What's going on?

Unlike using a cell phone, drunk driving is not a binary event. It's not that you are either drunk or you aren't. There are degrees based on the blood alcohol level. The real dangerous drivers are those way over the legal limit. Driving at the legal limit (0.08% in Illinois) isn't that dangerous or the limit would be lower.

When we hear that using cell phones are just as dangerous as driving drunk, we think, wow, cell phones are very dangerous. But our thoughts of the dangers of drunk driving is not at the level of drunkedness that are compared to cell phones.

Driving at the legal limit and on your cell phone are only mildly more dangerous than driving sober and distraction free. I'm not recommending that you drink or use your cell phones while you drive, you are certainly safer without doing so. But you should also be careful about reports about the dangers of activities and be sure the comparisons are correct. 

Is Computer Science Cool Again?

Back in 2005 I worried about loss of excitement about computer science among America's youth.

Today computers have become almost as commonplace as televisions and teens use them for a variety of tasks, including researching on the web, communication via email, instant messaging and blogging, and writing papers, all without an inkling of how to program. Computers have become a commodity and they don't see an additional value in knowing how and why they work any more than they need to know physics to drive their cars.

Yesterday IBM's David Ferrucci gave a talk at Northwestern on the challenges of creating Watson to play Jeopardy. The large lecture room was packed mostly with undergrads. Ferrucci didn't disappoint showing the challenges of Watson with lots of examples keeping the talk not too technical. Ferrucci will give a similar talk as an FCRC plenary speaker or you can watch a short version here.

My 12-year old daughter Molly came and enjoyed the talk and insisted on meeting Ferrucci afterwards just to tell him how cool Watson was.

The number of CS majors has grown dramatically in recent years at Northwestern and other universities. Bank of America runs ads on their ATMs that understands peoples checks ("How do they do that?") and Ford on how its Focus parks itself. And our local high school next year is teaching computer science again.

Håstad to receive the 2011 Gödel Prize

The 2011 Gödel Prize is awarded to Johan T. Håstad for his paper:

Some optimal inapproximability results, Journal of the ACM, 48: 798--859, 2001.

Håstad is the fourth person to win the prize twice (after Shafi Goldwasser, Mario Szegedy and Sanjeev Arora). He won the 1994 Gödel Prize for his switching lemma and tight bounds on parity for low-depth circuits.

The official citation:

This is a landmark paper in computational complexity, specifically, the study of approximation properties of NP-hard problems. It improves on the PCP Theorem (recognized in a previous prize in 2001) to give novel probabilistic verifiers that can check membership proofs for NP languages while reading very few bits in them — as little as 3 bits. The existence of such verifiers implies that existing approximation algorithms for several problems such as MAX-3SAT cannot be improved if P is different from NP. In other words, there is a "threshold" approximation ratio which is possible to achieve in polynomial time, but improving upon which is NP-hard. Before this paper such "optimal" inapproximability results seemed beyond reach. The Fourier analytic techniques introduced in this paper have been adapted in dozens of other works, and are now taught in graduate courses in computational complexity. They also directly influenced subsequent work, such as the formulation of the unique games conjecture for proving further optimal inapproximability results, and lower bounds for geometric embeddings of metric spaces.

On demand Publishing (guest post)

Cambridge Press (and others) offers PRINT-ON-DEMAND for some books. This is a guest post by Lauren Cowles from Cambridge Books about this, and then my comments on her comments, and then her comments on my comments. We stop there or else this could go on forever (OR we could make each block half the size of the prior block...)

LAUREN:

Print on demand is expanding rapidly all over the publishing industry. It's a way to keep books available if not forever at least much longer than they otherwise would be. This benefits people who want the books and the publishers who want to sell them.

The main factors are: Printing technology is now generally computer-driven, like everything else. There is no longer any need to set up film (or plates) to print from; many printing presses work from something that's essentially a fast and very high resolution laser printer. Therefore there is less economy of scale because there is much less in the way of set-up cost.

It is still cheaper to print several hundred books than to print them one at a time, but not nearly as much cheaper as you might think. So for many books there is now a tradeoff between the cost of the warehouse space and the unit cost. Also, of course, publishers are not spending money on books they might not sell. When sales drop below the point at which this tradeoff favors a conventional printing, we can often switch a book to being printed on demand simply by emailing the printer -- most of the printers we use now do both "conventional" printing and print on demand.

To get a print on demand book, all a customer has to do is order it in the normal way. The process is also so fast now that the customer normally has to wait only a few days more than if the book were in stock on the shelves.

BILL:

1. Will there be a time when there is NO cost diff between ordering one book and ordering in bulk? Will book companies only print on-demand?
2. Will Kindle and similar devices make print-on-demand a short-lived technology?
3. What does print-on-demand and kindle mean for the future of book publishers?
4. If these are cheap enough will they undercut the used-book market? If Kindle is the future will there no longer be such a think as a used book? (Molly Fortnow's daughter will ask Whats a used book mommy?.)
5. For academic books I am very happy that they will live on forever via either on-demand or kindle. Sometimes out-of-print math books are either impossible to find or are too expensive.
6. Will the notion of a rare book be obsolete?

LAUREN:

1. I doubt that the unit costs for print-on-demand will ever be cheaper than the unit costs for 500+ copies. But the PoD cost is low enough now that companies can make the choice for every book, and change that choice later in the book's lifetime. There already exist companies that only do print on demand (Lulu, for example).
2. Again, I doubt it.
3. Print on demand means we can keep things in print longer. What Kindle means is anybody's guess. Here in the publishing industry we are living in interesting times.
4. If fewer new books get printed, there may be a vogue for the old printed object... The used textbook market may be affected. I think the big textbook publishers have been trying for ages to find an electronic textbook model that will catch on, so that they can sell the electronic thing over and over at some similar-to-used-book price rather than sell the big expensive textbook once (effectively, directly into the used book market). I like to think people are keeping their Cambridge books so the used book question doesn't arise. (NOTE FROM BILL: I tell my students that they can buy ANY edition of the book for the course, they do not need to get the latest one. NOTE FROM BILL: Cambridge Press mostly does high level monographs which people are less likely to sell used.)
5. Cambridge Press has brought hundreds of books back into print now that we can afford to reprint them (eg Beck and Chen, Irregularities of Distribution).
6. In the sense of hard-to-find, yes. Google books has been scanning a lot of out-of-copyright books and making them available electronically. Cambridge U Press is doing something similar: we have been scanning classic books in the University Library and offering them as print-on-demand (eg Gibbs, Elementary Principles of Statistical Mechanics). The original of this from 1902 is still rare.

President Regan (not Reagan)

Whose name (in firstname lastname form) appeared most often in the pages of Newsweek in the 1970's? Is it---?

1. Richard Nixon
2. Gerald Ford
3. Jimmy Carter
4. Ken Regan.

The answer could well be... Ken Regan. Ken Regan is a photographer. Many pictures in Newsweek had Photo credit Ken Regan in tiny letters up the side.

I was emailed an invitation to an event titled Ken Regan Presents Bob Dylan, and I wondered if I was emailed this because

1. I have the largest collection of Bob Dylan satires in the world .
2. I am friends with Ken Regan who, for all I know, in addition to being a computer scientist, chess player, language expert, blogger, choir singer, and would-be composer and writer, could also be a photographer.
3. This email went to EVERYONE,
4. This email was spam (not clear how this differs from the last choice).

I emailed Complexity-Ken who told me (1) there is a photographer Ken Regan, and (2) Complexity-Ken-Regan does not equal Photographer-Ken-Regan. Sharing a name with a photographer seems okay. Its better than sharing a name with a vicious murderer, or worse, a Congressman.

Photographer-Ken has one thing going for him: he registered the domain www.kenregan.com. Thus Complexity-Ken has forever lost the chance to emulate www.fortnow.com or www.scottaaronson.com. Still, Complexity-Ken often pushes the domain into second place in Google searches, and simply Google Regan without any firstname at all turns him up on the first page of hits. Why is that? It may be a prerogative of being both a computer scientist and a blogger who tends to make a lot of comments under his real name, with his name (or handle KWRegan) linking back to his site. Perhaps Google regards this as legitimate self-citation, ticking up his page's "authority" score for each one?

Complexity-Ken's wife Debbie Howe is shares a name with the originator of the popular children's book series Bunnicula. However, Complexity-Ken-Wife-Debbie took Complexty-Ken's surname as her middle name and has used the resulting full name in some publications, which Google Deborah Regan Howe finds. More generally, preserving the Google trail has become a factor in wives' keeping their maiden names after marriage. I suspect its a bigger factor than feminism or being-your-own-person or other very good reasons. (I posted on this already here.)

FCRC Early Registration May 16

One final reminder for the FCRC Conference. Early registration deadline is this Monday, May 16.

There are a number of events at FCRC of interest to our readers: STOC, Complexity, Electronic Commerce, SPAA, PODC and Foundations of Mobile Computing. Plenary talks include Leslie Valiant's Turing Award lecture, Ravi Kannan's Knuth Prize lecture and David Ferrucci (the guy who led the Watson Jeopardy project).

No STOC tutorials this year, but EC has some interesting tutorials and workshops on topics including Bayesian Mechanism Design, Social Computing, Network Economics, Implementation Theory and measuring advertising effectiveness. You can still apply for one of four free student registrations for EC.

And last and definitely least: Bill and I will both be there. Maybe we'll do another Complexity Vidcast. Maybe you'll be on it.

Those Happy Samoans

Below is a post I wrote in 2009 but for some reason never made it to this blog. But I had better post it now because, as I found out via Tony Wirth, Samoa is moving across the international date line, 24 hours into the future. That should make Hawaii the last place on Earth to end the day, making conference deadlines an hour earlier.

So are the Samoans losing a hour to submit their papers or are they gaining twenty-three?

Update 12/28/11: Western Samoa is skipping this Friday to make the switch. American Samoa is not making the switch and will be the last place on Earth to end the day, an hour after Hawaii.

---

The deadline for ICALP 2009 was February 10th at 12:30 PM in Greece where the conference will be held. Did you sleep late and miss it? Why not have the deadline in late afternoon so people can keep working on their papers?

But in fact the deadline was Tuesday. At least while it was Tuesday anywhere in the world. So ICALP waits until the small country of Samoa approaches midnight before making its papers due. So the Greeks get all morning Wednesday. The New Zealanders have all day Wednesday until 11:30 PM. With Daylight Savings Time, the Kiwis are a full day ahead of the Samoans.

Nothing against the fine citizens of Samoa but it is not a hotbed of theoretical computer science. So it still seems strange to list the submission deadline as "February 10, 2009, (23:30 GMT-11)" in a time zone from which they will likely get no submissions instead of just giving the deadline as February 11, 2009 (10:30 GMT).

Not all conferences follow the Samoan rule. Complexity deadline is midnight Eastern on Friday. At EC we used Midnight GMT on Monday and we received a few complaints from people in the US. I just didn't want to have to be up at 4:30 AM Chicago time making sure the submission server wasn't crashing.

The NSF has a policy of submission of 5 PM in the submitter's time zone. So perhaps conferences could have a deadline of midnight in the place the submitter lives. This would give those Samoans the extra time they so richly deserve.

How has the STRUCTURES, OH- I mean CCC Conference changed: Lets look at the Call For Papers

Complexity theory has changed over the years. How to really track these things? One way is to look at the list of topics on the Call For papers for the CCC conference (called STRUCTURES until the name changed, another sign of change). Below I include pointers to the call for papers from 1986, 1997, and 2008. I also include the list of topics and I comment on them.

1. The 1986 CCC (then called STRUCTURES) call for papers (third page is best view) had this list:
   1. Structure of Complexity Classes. (What does this even mean?)
   2. Properties of NP-complete sets.
   3. Relations between Complexity Classes. (I wish we had more.)
   4. Resource-bounded Reducibilities.
   5. Theory of Relativizations. (I think this means oracles.)
   6. Recursion Theoretic Aspects. (To general.)
   7. Kolmogorov complexity and randomness.
   8. Crypto-complexity.
   9. Applications of Finite Model Theory.
   10. Independence Results. (I wish we had more.)
2. The 1997 CCC call for papers had this list:
   1. Structure of Complexity Classes. (I still do not know what this means.)
   2. Resource-bounded Reducibilities.
   3. Interactive Proof Systems.
   4. Computational Randomness.
   5. Circuits and other Concrete Computational Models.
   6. Proof Complexity
   7. Communication Complexity.
   8. Theory of Relativizations. (I'm surprised this is still here.)
   9. Complexity and Logic. (To general.)
   10. Kolmogorov complexity.
   11. Cryptographic complexity. (Is this different from Crypto-complexity?)
   12. Complexity and Learning. (Has there ever been a paper on this at CCC?) (ADDED LATER- Rocco found quite a few and then I generated a list which I am sure is incomplete here.
3. The 2008 call for papers had this list:
   1. Structure of Complexity Classes (Do they keep this topic for traditions sake?)
   2. Reducibilities and Completeness.
   3. Proof Complexity.
   4. Interactive and Probabilistic Proof Systems.
   5. Inapproximability. (I'm surprised this wasn't on the 1997 list.)
   6. Complexity in other Concrete Computational Models. (Other than what?)
   7. Kolmogorov complexity.
   8. Quantum Complexity. (Not sure when it first entered the list, though it was on the 2002 CFP.)
   9. Circuits Complexity.
   10. Communication Complexity.
   11. Complexity and Logic. (Too general.)
   12. Pseudorandomness and derandomization. (How does this differ from Computational Randomness?)
   13. Average case complexity. (I'm surprised it was not on the 1997 list.)
   14. Complexity and Learning. (What is this still doing on the list?)
   15. Cryptographic complexity.

NOTES:

1. The only topics on all three lists: Reducibilities, Kolmogorov Complexity, Cryptographic complexity. Maybe randomness. Depending on how you count `Logic and Complexity' maybe finite model theory.
2. I was surprised there was NOTHING on concrete models of complexity in 1986. Furst-Saxe-Sipser was already known (1981 FOCS, 1984 MST) so I would think Circuits would be of interest. Realize that FSS was first presented as an attempt to get an oracle that separates PH from PSPACE (which later succeeded- Yao and Hastad). You can feel the paradigm shifting and circuits becoming important unto themselves as opposed to servicing recursion-theoretic complexity.
3. Perhaps I shouldn't be surprised- the list of topics may lag behind the reality. It takes a few years to catch up.
4. The number-of-topics has grown from 10 to 12 to 15. At this rate...
5. The change to the topics seems to have come WITHOUT an old guard resisting the change. Why was this? TCS is young enough that people could change fields? TCS is young enough to not have an old guard?

Forty Years of P v NP

In the afternoon of May 4, 1971, in the Stouffer's Somerset Inn in Shaker Heights, Ohio, Steve Cook presented his STOC paper proving that Satisfiability is NP-complete and Tautology is NP-hard.

The theorems suggest that Tautology is a good candidate for an interesting set not in [P] and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory. 

And thus Cook formulated what was soon to be called the P versus NP problem. The rest is history.

Here's the 1971 STOC Program (there were 143 attendees) and what that sacred ground looks like today.