Depth thru Breadth

Chandra mentioned Avi Wigderson's invited STOC talk on whether theory is still a unified discipline. Avi's talk slides are now online (PPT alas!), and I recommend going through them, if only to get a magnificient birds eye view of what has been accomplished in the theory of computation, and it how all connects up.

What is STOC ?

From Googlism, answers to the question: What is STOC ?

---

The Factual:
stoc is acm symposium on the theory of computing
stoc is the largest acm symposium
stoc is considered one of the most prestigious conferences in computer science
stoc is traditionally held in a different location each year

The Legal:
stoc is not responsible or liable

The Predictive:
stoc is still growing
stoc is rising
stoc is bottoming
A bit confused, that one..

The Reflective:
stoc is a good source
stoc is pretty much for fun
stoc is for you

and finally, The Mystical:
stoc is god

Copy Protection: the next generation...

From Salon.com:

The Bush administration is offering a novel reason for denying a request seeking the Justice Department's database on foreign lobbyists: Copying the information would bring down the computer system.

"Implementing such a request risks a crash that cannot be fixed and could result in a major loss of data, which would be devastating," wrote Thomas J. McIntyre, chief in the Justice Department's office for information requests.


I don't know whether to find this amusing as a computer scientist, or to be very worried as a foreign visitor whose records all sit inside one of these systems. Maybe the open goverment advocates forgot to offer up some delightful dragon dainties.

Lower bounds comeback ?

Maybe I am reading too much into titles, but it seems like hardness results are back in business again. From a highly unprofessional inspection of the FOCS list:

An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching

Hardness of Approximating the Shortest Vector Problem in Lattices

Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique

On the (Im)possibility of Cryptography with Imperfect Randomness

The Hardness of Metric Labeling

Hardness of buy-at-bulk network design

Optimal Inapproximability Results for MAX-CUT and Other 2-variable CSPs?

---

If I get a chance I will comment on some of the interesting geometry papers out there (have been pinging authors for copies).

FOCS list is out...

Here.

Academics and the media

I've always wondered how reporters know whom to ask for a pithy quote on a technical topic. This article from the Christian Science Monitor (via ALDaily) illuminates the matter.

However, the following caught my eye:

For scholars, press interviews can bring fringe benefits or advance a career. Although news clips never substitute for publishing in scholarly journals, they can help the teaching reputation of a tenure-seeking professor who consistently attracts students drawn to a celebrity. Beyond that, Williams says, comes the satisfaction of knowing, "I can reach a million people, and I love that." He admits, "There's maybe an ego satisfaction involved."


You'd think the blogosphere could take care of that problem....

What is a good review ?

In a comment on my previous post, David Molnar asks:

Could you be more specific about the "many other conferences" that give better feedback than theory?

Well, I don't want to name names :). The reason I don't want to name names is because every time I have, the usual reaction has been "but our papers are much higher quality than theirs", which I think misses the point and clouds the issue.

Let me say though what I consider a "good" set of reviews: the areas I have in mind exemplify this to varying degrees. Note that I don't necessarily think there is any such thing as a good review per se; I am more interested in a good set of reviews. This good set would contain:

