Sorting vs Searching:

In a previous post, I had mentioned an upcoming paper in FOCS 2004 by Franceschini and Grossi titled 'No Sorting? Better Searching!'.

The paper is not yet online, but Roberto Grossi posted a long comment in that post detailing the results in the paper. I reproduce the comment below in full; a short summary is:

They show that the natural way to do searching in a set of ordered elements (i.e via sorting and then doing binary search), makes sense when the cost of comparisons is O(1), but does not make sense when elements are larger (formally, when each element of the list actually consists of k characters, where k is super-constant). They do this by demonstrating a new ordering technique that beats known lower bounds on searching a sorted list; what's nice is that their result is tight as well.

His abstract follows (bold-face is mine):

Sorting is commonly meant as the task of arranging keys in increasing or decreasing order (or small variations of this order). Given n keys underlying a total order, the best organization in an array is maintaining them in sorted order. Searching requires Θ(log n) comparisons in the worst case, which is optimal. We demonstrate that this basic fact in data structures does not hold for the general case of multi-dimensional keys, whose comparison cost is proportional to their length. In previous work [STOC94, STOC95, SICOMP00], Andersson, Hagerup, Håstad and Petersson study the complexity of searching a sorted array of n keys, each of length k, arranged in lexicographic (or alphabetic) order for an arbitrary, possibly unbounded, ordered alphabet. They give sophisticated arguments for proving a tight bound in the worst case for this basic data organization, up to a constant factor, obtaining

Θ[ (k log log n)/(log log (4 + (k log log n)/(log n)) + k + log n ]

character comparisons (or probes). Note that the bound is Θ(log n) when k=1, which is the case that is well known in algorithmics.

We describe a novel permutation of the n keys that is different from the sorted order, and sorting is just the starting point for describing our preprocessing. When keys are stored according to this ``unsorted'' order in the array, the complexity of searching drops to Θ( k + log n) character comparisons (or probes) in the worst case, which is optimal among all possible permutations of the n keys in the array, up to a constant factor. Again, the bound is Θ(log n) when k=1. Jointly with the aforementioned result of Andersson et al., our finding provably shows that keeping k-dimensional keys sorted in an array is not the best data organization for searching. This fact was not observable before by just considering k=O(1) as sorting is an optimal organization in this case.

When the paper is available I will link to it here; one interesting question is: how hard is this "other" order to compute ?

That wonderful feeling of nothing...

A friend of mine just defended his Ph.D successfully (congratulations, Nabil !), and sent me this excerpt (extracted from here) in response to my email congratulating him:

In February 1995, on a beautiful sunny day with clear Carolina blue skies, I turned in the final,signed copy of my dissertation. The graduate school staff member did some last-minute checks on the document and pronounced it acceptable. After six and a half years of toil and sweat, I was finally done! While walking back to the C.S. department building, I was sorely disappointed that the heavens didn't part, with trumpet-playing angels descending to announce this monumental occasion. Upon hearing this observation, Dr. Fred Brooks (one of my committee members) commented, 'And the sad fact is, you're no smarter today than you were yesterday.'"


Another amusing take on graduate student life, from the same article:

Being a graduate student is like becoming all of the Seven Dwarves. In the beginning you're Dopey and Bashful. In the middle, you are usually sick (Sneezy), tired (Sleepy), and irritable (Grumpy). But at the end, they call you Doc, and then you're Happy.

Path compression...

The main takeaway from the Seidel-Sharir paper refining the analysis for union-find, as explained to me by Adam Buchsbaum (who is still walking the corridors in amazement):

If path compression takes linear time, then it takes α(n) (amortized) time.

Truly amazing. Worth reading just for that...

Topology rules the playground !

This is the last place you'd expect to see a lucid discussion of topological concepts:

Boing Boing: Double twist strip playground equipment

Why do algorithm engineering ?

I was listening to a talk today where the speaker made the following statement: 'We know that this works well in theory, and now we'd like to see if it works well in practice'. Now this is a statement I have probably heard hundreds of times over the past many years, and it is in no way noteworthy or unusual.

However, it did get me thinking. It is by now a truism that no one will seriously dispute that there is often a gap between the theoretical predictions offered by an algorithm analysis and the behaviour of this algorithm in practice. Contrary to what many people would conclude, this is of course not a black mark on the value of theoretical work. The power of algorithm analysis, poly-time, and even the much maligned O() notation, lies in the invariance of (classical) machine definitions under poly-time transformations, and the powerful mathematical structure that complexity theory acquires as a result.

This structure does have a tradeoff; we get mathematical elegance, but lose a certain modicum of "predictiveness" when it comes to analysing the behaviour of an algorithm "in practice". And I think herein lies the true value of algorithm engineering. If the algorithm that has better theoretical guarantees does better in practice (and this happens more often than one thinks), one's task is complete; if not though, all is not lost. Often, peculiarities in the data cause certain algorithms to behave better than others, even though from an asymptotic perspective a different outcome would be expected. Sometimes, analysing the running time is not the right measure: output-sensitivity in geometric algorithms is an example of a measure that captures certain desirable properties that can be missed with a blunt-edge worst-case running time.

But ultimately, the goal of algorithm engineering, or of good experimental algorithmic work, is to tease out the tradeoffs, parameters and special cases that govern which algorithm is the right one for a specific setting. If I am a practitioner, I am less interested in knowing the algorithm with the best asymptotic efficiency than I am in knowing which algorithm can provide the best performance for my situation. This does not mean that we should throw proofs out of the window: it means that often a much more delicate analysis of the behaviour of an algorithm is required in order to determine what works better.

---

I think I just wrote an ALENEX manifesto. Oh well :)

A Pentium III ?

From Forbes, via the Computing Research Policy blog (emphasis added):
Meanwhile, another even more serious threat to the U.S.' competitive position in supercomputing is lurking in the shadows. Tucked away into the House version of the National Defense Authorization Act, which passed in May, is Section 1404, which would classify any computer using a Pentium 3 processor or stronger as a 'militarily critical' machine to the Department of Defense--or, a weapon--and make it subject to tightened export regulations. While high-performance computers are already regulated separately as part of a 1991 agreement with Japan, called the Supercomputer Control Regime, the new restrictions would arguably affect certain systems components developers need for supercomputers.

