Sadness

The end of UC Berkeley as we know it

There are two qualities that together make UC Berkeley unique among worldwide institutions of higher education.

One is that our several academic departments cover nearly all fields of scholarship, and that nearly every department is at the very top of its field. Very few places have this phenomenal combination of breadth and depth, although, admittedly, there are some.

The other is the diversity of the student body. Not ethnic diversity, because the passage of Proposition 209 made black and (to a lesser extent) Latino students almost disappear from campus. But, at least, UC Berkeley has been an engine of upward social mobility for a lot (and, being a big campus, it is really a lot) of white and Asian Californians from middle and working class families. To be sure, the top East Coast private universities do admit several students who are not from privileged families, and they do provide generous financial aid, but one has to be off-the-charts brilliant to get in based on raw talent alone. The merely very smart students can get in only if they have the kind of expensive resume-padding extracurricular activities that are out of reach for most students. At Berkeley, the merely very smart student has a good chance to get in by simply doing well in high school. And then, tuition is low for everybody who is from California, and the state used to give additional grants (80% of tuition) to everybody with a 3.0 GPA; plus the UC system has its own financial aid program.

Two days ago, the Chancellor announced that because of the cuts expected as a consequence of the state-wide budget crisis, UC Berkeley needs to cut about $100 millions. Next year, we should expect a complete freeze on hiring, layoffs of administrative staff, strong cuts to student aid, increased tuition, and salary cuts of 8%. For 2010-2011, rumors are that the sun will go dark, it will rain blood from the sky, and then the locusts will come and eat us alive. Unfortunately, 2011-2012 will be much worse.

So this is what “FOCS” stands for

At the STOC 2009 business meeting, Silvio Micali announced a new conference, Innovations in Computer Science (ICS), whose first edition will be in Beijing in January, 2010.

This is a conference that aims to be the venue for the first papers in new areas. This prompted people to ask me afterward if we shouldn’t start a new conference devoted to second papers. I thought this was an appealing ideas, and perhaps the conference could be called Follows-up in Computer Science; a snarky colleague, however, suggested that we already have two such conferences and they are called STOC and FOCS.

ICS has a steering committee entirely composed of past and future Turing Award winners, so surely they know what they are doing. A common complaint I heard, however, was that it isn’t clear exactly what the motivations and the goals of this conference are, what papers are being sought (surely you cannot fill up a 30-paper conference with first papers, each opening up a new area), and so on.

Helpfully, Oded Goldreich, one of the promoters of ICS, has written a statement about the goals ICS, as well as a longer essay on What is wrong with STOC and FOCS. The arguments made in the essay are Oded’s motivations for the new conference.

As I have said before, I agree with the importance of conceptual innovations, and of simplicity, but I disagree with the claim that our current review system undervalues such points. Hence, I think that initiatives such as the “letter on conceptual contributions” and now ICS will not correct an imbalance, but rather will create an imbalance, penalizing the necessary, hard, and unglamorous technical work by which we understand new ideas, exploit and simplify their applications, and create the conditions such that the next new ideas are “in the air” and the right person at the right time can get them, and so on.

LaTeX2WP minor update

LaTeX2WP is a program that converts a LaTeX file into something that is ready to be cut and pasted into the WordPress online editor. It makes it easier to write mathematical posts, to post lecture notes on WordPress, and so on.

A new version is now available, which fixes a couple of bugs:

• WordPress has trouble if a mathematical expression containing is followed by a mathematical expression containing . This is prevented by converting the inequality symbols to their HTML “character codes.”
• The previous version of LaTeX2WP had trouble with long sentences in square brackets; this is fixed.

In addition, \S for § and \v{C} for Č (as “in Stone–Čech compactification”) now work.

CS276 Lecture 27: Computational Zero Knowledge

Scribed by Madhur Tulsiani

Summary