* at least one that comments on the merits of the work and how it fits into the broader picture (or not, in case the reviewer doesn't like the paper).
* Some review that tracks detailed issues (even typos, minor errors etc): not all reviews need to do this, but it is useful for the author to know that someone read it thoroughly.
* Something that comments on why the reviewer likes the paper. This is an underrated feature: it's ok to learn from criticism, but without any sense of whether the reviewer actually appreciates my work, it is hard to get a sense of perspective on the criticism.

Overall, a sense that the reviewer understands the paper and assesses it from that perspective. Personally, I can accept a scathing review when the reviewer demonstrates an understanding of my work; it is harder to accept one when I see glaring gaps in the reviewer's comprehension.

My comments about "other areas" comes from submitting papers and looking at the extensive reviews that I get back, and comparing that with reviews from theory conferences, where I can occasionally be lucky to get even one line total from all three reviews. It also comes from the reaction of some of my coauthors (who are not used to theory reviews).

As I said earlier, a lot of this can be explained by the mechanics of the review process: it is a lot easier to review 10 papers thoroughly than 60.

SODA 2005

A friendly reminder. SODA submissions are due a week from today (Jul 5 @ 5 pm EDT). If you are working on submissions, do register them in advance. More instructions are here.

The Importance of Operations Research

The Boston Globe has a careful and well thought out article by Virginia Postrel on the importance of operations research over the years. She finesses the tiresome theory-practice debates rather well, by describing how the theoretical development of the field was boosted by the emergence of large data sources on which to apply the field's arsenal of algorithms.

I found the following line hilarious:
"In some OR journals today, the only empirical data are, `Date of submission' and `date of acceptance."'

---

Via Instapundit

On gaming program committees

Lance Fortnow has an interesting take on conference acceptance procedures today. He argues:

Two easy ways to improve your paper but lessen your chances of acceptance at a conference: Add more results and simplify your proofs. Adding a result could only increase the usefulness of a paper but program committees see many results in a paper and conclude that none of them could be very strong. One of our students a few years ago had a paper rejected at STOC, he removed one of his two main theorems and won the best student paper award at FOCS.

Given the same theorem, the community benefits from a simple proof over a complicated proof. Program committees look for hard results so if they see a very simple proof, it can count against you.

I agree mostly with his take on how PCs view papers: simple proofs can indeed be looked down upon. The interesting question is this though: since PC members are the same people who, when not on PCs, have this problem, what is it about PC membership that causes their judgement to skew ?

The usual argument is load: PC members in algorithms conferences typically review far more submissions than PC members in any other conference mainly because of two inter-related reasons:

1. Our PCs are small
2. PC members are not permitted to submit papers to the conference

(note that (2) more or less forces (1)).

Or could one argue that it is the right and appropriate thing for PC members to prune papers in this fashion ? And that it is the authors' responsibility to make the best case for their submission in a system which will always be imperfect ? One might think that this reasoning would encourage, rather than discourage, simple proofs, because these are easier to understand and lead to a better exposition in a conference setting.

It seems to me that one reason an elegant proof might be looked down upon in comparison to a more technical, grungy proof is that if the reviewer is not intimately familiar with the area of the paper, they might not appreciate the value of the elegant result, or be aware of how hard it was to achieve such an understanding of a problem etc. This doesn't sound like a problem that can be fixed easily, unless every paper can be reviewed by an expert in that specific area, which seems difficult to manage.

I would like to venture the slightly controversial claim that theory (STOC/FOCS/SODA/etc) committees are not as rigorous in providing feedback and comprehensive reviews as many other conferences. There are many good reasons why this is the case, and I don't think one can fault reviewers who do the best they can under severe load, but the fact remains, and it would be nice to see more discussion of this in business meetings or even in informal forums in the community.

Although this is somewhat removed from the original point about reviews themselves, I feel that feedback itself is a method for ensuring accountability and openness. A reviewer who has to write a detailed explanation of what they like/don't like in a paper will automatically do a more thorough job of reviewing it. Again, this is not a matter of harasssing reviewers: structural changes will have to made in how theory committees are set up to make this practical.

On Apollonian supergaskets, or how I always wanted to use 'syzygy' in a sentence.

Friday at the AT&T Math Seminar, Allan Wilks gave a beautiful talk on 'The Apollonian Supergasket', a structure that contains all strongly integral Apollonian packings via a set of simple operations. This posting is drawn heavily from his talk: all mistakes are mine :)

---

Apollonian Gaskets:
Apollonian circle packings come from the Apollonius Problem:

Given three objects, draw a circle mutually tangent to all three.

When the objects are circles themselves, and are already mutually tangent, there are exactly two solutions to this problem (an inner and outer solution), and these are called Soddy circles¹

It is very easy to compute the two Soddy circles. If we denote b_i = 1/r_i as the bend of a circle of radius r_i, then

2(b₁² + b₂² + b₃² + b₄²) = (b₁ + b₂ + b₃ + b₄)²

This is known as the Descartes Circle Theorem, and the four bends together are called a Descarte quadruple. What is intriguing is that if we wish to determine the circle centers, we can do so as well. If the centers are represented as complex numbers z_j, then Colin Mallows has shown that the numbers b_i * z_i also form a Descarte quadruple. An important note is that bends can be negative: if three mutually tangent circles are touched by a circle that includes all of them, its bend has a negative sign (you can think of this on the sphere to see why: the "sense" of the circle is inverted)

Now take four mutually tangent circles, and pick one. For the other three, find the "second" mutually tangent circle. Add that in and repeat. This yields a packing of the plane, called the Apollonian Gasket. Depending on the starting set of four circles, one can obtain many different kinds of gaskets.