If a Pentium III can be classified as military weaponry, suddenly I don't feel so safe anymore.

GR conferences are more interesting than one might imagine

This is from John Baez's latest column describing the frenzy at a general relativity conference in England where Stephen Hawking conceded the bet he and Kip Thorne made with John Preskill:

A fellow with long curly grey locks and round horn-rimmed glasses sat down beside me. I'd seen him around the conference, so I said hello. He asked me if I'd like to hear about his theory; at this point my internal alarm bells started ringing. I told him I was busy, but said I'd take a look at his manuscript later.

It turned out to describe an idea I'd never even dreamt of before: a heliocentric cosmology in which the planets move along circular orbits with epicycles a la Ptolemy! And his evidence comes from a neolithic British tomb called Newgrange. This tomb may have been aligned to let in the sun on the winter solstice, but some people doubt this, because it seems the alignment would have been slightly off back in 3200 BC when Newgrange was built. However, it's slightly off only if you work out the precession of the equinox using standard astronomy. If you use his theory, it lines up perfectly! Pretty cute. The only problem is that his paper contains no evidence for this claim. Instead, it's only a short note sketching the idea, followed by lengthy attachments containing his correspondence with the Dublin police. In these, he complained that people were trying to block his patent on a refrigerator that produces no waste heat. They were constantly flying airplanes over his house, and playing pranks like boiling water in his teakettle when he was away, trying to drive him insane.

Things to do with an iPod...

courtesy BoingBoing:

1. Have drink
2. Eat pizza
3. Find loo...

Entertaining audio reviews and even accompanying sound tracks such as Handel’s ‘Water Music’ and ‘Cosmic Winds’ will help users to locate their nearest (and loveliest!) loos.

---

For people challenged in the Queen's English, loo = restroom.

Black holes mangle matter and energy, but cricket IS better !

I had recently mentioned Hawking's retraction of his claim that a black hole destroys everything that enters it. He has now presented his work at a conference on GTR.

A footnote to this story is the famous bet that Hawking and Kip Thorne (of CalTech) had with John Preskill (also at CalTech). The terms of the bet were:

"information swallowed by a black hole is forever hidden and can never be revealed."
Preskill bet against that theory.

The forfeit is an encyclopedia, from which Preskill can recover information at will.


Since Hawking lost the bet, he owed Preskill an encyclopedia:

He presented Preskill a favored reference work "Total Baseball, The Ultimate Baseball Encyclopedia" after having it specially flown over from the United States.

"I had great difficulty in finding one over here, so I offered him an encyclopedia of cricket as an alternative," Hawking said, "but John wouldn't be persuaded of the superiority of cricket."


However, the matter does not appear to be resolved:

But Preskill says that Hawking's new take on quantum gravity rests on shaky mathematical foundations, and is unlikely to be embraced by the physics community. "I am sceptical about whether he has found a fully satisfactory resolution to the problem," he says.

What's eccentric about that ?

From the Fields Medal citation for Tim Gowers:

Banach was an eccentric, preferring to spend his time in the café rather than in his office in the University of Lvov

sounds reasonable to me...

The Two Cultures...

Michael Nielsen, in his ongoing series on the principles of effective research, talks about problem solvers and problem-creators as two models of research:

The problem-solver: This is the person who works intensively on well-posed technical problems, often problems known (and sometimes well-known) to the entire research community in which they work. The best problem-solvers are often extremely technically proficient and hard-working. Problem-solvers often attach great social cache to the level of difficulty of the problem they solve, without necessarily worrying so much about other indicators of the importance of the problem.

The problem-creator: This is a rarer working style. Problem-creators may often write papers that are technically rather simple, but ask an interesting new question, or pose an old problem in a new way, or demonstrate a simple but fruitful connection that no-one previously realized existed.

In an interesting coincidence, Chandra Chekuri just pointed me to Tim Gowers' (the 1998 Fields Medallist) website. There, Prof. Gowers has an article titled 'The Two Cultures', where he talks essentially about the same schism in mathematics, between problem solvers, and theory builders.

It is interesting to compare the two reflections. Nielsen feels that the 'problem-creator' style is rarer, and "less popular" than the problem-solver mode. In Gowers' view, theory builders look down on problem solvers (for example, people who do combinatorics) because of a perceived "lack of depth" and other such reasons.

The two polarities are not quite the same; but read together they provide a thoughtful perspective on the kind of schisms that we all face in our research work. I can definitely attest to feeling the kinds of conflicts they talk about, between 'solving problems' and 'building theories'.

Somehow writing a blog itself seems to fly in the face of Hardy's dictum:

There is no scorn more profound, or on the whole more justifiable, than that of the men who make for the men who explain. Exposition, criticism, appreciation, is work for second-rate minds..

Browsing the amazing list of expository articles at Gowers' website, it is comforting to see this shibboleth too go by the wayside.

Reading Harry Potter makes you very smart...

Today I got an email from Amazon.com (emphasis added)

Dear Amazon.com Customer,

As someone who has purchased books by J. K. Rowling, you might like to know that "Harry Potter and the Philosopher's Stone (Ancient Greek Edition)" will be released soon. You can pre-order your copy at a savings of 30% by following the link below


I knew that reading is good for you, but I didn't know that reading Harry Potter was that good for me...

Pacing...

The virtues of pacing are highly underrated. When you have over 60 submissions to review, the immenseness of the task can completely drown out all rational thought. The number of papers to be reviewed on a per-day basis is not that bad, but you have to stick to a routine !

Taking breaks is also a good thing: I finished my quota today, and I shall now soothe my fevered brow with a good helping of topological spaces via Claude Chevalley. Aaaahh.....

Useful trivial answer

Probably my first exposure to science fiction was via Isaac Asimov, and his robot books. I am shuddering at the thought of what the movie version of I, Robot did to his vision, and the review in Slate is not encouraging.

This little nugget of information is fascinating, and should be a Jeopardy question:

"By the end, Asimov achieved the Grand Slam of book writing, turning out at least one volume for each of the 10 classifications in the Dewey Decimal System."

Conferences and the e-print server at LANL

Lance has a nice post on the reason why conferences are so much more important in CS than in other (older) fields:

The answer is technological, namely airplanes. Before air travel conferences were much more difficult to attend and drew from a much more regional audience. Those who made the great effort and time to attend a conference were allowed to present. But presenting your paper at such a conference would not reach the majority of your colleagues. Journals were the most efficient way to broadly publicize your research and took on the more important role and have kept that role for historical reasons.

Computer science started as a field during the jet age. Many more people from a wider geographical base could attend a conference. One could now widely disseminate their research through conferences well before a paper appeared in a journal. Journals still played an important role for refereeing, editing and archiving but never held the importance in computer science as conferences do

Lance goes on to speculate as to what changes the internet will bring in our models of publication. It seems to me that the LANL e-print archive is one example of a new paradigm. Interestingly this has been adopted much more readily in the "old" field of physics than in computer science (as an aside, why is it that physicists always come up with cool technological developments ?), and this effect even shows up in areas like quantum computing that are on the border of the two fields.

In a sense, this is the logical evolution of the conference. If you want a place to disseminate results quickly to a wide audience, what better way to do it than via the e-print server, especially given how active it has become. Physicists still publish in journals as the primary source, but e-prints have helped replace some of the functionality of the conference.

Conferences will really never go away, since there is no replacement for direct one-on-one contact in my opinion, but e-prints are definitely a new Internet-only model...

Networking on the Network

Phil Agre has an article on networking on the internet for Ph.D Students. There are many general principles there that are quite interesting, and far too many to summarize in a brief post.

One nice excerpt:

Most people get socialized into institutions such as the research world without anyone ever explaining how the institutions work. For example, few PhD students ever get explicit lessons on the sorts of career strategies that I have been explaining in this article. What is more, the social world is filled with unspoken rules that keep these things hidden, for example the taboo against boasting or the imperative of explaining one's motives in terms of the general good rather than in terms of self-interest. These unspoken rules help people to get along, but they also make it much harder for average PhD students in complex professional interactions to figure out what is really going on. Most students do acquire up some insight from watching the experts, but they usually do not develop a complex theory like the one I have been explaining here. As a result, they often perceive their social environment in a relatively superficial way.


Pointer chase: Michael Nielsen -> Daniel Lemire -> Phil Agre.

All the above links spin off some interesting reading. In particular, Nielsen's ongoing series on the principles of effective research has some insightful thoughts.

Putnam Problem of the day...

Harvard has a Putnam Exam page that contains (apart from all the Harvard rah-rahing), a "problem of the day". Today's problem:


In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty 3x3 matrix. Player 0 counters with a 0 in a vacant position and play continues in turn until the 3x3 matrix is completed with five 1s and four 0s. Player i wins if the determinant is iPlayer 0 wins if the determinant is 0 and Player 1 wins otherwise (thanks, Amit). Assuming optimal strategies from both players, who wins and how ?


What they need is an RSS feed. hmm....

News of the day...

Some trivial...

On the origins of 'blog', from EvHead... (via BoingBoing)

....Blog was originally devised by British fans in the 1950s. There were two versions. A Liverpool fan named Peter Hamilton came up with the recipe for Blog Mark I, which consisted of "a brandy and egg flip base, to which was added black currant puree, Alka Seltzer, and Beechan's Powder. It effervesced." A second, simplified version (Blog Mark II) was produced by hotel barmen at the first Kettering Eastercon (1955) and consisted of "a half-pint of cider and a measure of rum."
...
You'll roll down stairs, fall off your chair, and hump your neighbors dog
It goes with a snack, you'll lie on your back, it's blog, blog, BLOG!

It's blog, it's blog
It's pink, it's yummy, it's punch
It's blog, it's blog
It'll make you lose your lunch

You're gonna love your blog
Come on and get your blog
Everyone loves their blog

And some not so trivial:

From the New Scientist:

After nearly 30 years of arguing that a black hole destroys everything that falls into it, Stephen Hawking is saying he was wrong. It seems that black holes may after all allow information within them to escape. Hawking will present his latest finding at a conference in Ireland next week.

Crisis in Science ?

<Rant>
In what twisted universe does 11pt and 12 pages actually mean 10pt, illegible margins, and 20 pages ? I tell you, this is the real crisis in science.
</Rant>
Phew: now I feel better...

So this article from the Chronicle of Higher Education talks about the problems facing universities trying to admit students for graduate studies. However, even after I read it a few times, I couldn't quite figure out what its central thesis was. The subtitle says:

Leaders warn of a labor shortage in the U.S., but indicators point to an oversupply

However, the following data points are presented:

* graduate enrollment from Taiwan has dropped by 25 percent
* NSF announced that foreign enrollment reached a new peak by 2002.
* A survey of 113 schools showed a 32% drop in foreign enrollment in those schools (especially from China)
* Purdue, UCLA and UT Austin are cited as examples of foreign enrollment either going up, or number of foreign applications going up.

If you are confused at this point, join the club.

Regarding overall jobs in the market,
* BLS predicted in 2001 that there would be a 47% increase in jobs in science and engineering by 2010
* Unemployment rates in computer science and systems analysis jumped to 6.7%
* unemployment among chemists is at "an all time high", as measured in terms of the number of postdocs.

Now I am getting rather dizzy.

The article deals with a complex matter, and I can respect the need to factor in a number of different statistics, but it is not clear to me that there is any story here at all. Enrollment is going up and down, jobs are going up and down, foreigners are applying more or less: what is the conclusion ?

If we look at the summary of the article:

...although no one can predict how many scientists and engineers the nation will need in 20 years, everyone agrees that the faces of those technical leaders will be far more diverse than those of generations past, and that American universities will scour the world for the best minds.

I don't know: it seems a little wishy-washy to me...

Some detailed methodological problems:

1. There is a conflation of science vs engineering, Ph.D vs M.S vs bachelors degrees, research jobs vs non-research jobs etc. These have different dynamics, and it is dangerous to draw broad conclusions from the aggregate of so many different sectors. For one thing, unemployment in computer science may not necessarily be related to employment prospects for Ph.Ds, because the IT industry has such a huge effect on such numbers....

2. They use number of US-authored publications to indicate a "flat" trend for research in the US. Without more details, it is hard to understand this statistic. As we know from SODA/STOC/FOCS, classifying papers by country is almost meaningless in times of multi-authored papers, and in experimental fields with lots of authors/paper, even more so.

3. There is a lot of confusion over US-born student enrollment vs foreign-born student enrollment; some stats are quoted for one group, some are quoted for the total

4. Using the rate of postdoc employment to infer general trends may or may not work in general. Do people in the natural sciences go for postdocs because they can't get jobs (as was the case in theory in the early 90s), or because they NEED a postdoc to even cross the interview threshold (as appears to be true in biology at least, and maybe physics). It is possible that mathematics is an example of the first case, but I don't know if math was part of this study at all.

A point that is not made often enough:

Mr. Freeman, like other economists, looks to dollars to make sense of the trends among graduate students. "They're not studying science," he says, "because they look and say, 'Do I want to be a postdoc paid $35,000 or $40,000 at age 35, with extreme uncertainty working in somebody else's lab, and maybe getting credit for my work and maybe not getting full credit? Or would I rather be an M.B.A. and making $150,000 and hiring Ph.D.'s?'"

---

p.s So I just spent all this time writing a review of an article in the CHE instead of writing a review of a SODA submission. oh well....

The 'e' movie

No, this is not an electronic movie, it is literally, a movie about e (or a fantasy on what one would look like).

In a whimsical and interesting article on ABC News (found via topix.net), John Allen Paulos speculates on what a movie about e might look like. He was prompted by the fame achieved by the golden ratio via The Da Vinci Code, and pi via the eponymous movie.

He gives four examples of the 'natural occurrence' of e: for my amusement, I decided to subtitle the examples with the actual mathematical principle. All of these are old friends of of the theoretical computer scientist:

1. Divide up a square portion of the night sky into a very large number, N, of equal smaller squares. That is, imagine a celestial checkerboard. Then search for the N brightest stars in this portion of the sky and count how many of the N smaller squares contain none of these N brightest stars. Call this number U. (We're assuming the stars are distributed randomly so by chance some of the smaller squares will contain one or more of the brightest stars, others none.)

If one knows some probability theory, it's not hard to prove that the ratio of N to U (N divided by U, that is) is very close to e and approaches it more and more closely as N gets large.

Indeed. 1/e is the limit of the expression (1-1/n)ⁿ as n grows unboundedly large.

2. A somewhat unusual appearance of the number involves two decks of cards. Shuffle each deck thoroughly, turn over a card from each, and note if it's the same card (both 7s of diamonds, for example, or both jacks of clubs). Then turn over another card from each deck, and note if it's the same card. Continue doing this until all 52 cards in the decks are turned over. It can be shown that the probability of no matches at all between the two decks during this sequence of turnovers is extremely close to one chance in e; that is, the probability is 1/e or about 37 percent.

This is the classical derangement problem. For many of us, the first introduction to the Principle of Inclusion and Exclusion.

3. ...imagine this year's high school graduates running a quarter-mile race. Runners are randomly selected and sequentially over a period of months each of them runs a quarter-mile and we keep track of the number of record times that they establish. The first runner would surely establish a record time and perhaps the fourth runner would be faster than the first three and establish the second record time.

If the Nth runner sets the Rth record, it can be proved that the Rth root of N will be an approximation to e, and this approximation approaches e more and more closely as N increases without bound.

Another way of saying this is that if we permute a set of numbers randomly and compute the min by the standard procedure, then its value will change roughly ln n times. Timothy Chan made use of this fact in an elegant way to replace parametric search by a cheaper randomized test for many geometric problems.

The fourth example is a variant of the first: however, he alludes (possibly) to another famous homework problem, the secretary problem, in his conclusions. Here, the probability of choosing the best secretary for the job is 1/e, and this is in fact optimal (over all online algorithms that make irrevocable decisions). Considering there is already a movie called 'The Secretary', you'd think this would be a good candidate :)

As an aside, the derangement problem has also been referred to as The Drunken Secretary Problem.

If only all mathematical questions were "this complex"

Seen on CNET:

A billboard placed this week in the heart of Silicon Valley posed a complex mathematical question that most commuters on Highway 101 would need Google to crack.

So that explains why we haven't solved the burning mathematical questions of today; we didn't use Google !!

Click below to earn your $1000,000 prizes:
1. P vs NP
2. The Hodge Conjecture

For the curious, this is the "complex mathematical question":

In a kind of geek jeopardy, the billboard read:"{first 10-digit prime found in consecutive digits e}.com." The answer, 7427466391.com, would lead a puzzle-sleuth to a Web page with yet another equation to solve, with still no sign the game was hosted by Google.

Mastering that equation would lead someone to a page on Google Labs, the company's research and development department, which reads: "One thing we learned while building Google is that it's easier to find what you're looking for if it comes looking for you. What we're looking for are the best engineers in the world. And here you are.


Showing a stunning mastery of stereotypes, CNET manages to conflate eggheads, mathematicians, geeks, engineers in one horrible mish-mash.

The Importance of...: Introducing Hatch's Hit List

I try to stay out of politics, but this is just ridiculous:

The Senate is trying to pass a bill called the INDUCE Act (Inducement of Infringement of Copyright) that is as ridiculous as it sounds: one example of "inducing" infringement could be an iPod, because it encourages the use of P2P networks.

Ernest Miller has a very funny fisking of the act at corante.com. He is also maintaining a
list of devices that could become illegal under the act.

Today's burning question

From the latest issue of the Communications of the ACM:

HAS THE INTERNET BECOME INDISPENSABLE ?

In future issues:
1. DOS vs SYSTEM V: Pros and Cons.
2. Gopher: a new method for data transfer...
3. Special IBM Issue: Does the world need more than 5 computers ?

Sigh...

A dog and pony show...

Freeman Dyson has a review of Brian Greene's new book 'The Fabric of the Cosmos' in the New York Review of Books. The review provides a contrarian view on the viability of string theory, and an interesting history of the evolution of quantum physics from a revolutionary vs conservative perspective.

I found the following passage rather astounding:

Three years ago, in January 2001, I was invited to the World Economic Forum in Davos, Switzerland. Brian Greene was also invited, and we were asked to hold a public debate on the question "When will we know it all?" In other words, when will the last big problems of science be solved? The audience consisted mainly of industrial and political tycoons. Our debate was intended to entertain the tycoons, not to give them a serious scientific education. To make it more amusing, Greene was asked to take an extreme position saying "Soon," and I was asked to take an extreme position saying "Never."


Doesn't it seem sad that eminent scientists are brought out for a dog-and-pony-show in front of industrialists ? I know that "voices of reason" will argue that this is a good way to spread the Word among movers and shakers, but like this ?

---

A related article in Slate (where I found this review) also talks about the role of beauty and aesthetics in guiding (or misguiding) scientists.

SODA update

490 papers in: roughly 10% over last year (450), but then the committee is 10% larger as well :) no breakdown as yet of short vs long.

