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.