Arch-blogging

The Utah blogging juggernaut (random fact: juggernaut is a corruption of Jagannath, from the festival of Lord Jagannath in Orissa in which people would throw themselves in front of giant chariot carrying an image of the god) chugs on. Our newest member is Rajeev Balasubramonian, who might very well be the first computer architecture blogger. The blog itself is intended as a group blog of the Utah architecture group, whose cleverly-chosen logo is the Delicate Arch (get it ? Arch?). Read the blog manifesto here.

Idle thought: which academic department has the highest ratio of bloggers/faculty ? Or blogs/faculty ?

Quick note

(am posting this from 37000 ft. isn't technology cool ?)

The clustering series will be on hiatus for a few days while I wrap up some more pressing deadlines. It will restart two weeks from now.

Congratulations to Adam Smith and Sean Hallgren on getting a PECASE award. See what creating a new blog can do !

"Bloggers", the media and science reporting.

Sometimes I read an article that I just cannot understand. The words make sense, and I can understand the logical flow, but the entire premise just escapes me. Consider the following exhibit: an article in Nature News on the "problem" of blogging from a conference. A snippet from the article (which I recommend reading in its entirety):

By disseminating scientific results far beyond the lecture hall, blogging and social networking blurs the line between journalists and researchers. Scientists in competitive fields may be more reluctant to discuss new findings if they can be posted on the Internet within seconds.

and then later:

MacArthur's comprehensive postings were read by many scientists but they irked journalists attending the meeting. The meeting rules stated that reporters had to seek permission from speakers before publishing material on their work, rules that Cold Spring Harbor instituted in part because some journals, such as Nature, discourage scientists from talking to the press before their work is published. But those rules didn't apply to scientist-bloggers like MacArthur and, after he posted details from a few talks, reporters contacted Stewart for clarification on the policies. The complaint was a wake-up call: "For the first time, I became aware that people were blogging about the data at the meeting," Stewart says.

If I understand this correctly, the premise of the article is that blogging from a conference is bad because it

• "scoops" the poor journalists under embargo ?
  
• disseminates information faster than someone might like ?

to which my only response is "HUH " ? Isn't the whole point of a PUBLIC presentation to disseminate results to - you kn0w- THE PUBLIC ? and how on earth does it matter how fast this happens ? And although I feel for the journalists who agree to weird embargo rules by control-freak journals, why on earth should I, as a researcher who happens to blog from conferences, care about this ?

Sometimes I think the media needs to get over itself....

Blogroll alert, and some musings on community.

Noam Nisan has a new blog on algorithmic game theory. This is great stuff. I must add that I'm finding Dick Lipton's blog fascinating reading, not only for the heavy research content, but the great historical perspective he brings to a number of well known problems.

p.s (snark alert) It does seem unfortunate that computational geometry blogs (and data structures) don't appear to be recognized as part of the theoretical computer science blogosphere, but in a world where SODA is viewed as a conference not worth attending, I guess this is small potatoes. (end snark alert)

p.p.s From an organizational perspective, it doesn't matter terribly whether geometry papers get published exclusively in SoCG/SODA, appear in STOC/FOCS, etc. Similarly, although Luca is concerned about crypto forking off from STOC/FOCS, I don't think there's a real problem with people naturally aggregating around a common topic area in their own conference. I'm also not too caught up with "name wars" despite my snark above.

The problem is really along other dimensions: the tenure process (what is your field and who evaluates you/writes letters), and even more crucially, the funding process. For many years, geometry was funded from a separate sub program of CCF than the rest of theoryCS (at least theoryA). This was a good thing (more money) and a bad thing (CG was clubbed in with solid modelling, graphics, and symbolic methods).

Now of course geometry has been folded back into the larger Algorithmic Foundations umbrella, and here's where perceptions start to matter. If AF gets defined (de facto) as STOC/FOCS stuff, geometry proposals are going to get short shrift (also because they tend to have more application-oriented material as well). This would be true for any other area that has forked off into its own community.

I didn't submit to the theory program last December, and I don't know how panel deliberations are going, but I'm curious as to whether there's been any noticeable change ?

Blogroll update alert

My student John Moeller has started a new blog 'On Topology':

My interest in topology comes from two directions: first, it was the reason that I got started in math (and subsequently the topic that broke me), and second, I found out over the last year that topology plays a prominent role in several research areas of computer science. These applications to CS are what really got me interested in the topic again. Algebraic (or combinatorial) topology is useful in studying the structure of data like meshes and graphs. Differential geometry is applicable when your data lives in another space, or on something called a manifold, and you want to do the same kinds of things that you’re used to doing in regular, old-fashioned space. Ultimately, both have to do with geometry, albeit in a very general way. That’s why these topics interest me; I want to know how to better get at the essence of data, and much of the time you can do that geometrically.

He actually enjoys thinking about Cartan-Hadamard manifolds and representation theory, but I don't hold it against him :).

Women in Computing workshop, and a new blogger

Sorelle Friedler, UMD grad student in geometry, tireless staff volunteer at SoCG 2008, and former AT&T summer visitor, has a new blog. One of the first things she writes about is the Women in Theory workshop at Princeton that ran Jun 14-18. Add the feed, folks !

They're coming out of the woodwork !!

Well, maybe not, but it's getting harder and harder to keep track of all the TCS blogs out there. I just discovered that James Lee has a "trial blog" (a tlog ?) with some very interesting posts. Doing the P vs NC posts has made me jealous of all the wordpress.com folks and their nifty LaTeX embedded in the posts: I think I'll switch over at some point myself.

The pitfalls of being watched..

Noah Snyder over at Secret Blogging Seminar points out one of the unreported pitfalls of blogging: your colleagues know what you're doing ! More importantly, they know that you're not doing the work you're supposed to be doing with them !

This is particularly bad when someone's hounding me for a review, or a revision, or something else...

More math-blogging

Gil Kalai has a blog (at least for the next year) (HT 0xDE)

Interesting new blogspam method ....

When you've been writing a blog for a while, you'll discover what appear to be automated blogs that shamelessly steal your posts and repost them as new posts verbatim. I can only imagine that they do this to get high hits (and therefore advertising revenue) from Google, although why someone would take *my* posts for this purpose escapes me.

A new form of blog plagiarism combines the best of spam techniques with post copying, so as to evade the obvious duplicate detection methods. Consider the following examples:

The original post:

There's been a lot of grief over the reduction in price for iPhones only a few months after they were released. Wired magazine interviewed people who don't regret paying the higher price for the virtue of being an early adopter/arbiter-of-cool, and this comment caught my eye

The modified post (and no, I'm not going to link to it):

There's been a number of visibility at the decline master p scholomance for online in very couple weeks and we were released. Wired magazine interviewed people who don't regret paying a low frequency of the world as both an early riser and perhaps comment and the eye

The original post:

Suppose you're given a metric space (X, d) and a parameter k, and your goal is to find k "clusters" such that the sum of cluster costs is minimized. Here, the cost of a cluster is the sum (over all points in the cluster) of their distance to the cluster "center" (a designated point).

The modified post:

Lil romeo you're given a multidimensional space (X, d) and a parameter k, and a buff being use find k "clusters" such as lump- end of the effect is minimized. Here, lil romeo use 70million a target wikipedia, the sum of these items out the amount of the need codify the cluster "center" (a designated point).

And so on. What's more mysterious is that this isn't straight plagiarism: the post credits my post as the "source", although given the garbage that's generated, I'm not sure I want that "source" credit :).

Very mystifying...

While I wait for inspiration to strike..

I need to find all the napkins I scribble things on...

What a great idea ! PostSecret for the researcherati....

Popularizing computing

Brian Hayes writes for the American Scientist (and on his blog, bit-player), and in my mind is one of the best writers of popular material about computing. Every time I read something he's written, I learn something new, even if it's about a topic I'm familiar with. What's even more impressive is that he often focuses on the mathematical aspects of computing and finds interesting ways to explain them to his audience.

Two recent articles of his are exemplars:

1. Sorting out the genome, from September-October 2007. Here's a key extract:

Given two arrangements of a set of genes—say a b c d e f g and f e b a g c d—how do you determine what sequence of reversals produced the transformation? This example has a three-step solution, which you can probably find in a few minutes with pencil and paper. For larger genomes and longer chains of reversals, however, trial-and-error methods soon falter. Is there an efficient algorithm for identifying a sequence of reversals that converts one permutation into another?

The genetic reversal problem lies at the intersection of biology, mathematics and computer science. For some time, the prospects for finding a simple and efficient solution seemed dim, even with the most powerful tools of all three disciplines. But the story has a happy ending. A little more than a decade ago, computing gene reversals was still a subtle research problem; now it can be done with such ease that it's a matter of routine technology. If you need to know the "reversal distance" between two genomes, you can go to a Web site and get the answer in seconds.

The article proceeds to lay out the entire history of sorting with reversals, pancake sorting, and related problems. It's a great case study for the study of algorithms in an application domain: how to model a problem, come up with algoritms, discover that the model doesn't quite capture what you want, rethink the model, come up with more algorithms, and so on. It touches on dynamic programming, greedy algorithms, NP-hardness, and approximations. I liked it so much I'll be devoting a lecture in my algorithms class to it, to illustrate how algorithms research works "in the real world".

2. Conquering divide, bit-player, October 9th, 2007.
The "hook" for this article is is Eric Allender's review article on the true complexity of division (short summary: Division is complete for DLOGTIME-uniform TC^0), which is a must-read in its own right. What Hayes discusses in his article is the reason to even ask this question, starting with the general lack of symmetry between grade-school methods for multiplication and division. I found this particularly insightful:

Why is division so hard?

At times I feel this is a dumb question, and that the universe doesn’t owe us an answer to such questions. Some things are just harder than others; that’s the way the world works. We can count ourselves lucky that multiplication has a polynomial-time algorithm; we have no right to expect that our luck will hold when we turn to division.

But then I get to thinking about physical systems that multiply and divide, where the two operations seem perfectly symmetrical. An example is an electrical circuit governed by Ohm’s law.

If we attach the terminals of a voltmeter to opposite ends of a resistor, we observe Ohm’s law in the form E = IR: Voltage is equal to the product of current and resistance. If we install an ammeter in series with the resistor, we see the effects of the law I = E/R: Current is equal to voltage divided by resistance. If you prefer pipes to wires, you can do the hydraulic version of the experiment, and there are also lots of mechanical schemes, where the same principle is illustrated with levers, gears, pulleys and such. In all of these systems, nature seems to divide just as easily as it multiplies. Why can’t we do the same with pencil and paper, or transistors, or neurons?

CoM #18

The latest installment of the Carnival of Mathematics is out, hosted by jd2718. It's an amazing effort, with 52 posts from 49 different authors. The first few installments of the CoM were quite sparse, and for a while I wondered whether there was enough chatter in the blathosphere to sustain it. The answer, looking at the variety and quality of posts that Jonathan has put together, is clearly yes !

Well done !

An interesting blog

Derrick Coetzee writes a blog at MSDN titled, 'Developing for Developers'. There's lots of stuff related to code development, but also articles on general computing and theory. Some recent posts:

• P-completeness and parallelism
• Cache-oblivious algorithms
• Intractability

None of this is necessarily new to people reading this blog, but it's heartening to see an audience for this material in the developer community. And of course, anyone who says,

In reality, computing has nothing to do with computers. Computing is fundamentally about solving problems using strictly defined processes under resource constraints. The theory of computing, by design, has little regard for what device you use to carry those processes out.

will always have a special spot in my blogroll :)