The Supergasket:
Now comes the stunning part². A set of two simple inversion operations allows us to move from one Descarte configuration to another. One operation we have already seen: if we consider the two solutions to the 3-circle Apollonian problem, they invert to each other with respect to a fixed circle. This gives us one new circle for a fixed set of three.

The other inversion operator works as follows. Take one of the Soddy circles, and invert its three touching circles into it. This yields another 4-circle configuration inside the Soddy circle.

There are a total of eight such operations (4 for each kind of inversion). Together, these operations generate a special group called a Coxeter group with appropriate syzygies. Among the properties of these operations are:

• Each pair of circles thus generated are tangent or disjoint
  
• If the starting configuration is (strongly) integral, so are all resulting configurations.
  
• The resulting set of configurations contains all strongly integral Apollonian packings
  

That last statement is what for me is so amazing. Essentially there is a single universal packing that contains all Apollonian packings (in the integral case). This is a truly mysterious structure.

Also, there are beguiling symmetries if we look at outer circle configurations (configurations where there is one outer circle and three inner circle). The mod 2 bend groups are symmetric with different axes of symmetry, and all outer circles having the same bends form symmetric patterns in the supergasket.

---

Notes:
1. Apollonian circle problems were discussed in Sangaku (Japanese Temple Geometry) that I had talked about earlier. More on Sangaku here (via GJ).
2. When Allan was giving this talk, he said 'beautiful' so many times he had to restrain himself; now as I try to describe this in words, I understand his problem :)

References:
This is based on work by Jeff Lagarias, Ron Graham, Colin Mallows, Allan Wilks and Catherine Yan.

Papers: (at www.arxiv.org)

• Beyond The Descarte Circle Theorem
  
• Apollonian Circle Packings: Geometry and Group Theory:
  I: The Apollonian Group
  II: Super-Apollonian Group and Integral Packings
  III: Higher Dimensions
  
• Apollonian Circle Packings: Number Theory
  

Einstein, Poincaré, and Picasso

An interesting review of cubism in the Guardian talks of the influence Henri Poincaré had on Picasso.

Cubism was never a style in that sense. It was an inquiry. Picasso and Braque were lucky enough to be young - Picasso was 28 in 1909, Braque 27 - at a time of intellectual revolution. Habits of perception and assumptions about the nature of things that had been stable since the 17th century were falling away. Arthur I Miller's 2001 book Einstein, Picasso: Space, Time and the Beauty that Causes Havoc demonstrates how uncannily Picasso's discovery of cubism parallelled Einstein's contemporary theories of special and general relativity. In science, mathematics and philosophy, the laws of a clockwork universe established by Sir Isaac Newton in the Baroque age were giving way before the first world war to extraordinary notions - that time and space are one, that light waves curve, that no two observers ever see exactly the same thing.

Picasso and Einstein, Miller has shown, were both influenced by the French thinker Henri Poincaré, who published his book La Science et l'Hypothèse in 1902.
...
Picasso learned about his ideas through the mathematician Maurice Princet, who was a regular at Montmartre cafe tables. Picasso's friend André Salmon wrote that Princet "preoccupies himself especially with painters who disdain ancient perspective. He praises them for no longer trusting the illusory optics of not long ago... "

Knot or not ?

A recent posting on comp.theory prompted this note:
given the 3 dimensional layout of a rope, I would like to know if
pulling the strings at both ends would result is knot or not.

MathWorld had this to say:
There is no general algorithm to determine if a tangled curve is a knot or if two given knots are interlocked. Haken (1961) and Hemion (1979) have given algorithms for rigorously determining if two knots are equivalent, but they are too complex to apply even in simple cases (Hoste et al. 1998).

Note that the question MathWorld asks appears to be slightly more general (asking if a given curve is a knot or not). The question by the comp.theory poster (I imagine) only asks about a motion pulling in two opposite directions (although this is probably not the most precise way to put it).

I imagine that the answer to the question posted above is well known: I'd be interested in a pointer if anyone has one.

---

There are a plethora of links on the web concerning knot theory. The Geometry Junkyard has a knot theory page, and a far more comprehensive set of links can be found at Knots On The Web.

Lindstrom's Lemma

I recently came across an interesting combinatorial lemma on graphs. Let G be a planar DAG, and designate the 2n boundary nodes as sources and sinks (consecutively, so walking around the boundary you see first the n sources and then the n sinks). Construct the n X n matrix M where m_ij = number of distinct paths from source i to sink j. Then

Lindstrom's Lemma:
Each minor D_I,J of M is the number of families of non-intersecting paths from sources indexed by I to sources indexed by J.