In this lecture we begin the construction and analysis of a zero-knowledge protocol for the 3-coloring problem. Via reductions, this extends to a protocol for any problem in NP. We will only be able to establish a weak form of zero knowledge, called “computational zero knowledge” in which the output of the simulator and the interaction in the protocol are computationally indistinguishable (instead of identical). It is considered unlikely that NP-complete problem can have zero-knowledge protocols of the strong type we defined in the previous lectures.

As a first step, we will introduce the notion of a commitment scheme and provide a construction based on any one-way permutation.

The Loser Gets Pregnant First

After reading the mouseover text of today’s dinosaur comic:

I couldn’t help looking up the Pseudobiceros hancockanus flatworm, and here is a PBS video of two of them engaged in penis fencing. (direct link)

The Triangle Removal Lemma

[At the end of a survey paper on additive combinatorics and computational complexity which is to appear in SIGACT News, I list three major open questions in additive combinatorics which might be amenable to a "computer science proof." They are all extremely well studied questions, by very smart people, for the past several years, so they are all very long shots. I don't recommend anybody to start working on them, but I think it is good that as many people as possible know about these questions, because when the right technique comes along its applicability can be more quickly realized.]

The first question is to improve the Triangle Removal Lemma. I have talked here about what the triangle removal lemma is, how one can prove it from the Szemerédi Regularity Lemma, and how it implies the length-3 case of Szemerédi’s Theorem.

As a short recap, the Triangle Removal Lemma states that if is an -vertex graph with triangles, then there is a set of edges such that the removal of those edges eliminates all the triangles. Equivalently, it says that if a graph has triangles which are all pair-wise edge-disjoint, then there must be triangles overall.

The connection with Szemerédi’s Theorem is that if is an abelian group with elements, and is a subset of with no length-3 arithmetic progressions (i.e., is such that there are no three distinct elements in such that ), then we can construct a graph that has vertices, pair-wise edge-disjoint triangles, and no other triangles. This contradicts the triangle removal lemma if , and so we must have .

This is great, until we start looking at the relationships between the constants hidden by the notation. Quantitatively, the Triangle Removal Lemma states that for every there is a such that if a graph has at least pair-wise edge-disjoint triangles, then it has at least triangles. The only known proof, however, has incredibly small: grows like a tower of exponentials of height polynomial in . The proof uses the Szemerédi Regularity Lemma, and the Regularity Lemma is known to require such very bad dependencies.

63 years ago, Behrend showed that , prime, has a subset that contains no length-3 arithmetic progression and whose size is . (Last year, Elkin gave the first improvement in 62 years to Behrend’s bound, but the improvement is only a multiplicative polylog factor.) Combined with the graph construction mentioned above, this gives a graph with vertices, edge-disjoint triangles, and no other triangle. Thus, the graph has triangles where , but one needs to remove edges to make it triangle-free, where . This shows that, in the Triangle Removal Lemma, must grow super-polynomially in , and be at least .

The question is to shorten the gap between the tower-of-exponential relationship between and coming from the proof via the Szemerédi Regularity Lemma and the mildly super-polynomial lower bound coming from the above argument.

CS276 Lecture 24: Zero Knowledge Protocols

Scribed by Milosh Drezgich

Summary

Today we introduce the notion of zero knowledge proof and design a zero knowledge protocol for the graph isomorphism problem.

CS276 Lecture 28: the CZK 3-Coloring Protocol

Summary

Today we define the notion of computational zero knowledge and show that the simulator we described in the last lecture establishes the computational zero knowledge property of the 3-coloring protocol.

CS276 Lecture 22: Signatures in the Random Oracle Model

Summary

In the last lecture we described a very complex signature scheme based on one-time signatures and pseudorandom functions. Unfortunately there is no known simple and efficient signature scheme which is existentially unforgeable under a chosen message attack under general assumptions.

Today we shall see a very simple scheme based on RSA which is secure in the random oracle model. In this model, all parties have oracle access to a random function . In implementations, this random function is replaced by a cryptographic hash function. Unfortunately, the proof of security we shall see today breaks down when the random oracle is replaced by hash function, but at least the security in the random oracle model gives some heuristic confidence in the design soundness of the construction.