Carnival of Mathematics XVI

is up, courtesy Kurt van Etten @ Learning Computation. The theme is 'Good, Bad and Ugly', and for some reason, computer science is "Ugly" :). Given that two of the entries involve mathematical feuds, maybe this is fitting.

New TheoryCS Blog Alert !

Mihai Pătraşcu, cause of numerous flame wars on the complexity blog, as well as lonely campaigner for the rights of esoteric data structures everywhere, has a blog, self-billed as 'Terry Tao without the Fields Medal'.

Enjoy !

My Biased Coin: A New Blog !!

It's been a while since I've been able to announce a new CS blog. Please point your bookmarks/RSS newsreaders/browsers to Michael Mitzenmacher's new blog, My Biased Coin. Michael has occasionally posted over here, and has often had comments and suggestions for me. When he's not brokering peace agreements between power law distributions and log normal distributions, Michael corrupts young grad students at Harvard for a living, filling their minds with all kinds of random bits that are occasionally error corrected.

9th Carnival of Mathematics

From A to Z, at JD2718.

8th carnival of mathematics

It's back-to-school night at the carnival of mathematics. Time to revisit, reflect, and ponder on things we think we already know.

Estraven at Proving Theorems wishes that mathematicians today spent more time revisiting and bring up to date older, more inaccessible works of mathematics. This is discussed in the context of a re-publication of some of Grothendieck's early work on schemes.