it's going to be a long summer...

SODA 2005

well the SODA submission deadline has passed (congratulations Jeff), and we have a record number of submissions this year (again). I will now go underground, to see daylight in a few months...

Apple, Wired and FOCS 2004.

Jeff Erickson snarks about Apple's discovery of the wonders of searching as-opposed-to sorting. Just to demonstrate that our community is on the cutting edge of technology trends, I present to you, hot off the presses, from the FOCS 2004 accepted papers list:

No Sorting? Better Searching!
Gianni Franceschini and Roberto Grossi

No paper link yet, alas...

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.

More on loops and strings

Readers of this blog will recognize my unhealthy fascination with loop quantum gravity and string theory. In my browsings of arxiv.org, I discovered a section of the physics area on popular writings in physics (what a concept: why can't we do this in theory CS too?). There's a nice article there by Rüdiger Vaas called 'The Duel: Strings Meet Loops' that explains the conflicts between the two approaches to unifying quantum physics and general relativity.

A related article is a Socratic dialogue between a fictitious professor and student on the pros and cons of string theory and loops. Bear in mind that this was written by Carlo Rovelli, one of the fathers of loop quantum gravity, so it is may be somewhat biased :)

And for those of you who say 'Bah ! Humbug ! Why should I care about such nonsense', I say 'Don't you want to understand John Baez's talk at SODA ?'

Automaton Simulator

Someone emailed me, asking if I knew of any packages that simulated various kinds of automata for visualizing their behaviour. I did some sniffing around, and found this package.

It simulates DFAs, NFAs, DPDAs, and Turing machines. From the interface, it doesn't appear to be that useful for large scale automaton construction, but is easy to play with interactively. Runs in Java.

Blog Page Update

I now have a (long overdue) collection of links to what I call "theory blogs", which I loosely define as pages with RSS feeds that are primarily theory-CS related. It's on the right side of the page, below my user profile. If there are other links I have missed, feel free to inform me (I won't guarantee I'll add them in though :) )

STOC 2004: A Report (Part II)

Chandra Chekuri continues his report on STOC 2004.

---

Todays topic is Jonathan Kelner's paper that won the best student paper at STOC a few days ago.

Many people know about the planar separator theorem: every planar graph has a vertex separator (a set of vertices whose deletion separates the graph into two pieces of roughly equal size) of size O(√n). For a bounded degree planar graph the same theorem also shows that there is a cut of sparsity O(1/√n). These results extend to graphs that can be embedded on a surface of genus g - vertex separators of size O(√(gn)) and cuts of sparsity O(√(g/n)) exist. Gilbert, Hutchinson, and Tarjan showed how to find the separator (cut) if the embedding of the graph in a genus g surface is given as part of the input. The catch is that given a graph G, the problem of finding the genus of the graph is NP-hard. It has been an open problem if one could find the separator and cut without finding an explicit embedding.

Another related question is the following. A popular graph partitioning technique used in practice is that of spectral partitioning. Spielman and Teng showed that this algorithm is also good in theory for planar graphs by demonstrating that the algorithm always yields a cut of ratio O(1/√n). They conjectured that the spectral method also works for higher genus graphs and thus pointed a way to overcome the problem of not knowing the genus explicitly.

Kelner's paper resolves the above two problems by proving that the spectral methods yields a cut of sparsity O(√(g/n)). The high level scheme is from Spielman and Teng. Kelner generalizes the scheme using some nice results from algebraic geometry. This result is beautiful because of the connection between combinatorial objects (graphs) and continuous mathematics (ed: Aha !! ).

Here is a brief description of the method. Spielman and Teng use the Koebe-Andreev-Thurston theorem which shows that planar graphs can be obtained as a contact graph of disjoint circles on the plane (or equivalently on the surface of a sphere in 3 dimensions) where there is an edge between two vertices u and v iff the circles corresponding to u and v touch tangentially.



Using this circle packing theorem, Spielman and Teng show via a simple but clever argument that the second eigenvalue of the Laplacian of the graph is O(1/n).

The result for genus g graphs would follow from the same approach if it can be shown that the graph can be obtained by the adjacency graph of circles touching on the sphere with the proviso that any point on the sphere is contained in at most O(g) circles - in other words we allow overlapping circles now. Unfortunately this cannot be done. To overcome this Kelner uses a theorem of He and Schramm that shows that genus g graphs can be obtained by touching circles where the circles are disjoint and embedded on a Riemannian surface of genus g. The technical part of the proof involves mapping the Riemannian surface back onto the sphere via conformal mappings (mappings that preserve angles). Difficulties arise because the original mapping to the Riemannian surface has branch points which are points of singularity and the mapping from the surface to the sphere does not maintain conformality at these branch points. The number of branch points is however limited to O(g) and by using a fine subdivision of the graph it is shown that these singularities do not play a major role.

