Open Problems

John Langford points us to the COLT 2005 open problems CFP. The COLT open problems appear in the proceedings, a feature that distinguishes them from (for example) the SoCG open problems sessions, which are more informal.

It's worth pointing out that there are open problems, and there are open problems. Anyone who writes a paper can come up with open problems; these are merely the questions you didn't get time to address, and are either too bored or too unmotivated to work on yourself. These are not really that interesting. Good open problems are not necessarily easy, and are not too hard either (P?=NP is an open problem in the true sense of the word, but is not particularly useful as a proposal for this kind of forum).

A good open problem thus has some intrigue, has some surprise, and should tantalize the reader; the solution should appear to be just over the horizon, rather than indistinctly fading away. Any thoughts on good candidates ?

New (to me) book on randomization

As the networks are prone to say during the summer, "If you haven't seen it, it's new to you".

Cambridge University Press has cornered the market on randomized algorithms. After publishing the truly excellent Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan (ed: wasn't Rajeev your advisor ? me: that has nothing, nothing at all to do with it), they have now published Probability and Computing by Michael Mitzenmacher and Eli Upfal. I caught a brief look at the book the other day, and it seems to have a slightly higher focus on probabilistic tools and techniques and possibly a slightly lesser focus on randomized algorithms, but I could be wrong here.

All in all, looks like a great book to have; it's definitely on my list of books-to-get.

Blogging from FSU

where I am visiting Piyush Kumar and giving a talk. On the way into town, I saw this amusing billboard:

The best vitamin for Christians -- B1

The latest issue of Salon (you can read the article if you sit thru an ad) reviews two books on Gödel that were mentioned here earlier: Rebecca Goldstein's Incompleteness and Palle Yourgrau's World Without Time...

New Abel Prize(s)

The 2005 Abel Prize has been awarded to Peter Lax

for his groundbreaking contributions to the theory and application of partial differential equations and to the computation of their solutions

An interesting section from the long popularized explanation of his work:

Lax considers himself both a pure and an applied mathematician. His advice to young mathematicians is summarized in 'I heartily recommend that all youngmathematicians try their skill in some branch of applied mathematics. It is a gold mine of deep problems whose solutions await conceptual as well as technical breakthroughs. It displays an enormous variety, to suit every style; it gives mathematicians a chance to be part of the larger scientific and technological enterprise. Good hunting!'

I really like the fact that the Abel Prize committee supplies these popular explanations of the work of the awardees. The ACM has a detailed press release for its awardees, but a popular exposition of the work would be a great addition.

In other news, the Abel Prize Committee is funding a new prize called the Ramanujan award. From the news blurb on the Abel Prize site:

The Prize will be awarded annually to a researcher from a developing country less than 45 years of age at the time of the award, who has conducted outstanding research in a developing country. The first winner will be announced in 2005.

The award amount will be $10,000.

An interesting tidbit I heard at lunch: apparently Paul Wolfowitz (DoD under-secretary, World Bank chief nominee) is the son of a very well known information theorist and statistician. Jacob Wolfowitz wrote one of the classic books on coding theory.

Mmmm, ice cream

From the AIR:

There is, or at least was briefly, an ice cream flavor created in honor of physicist Richard Feynman. Devised by Toscanini's Ice Cream, it was inspired by the story that earlier inspired the name of the classic book Surely You're Joking, Mr. Feynman!

On that note,

The Newton: comforting and familiar, with a rich chocolate sauce. But it ends, and you are sad.

The Heisenberg: Everytime you think you can nail it down, it escapes you.

The Einstein: Mindbending, dude !

The Godel: I could describe the flavor, but I need another icecream...

Clickety click

Ernie points out another knitting mathematician. I have to say that I never thought there could be so many blogs about knitting (see Andrea's blogroll).

Numb3rs Review: "Counterfeit Reality"

...also to be referred as the 'projective Daubechies' episode.

After a brief hiatus, Numb3rs is back, with another kidnapping episode. As usual, spoilers abound..

Plot Summary: Series of store robberies and two murdered teens lead to a gang of counterfeiters, who kidnapped an artist and forced her into doing note sketches for them. If Don, Charlie, and the rest of their merry men can't find her in time, it's lights out !

This is a good "character development episode", with backstory about Don's love life being revealed. I guess the producers didn't have the courage to go all CSI/Law and Order/Law and Order SVU/Law and Order CI/Law and Order WillYouStopWithAllTheSpinoffs on us and dispense with the characters' backgrounds. Pity...(Yes, I know this is a frequent rant, but ...)

As I always say, if you want character development, don't read this blog ! My heart races when they say 'wavelets', which in fact they did. Local cop refers to a 'video-enhancement algorithm' that Charlie has developed, and I was wondering when wavelets would come up. As it turns out, there are scenes with pictures of what appear to be wavelet basis functions (though they didn't look like Haar wavelets at least).

I have now seen 7 episodes of Numb3rs, and in these seven episodes, Charlie uses statistical modelling, attacks P vs NP, does cryptography, understands advanced number theory, knows civil engineering, is a mean hacker and consults on string theory problems. Not to mention having tenure. So my question is: What could Charlie's field of specialization possibly be ? I mean, what on earth could he have written a thesis in ? The 'professor of applied math' part could cover the modelling and the civil engineering, but the rest ? And does he not know that at certain universities, math department professors wrinkle their noses when a professor of 'applied math' walks by ? I have certain departments in mind, but I'm not naming names ;)