There's a lovely quote at the end of the article, one that I cannot but help share:

I could of course keep writing paper after paper. But there is so much beautiful mathematics out there that I don't know yet, and I want to read at least some of it before I die

I remember first sensing beauty when I first learnt Burnside's Lemma: Leadhyena Inrandomtan at Viviomancy has a detailed post on this simple, and yet elegant result in combinatorics.

Burnside's Lemma ultimately deals with counting symmetries: Ian Stewart has a new book out on the history of symmetry titled, "Why Beauty is Truth: A History of Symmetry". In a post at the Brittanica blogs, he describes why he decided to write this book.

In an ongoing series, John Amstrong continues his unapologetic look at coloring knots. I'd say any topic that has phrases like 'involuntary quandle' is worth studying. Of course, the original tying-yourself-in-knots proof was the diagonalization method of Cantor, which Mark Chu-Carroll is kind enough to explain to us, while he takes a timeout from beating errant creationists with sticks of logic. Mark notes that he's been going back to some old books on Set theory and is thoroughly enjoying them, another example of the theme of the day :)

Godel's incompletenes theorem is another of the tying-yourself-in-knots variety, and this year's Godel prize winner is a result in the same vein, showing why certain "natural proof structures" cannot be used to prove P != NP. Siva and Bill Gasarch have the scoop.