The above description is at a very high level. The paper of Kelner is short - it uses several important known results from mathematics in a direct and effective way. It is impressive that he knows enough math to know and put them together - most people in the audience at STOC including myself have limited background in the continuous mathematics that is needed to do this proof. I wish that I had more classes in pure math ...(ed: Amen..)

References:
J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan. A separator theorem for graphs of bounded genus. J. Algorithms, 5:391-407, 1984.

Blogging etiquette

Most blogs, even today, are essentially online diaries; in fact the proliferation of blogs is directly due to this, since anyone can write a diary, even if not anyone can create web pages. However, more and more, one finds specialized "topic" blogs: political blogs being the vast majority, but also for topics like music, photography, the media, and even academic disciplines like economics, philosophy, and of course computer science.

As I write entries, I am conscious of the fact that my posts are a form of public announcement, and as such should be governed by some of the rules of normal academic public discourse. When I chat with people at conferences about problems and results, I have to be careful in what I say about these conversations, in the same way that I would be careful in one-on-one discussions. However, it seems to me that if I hear about a new result, and the result is not confidential, telling a colleague at lunch is still different to posting it on a blog, mainly because of the illusion that I can control the rate of dissemination of information. Moreover, as with normal conversations, I wouldn't want people to think that everything they told me could end up as a blog entry at some point.

A discussion on these lines has been going on in some of the philosophy blogs. I think this kind of discussion will probably happen more and more as more disciplines turn to blogs as a means for information dissemination and general discussion.

Geometry Junkyard RSS feed.

Start your aggregators ! David Eppstein's Geometry Junkyard page, (that I have mentioned in the past), now has its own RSS feed.

From the "NP != Non-Polynomial" department...

Was browsing some science news, and came upon this tidbit (emphasis added) in a PR release for a SIGGRAPH paper on mesh simplification:

Computer scientists have struggled with the problem of finding an optimal mix of large and small elements for years. In 1998, theoreticians proved that the problem was ''NP hard'' -- that no general solution exists that can be solved by a computer in finite length of time.

Sigh...

Later on, the article goes on to say:

'This is not a hack,'' says another expert, in the field [.. snip ..], using the term for a makeshift, unsystematic improvisation. ''It has a strong formal basis. You can make up extreme cases that will trick it, but for ordinary shapes, it works remarkably well.''

That's funny. Strong formal basis, but has extreme cases that can trick it ? If it sounds like one and smells like one....

STOC 2004: A Report

I am happy to introduce my very first guestblogger, Chandra Chekuri from Bell Labs. Chandra was recently at the ACM Symposium on the Theory of Computing (STOC) in Chicago, and has this report from the conference:

---

This year's STOC was in Chicago as most of the readers of this blog already know. It was the first time in Chicago for me. The hotel was in downtown right across from Grant Park near Lake Michigan. I went early on Saturday and had a chance to walk around and check out the Blues Festival in the park and walked the Magnificient Mile. Didn't have much time to do anything else touristy but had a very positive impression of the city. Maybe I should also visit during the winter to have a balanced view!

I felt that the papers in this STOC were particularly good. In addition to the usual breadth of topics, several papers in each topic were quite interesting. The two best award papers and the two best student papers were very well received.

Best Papers:
* Multilinear Formulas for Permanent and Determinant are of Super-Polynomial Size, by Ran Raz.
* Expander Flows, Geometric Embeddings and Geometric Partitioning, by Sanjeev Arora, Satish Rao, and Umesh Vazirani.

Best student papers:
* Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus, by Jonathan Kelner
* Lower bounds for local search by Quantum Arguments, by Scott Aaronson.


Interestingly there was one algorithms paper and one lower bounds paper in each category. Algorithmic game theory, quantum algorithms/complexity, and sub-linear time algorithms (including property testing) are still the relatively new topics along with the more established areas.

The invited talks reflected the invasion by the new areas. The most interesting of the invited talks was by Avi Wigderson who was asked by Laszlo Babai to comment on whether theory of computing is still a unified discipline given the many diverse sub-areas that are represented at STOC/FOCS. Avi gave a very nice talk on this. He showed how communication complexity is central to many of the topics. He also connected interactive proofs to many areas and finally concluded with what he thought was the glue between the areas. He promised to put up his slides on his web page soon and you can see them for yourself (ed: will add a link when it is available link). One of the glues that he mentioned are people like Les Valiant who have contributed deeply to many different areas.

Most of the Business meeting was taken up by the discussion on moving the STOC special issue from JCSS to other journals. You can read more about this on Lance Fortnow's and Jeff Erickson's blogs. I am all for moving away from for-profit journals (especially Elsevier and Kluwer) to either society journals (ACM, SIAM, IEEE, Math Programming, INFORMS etc) or free electronic journals. Laszlo Babai very recently started a new free electronic journal ToC (Theory of Computing). With several very highly respected journals such as JACM and SICOMP available as society journals, will authors send their good papers to ToC? Or will this journal turn out to be like the Chicago Journal of TCS that was started by Babai many years ago and failed to catch on? I think times have changed and there is a higher probability for ToC to be successful. One thing that did bother me was that Babai chose to have most of the STOC'04 committee (of which he was the chair) as editors. The STOC'04 committee is filled with many fantastic young researchers, however some of the comments that Babai made and the way he went about choosing the editors makes one feel that ToC is his own show. In my opinion a respected journal should have a certain reputation that is independent from the editor-in-chief even though the editor-in-chief is well known and respected through out the community. I wish the best for ToC and I hope the editors lead the way in making it a success.

STOC 2005 is in Baltimore and there was a bid from U. Washington faculty Paul Beam and Anna Karlin (delivered by Venkat Guruswami) to host STOC 2006 in Seattle. Vladen Koltun compared the registration fees and hotel rates at STOC with those of SoCG and was wondering why we don't make more of an effort to make the whole thing cheaper. This issue keeps coming up but people ignore it - my take is that the people who care about it the most are not present at the business meeting! Another potential reason is that we have several conferences (at least three major ones, STOC/FOCS/SODA) each year and it is difficulty to find volunteers to make all this work out cheaply. That brings up the topic of the next conference, FOCS 2004, to be held in Rome, Italy. The accepted papers list will be out soon, June 25th according to the call for papers.