Best/Most inane line of the episode: Charlie's grad student (who appears to be a wavelet expert as well as a combinatoricist), says 'In combinatorics, sometimes we vary the angle of attack'.

In algorithms, sometimes we eat the sugared candy...

• Next episode review
• Previous episode review
  

Tags: numb3rs, reviews

Gödel, Original Sin, and Sausage...

Jordan Ellenberg (he of the countably infinite reading list) has a nice Slate review of a new book about Gödel's theorem (Incompleteness, by Rebecca Goldstein). He makes the important point that the incompleteness theorem did not have the cataclysmic effect on modern mathematics that non-mathematicans were under the impression it does. All it does is destroy a

"Communist takeover of mathematics" in which individuality and intuition would be subjugated, for the common good, to logical rules.

This tidbit is funny.

Yet, Gödel is routinely deployed by people with antirationalist agendas as a stick to whack any offending piece of science that happens by. A typical recent article, "Why Evolutionary Theories Are Unbelievable," claims, "Basically, Gödel's theorems prove the Doctrine of Original Sin, the need for the sacrament of penance, and that there is a future eternity."

To that, I have only one response: the Sacred Sausage Invocation. Amen.

Tags: Gödel

The answer...

Here's the answer to yesterday's question:

It becomes clear fairly quickly once you start playing with examples that the thing to do is create some kind of bipartite graph, where the left side is the "bad answer" and the right side is the "good answer". Since picking all the vertices on a side is a valid cover, and you have to pick all of at least one side, it is clear that the smaller side is the optimal solution. So the goal is to make an example with more nodes on the left than on the right, and force the algorithm to pick something from the left each time (if you could direct the edges, to force picking from one side, then it would be easier, but then you've just created a SET COVER instance).

The catch is that just by averaging, if the left side has more nodes than the right, then it seems that the nodes on the right should have higher degree and should be picked first. How does one avoid this ? This is where the "trick" is used. Gronwall's theorem bounds the sum of the number of divisors of n. Roughly, the sum of the divisors of n behaves like n ln ln n as n goes to infinity. So here's the construction:

Let 1 = d₁ < d₂ < ... < d_k = n be the divisors of n. Create n nodes on the right side. For each i, create d_i nodes on the left side. Of these d_i nodes, connect the first to the first n/d_i nodes on the right, and the second to the next n/d_i, and so on. There are (asymptotically) n ln ln n nodes on the left side. The maximum degree on the left side is n/d₁ (= d_k!), and the maximum degree on the right side is k, since each node on the right connects to only one node in each group on the left. It is easy to check that d_k is always greater than k, so the algorithm always picks the first node from the left side. Repeat, use induction, clean your hands, and voila! you end up picking n ln ln n nodes instead of n: a ln ln n approximation gap.

This is not the best solution possible. With a bit more work based on this solution alone you can go up to c ln n. I'll leave that as an exercise ;).

Tags: VertexCover, algorithms, numbertheory

An old question, a new approach

In a graph, say that a vertex v covers an edge e if v is adjacent to e. VERTEX COVER, one of the original 6 NP-Complete problems, asks if you can find a set of vertices of minimum size that cover all edges in the graph (for purists, the decision problem is to check, for a given G, and value B, if there is a vertex cover of size at most B).

One of the most obvious attacks on this problem is to use a greedy approach. Pick the vertex of highest degree, and remove all the adjacent edges. Repeat this till all edges have been removed. Clearly the set of vertices picked form a cover. But how good is this ?

The answer is, 'not very good', and one of the first homework problems in a graduate class on algorithms is to show why, by coming up with a counter-example. There are some standard (but not trivial) constructions that can be used, and you can amuse yourself with thinking about this.

However, this is not the point of this post. Amit Chakrabarti is teaching an graduate algorithms class up in Dartmouth, and Khanh Do Ba, a junior taking the class, came up with an ingenious solution that I at least had not heard of before. I will not tell you the solution just yet, but I will give you the hint that Amit gave me when he told me about it: the student used Gronwall's Theorem.

Happy pondering. Tune in tomorrow for the answer.

Tags: VertexCover, algorithms, numbertheory

Sp311ing

No Numb3rs review this week because my TiVo flaked did its job, but in its stead, I present to you,

Sp311ing

Courtesy of the most bizarre blog on the web: Fafblog !

“Oh no, a crime!”
“Maybe we can solve it – with spelling!”
“Applesauce. A-P-P-L-E-S-A-U-C-E. Applesauce.”

“So, you are the American dog who spells for the Great Satan, eh? Well, now you will spell for the jihad!”
“Never!”

“We’ll never disarm this bomb in time! It’s impossible”
“You can’t spell ‘impossible’ without ‘possible’! Let’s go, team!”
“Australopithecine. A-U-S-T-R-A…”

Tags: Numb3rs

Alpher, Bethe, Gamow

Hans Bethe, Nobel laureate and giant of theoretical physics, died today. I will leave commentary about his life and work to the physicists, but remember one fairly well-known anecdote regarding him and George Gamow.

From Quark Soup:

Here is Gamow's own account, from his popular science book _The Creation of the Universe_:

"The results of these calculations were first announced in a letter to _The Physical Review_, April 1, 1948. This was signed Alpher, Bethe, and Gamow, and is often referred to as the 'alphabetical article.' It seemed unfair to the Greek alphabet to have the article signed by Alpher and Gamow only, and so the name of Dr. Hans A. Bethe (_in absentia_) was inserted in preparing the manuscript for print. Dr. Bethe, who received a copy of the manuscript, did not object, and, as a matter of fact, was quite helpful in subsequent discussions. There was, however, a rumor that later, when the alpha, beta, gamma theory went temporarily on the rocks, Dr. Bethe seriously considered changing his name to Zacharias.

"The close fit of the calculated curve and the observed abundances is shown in Fig. 15, which represents the results of later calculations carried out on the electronic computer of the National Bureau of Standards by Ralph Alpher and R. C. Herman (who stubbornly refuses to change his name to Delter.)"

Tags: Bethe

First we wrestle, then we ooze

In which the academic, fresh from a bout of rabid-squirrel-wrestling, oozes off into the primordial swamp of knowledge:

How is the modern professoriate like a slime mold? Consider this description from Steven Johnson:

[T]hey solve problems by drawing on masses of relatively stupid elements, rather than a single, intelligent "executive branch." They are bottom-up systems, not top-down. They get their smarts from below. In a more technical language, they are complex adaptive systems that display emergent behavior. [Emergence: Scribner, 2001]

Read the article: it's interesting.

(HT: Three-Toed Sloth)

Tags: academe

updating web pages..

Seen on a mailing list I subscribe to:

for many academics, the practice of keeping
one's web page up to date with both their long term and short
term research interests is something that gets prioritized just
below rabid-squirrel-wrestling.

And just for the heck of it:
Tags: rabid, squirrel, wrestling

Wake up, ACM.

The ACM is the mothership of all CS endeavours. It runs most of our conferences, has the excellent digital library, and dishes out some of the most prestigious awards in the field. But those of us who use the ACM's services on a regular basis know that its affinity for technology is, how shall I say this politely, somewhat on the weaker side. Try buying anything from the ACM store online and you'll see what I mean.

Current case in point: RSS. A recent issue of CACM covered the blogosphere in great detail, so clearly the ACM is familar with the notion of RSS. However, there are still no RSS feeds for tables of contents for journals. ACM instead provides a TOCalert email service, something that was in vogue quite some years ago.

There is now a standard for RSS feeds from journals. Nature Publishing Group, that publishes most of the Nature:XX journals, provides RSS feeds for all of its journals. The IEEE provides feeds for its journals (though not in the PRISM standard format). The ArXiv provides feeds on all subject categories.Why can't the ACM ?

The reason I bring this up has to do with CiteULike. One of the things you can do with CiteULike is track RSS feeds of many journals archived there. There are numerous CS journals, including many in the area of machine learning. However, since the ACM doesn't provide RSS feeds, these can't be tracked inside CiteULike.

Even if ACM can't provide feeds in a standard format, any feed would be useful. Maybe some of you readers know people who know people who know people.... inside ACM ?

On Grace Murray Hopper

When Karen was in high school, in a special school for the sciences, Rear Admiral Grace Murray Hopper came to speak with them:

Her messages to us:

If you want to get something done, do it first. Apologize (if apologies are necessary) later.

Don't let anyone tell you you can't succeed, especially if you are a woman.

She gave us lengths of wire cut to the distance light travels in a nanosecond, and handed out pepper grain sized wires that she called picoseconds for the same reason.

Her talk was less about doing computer science and more about having the will to succeed against all odds. Very inspirational.

CS Awards

This year's Kanellakis prize goes to Robert Schapire and Yoav Freund for their work on boosting. They had previously won the Gödel Prize in 2003 for their paper "A Decision Theoretic Generalization of On-Line Learning and an Application to Boosting".

Jennifer Rexford has won the Grace Murray Hopper Award.

With a mixture of pride and regret I point out that all three are AT&T Labs alumni.

If you want to know more about what these awards are given for, visit the ACM Awards page. The Kanellakis prize commemorates an achievement that spans theory and practice (has theoretical heft and has shown to be effective in practice). The Gödel Prize acknowledges a single journal paper that has had great impact in the last seven years. The Grace Murry Hopper Award is a 'young achiever' award, given to researchers below the age of 35. The Turing Award, of course, is the computer science "Nobel" for lifetime achievement. The Knuth prize is the theory lifetime achievement award.

Gödel, Turing and Knuth need no introduction. Paris Kanellakis was a professor at Brown who died tragically in a plane crash in 1995. He was one of the pioneers in database theory. Grace Murray Hopper was one of the first programmers of modern computers, the first compiler designer, and is attributed with the coining of the term 'bug' to describe an error in a program.

Now that's the way to say it:

A university is not a Walmart

-- Daniel Lemire.