Thus, every minor of M is non-negative. A matrix having this property is said to be totally non-negative.

---

Source: Combinatorics and Graph Theory, by Mark Skandera

Mathematicians are a machine....

And this is some machine: espresso in your car...Mmmmm

---

(via Boing Boing)

More visa woes...

I think Sariel needs to send the USCIS some more virgin red dragon blood.

From the AP Wire:

Foreigners with worker visas must reapply for them overseas when they expire, the State Department said Wednesday.

Department spokesman Richard Boucher said that in the past, foreigners with worker visas were able to reapply for visas in the United States.

The reason for the switch, he said, is that U.S. embassies abroad are better equipped than government offices in the United States to interview and fingerprint the growing number of visa applicants.

"These people can stay as long as they want. They can leave when they want," Boucher said. "But when they come back, instead of getting a visa here in advance, they will have to get one overseas at one of our embassies and consulates and then come back."

Foreign Students and Visa Issues

For a long time, Lance Fortnow has been warning us about the problems facing foreign students and scholars (of which your humble blogger is one) trying to visit the US, stay here, and travel to scholarly meetings. Nitish Korula, an Indian student who recently got admission to the Ph.D program at UIUC, has been chronicling his suffering as he navigates the student visa process.

Although this may not be news to those of us in research/academics, it's nice to see discussion of this problem spreading beyond the confines of academe. Today at Talking Points Memo, one of the most widely read blogs on the Web, John Judis discusses this issue.

Lance mentioned the cold war and how countries tried to keep their scientists from coming here: this quote is from Judis's post:

During the Cold War, American officials discovered that one of the best ways to promote democratic capitalism at the expense of communism was by luring foreign students to American colleges. Some of these foreign graduates returned home to become the leaders of reform movements in their countries. Others stayed in the United States and contributed their skills to the great postwar boom. The same reasoning that prevailed during the Cold War should prevail during the war on terror. The United States should be eager, one would imagine, to expose students from abroad to democracy and religious pluralism, as well as to take advantage of their skills.

More on Origami

I had posted a note on computational origami a couple of months ago. The NYT has an article today on David Huffman (of Huffman coding) and his fascination with computational origami. The Geometry Junkyard has a page on origami.

STOC 2004: A Report (Part III)

This is the third post in Chandra Chekuri's STOC 2004 report: Part I and Part II were posted earlier.

---

A Probabilistic Lemma due to Uri Feige

One of the cute results in STOC is the following probabilistic bound due to Feige.

Let X₁, X₂, ..., X_n be independent positive random variables with mean 1. Note that we do not make any assumptions about their distribution and hence their variance can be arbitrary and in particular they are not iid. Let X = X₁ + X₂ + ... + X_n. By linearity of expectation µ, the mean of X, is n.

A typical question in bounding the deviation of sums of random variables is the following.

What is probability that X deviates significantly from its mean?
We have a variety of bounds including the Markov inequality, the Chebyshev inequality and of course the Chernoff-Hoeffding bounds. Of these the Markov inequality is the simplest and pretty much makes no assumptions other than that the rv is non-negative:

Pr[X > t µ] <= 1/t for a non-negative rv X.
Phrasing it in a different form, Pr[X <= t µ] >= 1-1/t.

Cheybyshev inequality is useful when we have a bound on the variance of X but in our case we don't. Chernoff bounds are the most useful for sums of bounded independent random variables. Feige's bound is quite different. He showed that Pr[X <= n+1] > 1/13. In other words there is a constant probability that X deviates by an additive 1 from the expected value. Note that the Markov inequality would give a bound of 1/(n+1) which is very far from the truth in this case.

Feige uses the above bound for an application to estimate the density of a graph but it is not the most compelling one (as he himself states). He anticipates more interesting applications in the future.

An Open Problem:
The bound Feige shows is 1/13 but the worst case example he knows has a bound of 1/e where e is the base of the natural logarithm. It is the obvious one: Each X_i takes on a value of (n+1) with probability 1/(n+1) and 0 otherwise. Therefore the probability that X is at most n+1 tends to 1/e. Feige conjectures that this the right bound. The problem is all yours.

---

Calling India

WARNING: Non-geometry info ahead...

---

Reliance India is now offering 12c/min calling card service to India. This is significantly better than what current calling card operators are giving, and is way better than what the big telcos like AT&T et al are offering (much as it hurts me to say so :)

I just signed up, and so I don't know what the call quality is like, but given that that is a Reliance endeavour, it should be good.