Another post will detail some of the papers and ideas that I liked the most at STOC.

---

Successful ideas...

In science, successful ideas are those that are pervasive and invasive, are invitingly elegant and methodical, are open to extensio9ns and variants, andc apture and objective necessity, ansswer a widespread but diffuse sense of dissatisfaction in the scientific community


Christos Papadimitriou, in NP-Completeness: A Retrospective (via the P-NP page)

geeks and fonts...

A couple of years ago, when Agarwal, Kayal and Saxena announced that PRIMES was in P, an entry was posted on slashdot and much of the early discussion centered not on the proof itself, but on how to convert PS to PDF, and the relative merits thereof (this was prompted by the fact that the authors had linked a PS file online).

A few days ago, Lance Fortnow posted a note about one of his favorite theorems in complexity, a result by Trevisan connecting extractors and pseudo-random number generators. He got 9 comments; a fair number. All of them were devoted to the technical details of PS to PDF conversions !!

I am as happy as the next person to jump into a lecture on using type1 fonts with latex, but....

Don Quixote enterprise ?

Via /., news of the first quantum computer simulation tool. However, what I find most interesting is this excerpt (emphasis mine):

Classical simulation of quantum processes seams like a Don Quixote enterprise - this is well known. But imagine, you may test all the quantum algorithms you have in mind now - not tomorrow when everybody is able to press them in hardware. Let's discover the quantum ways by simulation now - to reach the world of Quantum Computing today.

Something must have been lost in translation...

Losing a Ph.D for discredited papers...

From today's NYT:

A German university has revoked the doctoral degree of the former Bell Labs scientist who claimed a series of research breakthroughs, then was fired two years ago when it was discovered that he had manipulated data and fabricated results.

The physicist, J. Hendrik Schön, 33, did not commit misconduct in his doctoral research at the University of Konstanz, an investigation there found last year. But on Friday, the university said it had a legal right to rescind a degree when the recipient behaved "unworthily" of it.

I have mixed feelings about this: on the one hand it appears that he did fabricate data at Bell Labs. However, to rescind his Ph.D seems arbitrary, even if the university "had a legal right" to rescind it.

RSS for papers

The time has come to have RSS feeds for subjects at a much finer granularity than what arxiv.org provides. Suppose I want to track papers on art gallery problems. Today it is not hard to imagine a spider that crawls well known sites like SoCG conf pages/SODA web pages etc, finds paper titles, and determines what papers might be of relevance to an art gallery problem search. One could use Feedster right now for such a search, but searching over the entire web will generate a lot of junk (or nothing at all)

Seems like it would not be hard given current web technology....

SoCG: The Business Meeting

Read all about it here

SoCG: The Cruise

Last night our conference banquet was on a cruise boat that went up and down the Hudson and East River. It's a good way to see the less serious side of CG researchers. Bernard Chazelle is an accomplished guitarist, and during the cruise we had a number of solo pianists (jazz/classical) performing for our benefit.

Tverberg Points

Inspired by Algorithms for Center and Tverberg Points by Pankaj K. Agarwal, Micha Sharir, and Emo Welzl:

Usually, checking if a point satisfies property X is easier than finding a point that satisfies property X. Tverberg points are an example of a rather bizarre reversal of this situation.

Suppose I take a collection of points in the plane, and partition it into subsets cleverly so that the convex hulls of the subsets all intersect in at least one point. Such a point is called a Tverberg Point. It was shown by Tverberg that such a point always exists. However, the following problem has unknown complexity in three dimensions:

Given a point p and a set of points P, is p a Tverberg point of P

---

The Tverberg point is one among a family of nonparametric notions of "deep" points in a point set. Other notions are the centerpoint (a point that "sees" the maximum number of points no matter which direction it looks in), and the Radon point (a Tverberg point where you partition P into two pieces).

Problem 2: Coins...

Heard around the dinner table....

I am given n piles of coins, with the knowledge that the total number of coins is 1 + 2 + 3... + n. I take one coin from each pile, and make a new pile. If the i^th pile has i coins, this operation leaves all piles unchanged. Prove that no matter what starting configuration of coins in piles I start with, I always end up with this stable configuration.

Answer in a week, or thereabouts...

SoCG...Live !

Am at SoCG right now: will attempt to report on the activities as they happen...

Traditional dinner table conversation at conference dinners involves either gossip or tossing around of problems. Sometimes one even solves them ! I had mentioned the turnpike problem a while ago, and its variant, the "sum-turnpike" problem. Thanks to Vladlen Koltlun and Shankar Krishnan, there is now an efficient poly-time algorithm for the sum-turnpike problem.

Alan Turing: 50th Death Anniversary

Alan Turing died 50 years ago today. We often use the word genius lightly: for him, it is fitting...

---

Cryptonomicon is set partly in the Enigma period of WW II, and has many very accurate discussions of Turing machines and the halting problem. Turing is a character in the novel as well.

SODA 2005 invited speakers

Some of you may recall my musings on quantum gravity and the discrete nature of spacetime. I am delighted to note that at the upcoming Symposium on Discrete Algorithms, we will have an invited talk on loop quantum gravity by John Baez of UC Riverside.

Prof. Baez writes an occasional column called This Week's Finds in Mathematical Physics.

---

Micha Sharir and Uri Feige will also be speaking at SODA; two better speakers one will be hard-pressed to find...

FSTTCS Announcement

FSTTCS is the premier Indian conference on theory/algorithms/fundamental aspects of computer science. It's always in winter, so the weather is nice :), and this year it is in Chennai, in the south. The deadline for submission is coming up (Jun 21). More details are in the call for papers

Passwords as one-way functions

This is an interesting article: the premise is that a password should be something that is individualized, but not conscious:

In tests of the picture version, users went through a two-step process to get a set of user certificates, or unconscious passwords. Users were first shown a set of 100 to 200 pictures randomly selected from a database of 20,000 pictures. Pictures were organized in groups of 2 to 9 pictures with a common theme, and each user was certified on one picture from a given theme group. The user then practiced choosing certificate images from entire theme groups.