Walt at Ars Mathematica catches up to the Bulletin of the AMS, highlighting some nice expository articles that should make Estraven happy.

It's time to get educational now. Dave Marain helps high school math teachers everywhere with lesson plans for teaching quadratic systems and tangents without calculus. Mikael Johansson shows bravery far above and beyond the call of duty, explaining fundamental groupoids to a group of 9th graders. Heck, I don't even understand what a groupoid is, and I read John Baez all the time !

jd2718 shows his students how Fermat is connected to them. It would be remiss of me not to give a shout out to the Mathematics Genealogy Project. We've all heard the horror stories about the students who write "dy/dx = y/x"; Dan Greene at The Exponential Curve talks of students who write "log 5/log 2 = 5/2" and wonders if we need to change the notation for log to something more "mathematical".

I am delighted, and surprised, to see the quality of reports produced in the undergraduate
automata class that Leo Kontorovich is TAing. Read more about what his students did here. Andy Drucker weaves tales (tails?) of dogs eating steak in mineshafts, and cats climbing GMO-compromised trees, to explain some of the subtler details of computability theory.

We're almost ready to wrap up this edition of the carnival. Chew on some simple brainteasers that will excercise regions of your brain that you may not have known existed ! And review the history of calculating devices, with some speculation on what future calculators might look like.

Finally, no carnival of mathematics would be complete without a cartoon by XKCD:

And that's all, folks ! Keep those posts coming. The next Carnival of Mathematics is in two weeks, hosted by JD2718.

Reminder: Deadline for the 8th Carnival of Mathematics in a week

Post your submissions here, or email me.