Later, in lieu of passwords, users identified most of a short series of certificate images. To guard against eavesdropping, each certificate picture is only used once, and the user retrains when they run low.

Subjects were able to recognize previously seen pictures with better than 90 percent accuracy for up to three months. According to the researchers' calculations, the chances that a user who guesses correctly four times in a row is an imposter is less than 1,000th of one percent.

Our ranks are growing :)

Just discovered Jeff Erickson's not-new blog (he has posts dating back to Sep 2003, but most activity appears to be recent). Congratulations on getting tenure !

How did I discover it ? Sitemeter: a great place to satisfy one's inner narcissist.

419 scams and world affairs

I have decided that instead of actually trying to read newspapers to figure out what is going on in the world, I will just monitor my 419 scam mail. So far in the past few years, I have got 419 scam variants from major hotspots in the world:

• Nigeria of course
  
• Liberia
  
• Sierra Leone
  
• Haiti
  
• And now Zimbabwe.
  

I am somewhat disappointed to have not received anything from Sudan, and even more surprised that nothing has come from Iraq. I am expecting some mail from the Congo in the next few days...

Upcoming events: sausage and soda

• The Symposium on Computational Geometry will be in NYC from Jun 9-11.
  
• The ACM Symposium on the Theory of Computing (one of the main theory conferences) will be in Chicago from Jun 13-15, where you can also visit the original theory blogger :)
  
• The paper submission deadline for the Symposium on Discrete Algorithms (SODA) is approaching (July 5). Consider this your first warning...
  

Math meets Hollywood

(Via slashdot...)
A little-known fact about "Futurama", FOX's cancelled cartoon sitcom about a pizza delivery boy stuck in the future, is that many of the writers had advanced degrees in math or related fields. Read this article for more info.

A personal connection is to Jeff Westbrook, one of the writers. He used to be at AT&T Labs, and is the only theoretician I know* who writes scripts for Hollywood. We even wrote a paper together, so I guess my Hollywood number is 1 !

---

* Len Adleman consulted on 'A Beautiful Mind' and I believe even "decorated" a blackboard for a scene in the movie.

Princeton math oral exams

Via Michael Nielsen, the Princeton Math Department Graduate Student Guide to Generals (their oral exams).

I found the following excerpt hilarious: this is the start of an orals transcript, with a commitee consisting of John Conway, Andrew Wiles, and Charles Fefferman (speakers are marked with lastname-firstletter:

C: "So who is the chair of this committee?"
F (scratching head): "I think it's one of you two."
W: "Is it me?"
C: "I don't know... Perhaps it's me."
W: "How will this be determined?"
F: "Does it matter??"
C: "Let me find out from the office downstairs."

(Just as he was about to leave, I informed Prof. Conway he was chair.
A similar discussion then ensued as to what my special topics were!!
It was quite entertaining. But at last, we were all ready to begin.)

C: "So who wants to ask the first question?"

(Everyone kept looking at Conway. (He was chair after all.) )

C: "Hey, why is everyone looking at me?!?"

(Another entertaining dispute followed.
Finally, Prof. Fefferman agreed to start.)

The Strong Law of Truly Misquoted Mathematics

On the one hand it is nice when technical terms from the world of math/CS sneak into common usage. On the other hand it can be rather grating. If I had a dime for every time someone used "exponential growth" to mean "something big", I could probably buy a single share of Google stock...

This excerpt from a Slate article on cell phone usage is another example:

...the cell-phone growth projections are based on premises that are more redolent of 1990s-era techno-enthusiasm than the current decade's putative realism. Some savvy observers of the telecom world detect the beginnings of a bubble. "At some point, we're going to run into the law of large numbers and it's going to be a nasty setup," said Cody Willard, general partner at CL Willard Capital and a columnist for TheStreet.com. "I just don't think we're quite there yet."

I have to ask: exactly what law is Mr. Willard scared of running into ? Let's consider the options:

The Weak Law of Large numbers:
The probability that the sum of i.i.d variables over the same distribution differs from the mean is arbitrarily small.


or even:
The Strong Law of Large NumbersNot only is the probability of deviation small, the actual deviation of the sum from the mean is arbitrarily small.


Somehow I don't see how either of these fit into an analysis of the global cell phone market. But wait!, there are some more intriguing possibilities.

The Frivolous Theorem Of ArithmeticAlmost all natural numbers are really large

Possible, but Mr. Willard did after all quote a law of large numbers. We should grant him at least some degree of precision in his statements.

Strong Law of Small NumbersThere aren't enough small numbers to meet the many demands made of them..

This seems somewhat more plausible: after all, soon we might run out of small numbers to describe cell phone usage, at which point the market might collapse.

But I think the real answer lies in a deeper analysis of his prognostication. Note if you will the use of the phrase 'nasty setup'. This clearly indicates his invocation of:

The Law of Truly Large NumbersWith a large enough sample, any outrageous thing is likely to happen

This indeed settles it. As cell phone usage increases, something bad is going to happen. Now we know why they get paid the big bucks in Wall Street.

Floating point arithmetic is not associative...

Especially in computational geometry, robust calculations are of paramount importance because of the algebraic calculations at the heart of most geometric algorithms, and the catastrophic effects of precision errors - you lose incidences, points disappear, algorithms crash, the universe slips into a black hole....

An old article by David Goldberg talks of the perils of floating point computations. Worth reading...
What Every Computer Scientist Should Know about Floating Point Arithmetic

Page Numbering Planar Graphs

In honor of the recently passed Graph Drawing deadline....

Suppose we place all the vertices of a graph on the spine of a book, and partition the edge set into sets such that each set can be drawn on a single page without crossings. The page number of a graph is the minimum number of pages required to draw a graph in this way. Clearly an outerplanar graph has page number 1.

A well known result by Yannakakis states that any planar graph can be drawn with page number 4, and this is necessary. A very interesting related result by Lenwood Heath in SODA 1991 states that the edges of a planar graph can be partitioned into two parts, each inducing an outer planar graph.

It is NP-hard to determine whether a given planar graph has page number 2 or not.