Sunday, September 30, 2007

Pythagorean Expectation

In baseball, one can "predict" the winning percentage of a team as the ratio (scored runs)^2/ (scored runs^2 + allowed runs^2), something called the Pythagorean formula.
  • Data analysis in Davenport and Woolner article.
  • Mathematical analysis using Weibull distributions by Steven Miller here.
  • A linear formula.
  • Tweaks of the exponent 2 for baseball and its inflation to (10, 14, ?) for basketball.
Baseball in numbers can be found in the book called Baseball Between the Numbers. Check out the map at the bottom.

Saturday, September 29, 2007


Most of my friends don't typically think furniture (unless it is the problems of moving piano/sofa/ladder). I have an apartment that can be poetically described as a "haiku of a house". Tiny and tactfully measured. So, one tends to think long, buy small, and spend much. An example on the left.

Friday, September 28, 2007

TV Time

End of Sept, the Hunt for October is on.

I don't keep a TV at home, so I usually watch TV only when I travel and stay in hotels ("so, you watch a lot of TV", someone I know quipped). I was curious what music videos VH1 will play this AM as I was getting ready for a day on the road, and it was a nod to synchronicity, in many levels, here is, Wake Me Up When September Ends, almost an oldie in our Internet age, and a takes a bit to get to the music.

Thursday, September 27, 2007

Department of Peace

Dennis Kucinich a long ago proposed creating a Department of Peace in the government. If that world had come to be, presumably they would have funds to support research, the dept's officers from DC/VA/MD explaining problems to researchers in veiled terms like they now do for intelligence agencies, and can you imagine the "grantmanship" researchers will display in their grant proposals?

Tuesday, September 25, 2007

Week in Review

Usually I review my weeks, some times raw as they unhinge, some times in retrospect, creased and folded, but it is typically sporadic, under the whim of the schedule of my life that cannot tell the week from the weekend, the sunlight from the twilight. NY Times on the other hand is more predictable. Their Week in Review on Sept 23rd had an
  • article on (almost, not quite) Algorithms, meandering its way through Algoritmi, algorismus and other Latinisms that have obsessed me for some time ("Anonymous", the most prolific blogger, points out the related slashdot article).
  • article on Vigil for the Vanishing Tongue, that gives examples from languages spoken by only a handful of people in the world. And finally,
  • article you can not refuse (how can you?): The Day Louis Armstrong Made Noise. Lubenow interviews L. A. who finally blows, on the night of Sept 17, 1957, on race and beyond, and the world is still trying to drown out his horn.

Book Algorithms

We know the legend of Paul (Uncle, to some) Erdos and the Erdoslore of Book Proofs, proofs brilliant and perfect from The Book.

To an algorithmus, the question is, what are examples of Book Algorithms? Algorithms is a broad research area and it is hard for any one to select Book Algorithms or to even define one or elicit any consensus at a dinner table of algorithmii. In string matching algorithms, I think the suffix tree algorithm of Karkkainen and Sanders is an example. What about geometry, scheduling, graphs, approximate, random, online or other algorithms, data structures included?

Friday, September 21, 2007

Films, Handle Subjects With Care

I am a fan of American films. On my peripheral focus the past couple of years are films that introduce to us individuals in difficult places in their life and lore, and proceed to handle them gently, with great care. Families and obligations, how we try, fail, travel and find some way to be.

In the "known" category are Jim Jarmusch's Broken Flowers, the popular Little Miss Sunshine, and the merlot-killer Sideways (book). In the "less known" category are the "masterpiece of mood" Lonesome Jim and the movie I saw two days ago, "Marty-esque" I want someone to eat cheese with.

When you have no deadlines and don't want to be anywhere specifically, grab a drink, watch these movies, and walk back home reminiscing.

Saturday, September 15, 2007

Food, Friends.

My friend, The Precious One, Meeyoung Cha, loves taking pictures, of food items. Here are some of my pictures of consumables, falling far short in taking pictures, being friends, or consuming with control.

Friday, September 14, 2007

Bursting Out Of Roles

We know who is an extroverted mathematician (he is the one who stares at your shoes when he talks to you), now I know who is an exhibitionistic mathematician (who imagines he is the one who is naked when he is nervous addressing an audience). Well, it has been a long week following a long summer, so let me end it with Borges:
To see in every day and year a symbol
of all the days of man and his years,
and convert the outrage of the years
into a music, a sound, and a symbol.
Weekend is a time to burst out of roles/ stare at others' shoes, nap and dream/ weekend has just begun, Yankees struggling.

Thursday, September 13, 2007

Tricks, Techniques and Ideas

We use a variety of words to describe the means to our results. Sometimes, it is a trick (space-saving trick, four-russians trick), other times, it is a technique (rounding technique, primal dual technique), or in some rare cases, an idea. It is difficult to see when a trick becomes a technique, and when an idea sparks it.

What are the top 10 ideas in theoretical computer science?

I have been asked this question during interviews (replace 10 by 5,3 whatever, and replace theoretical computer science by others if needed). There are a few courses in various colleges that are typically introductory: Anupam Gupta co-teaches a CMU course and there seems to be a much too general CS course at Harvard. But taking it up several notches, what are the top 10 ideas in theoretical computer course?


Let me consolidate:

Saturday, September 08, 2007

Novak, All in One.

It is tennis time, a lunch conversation spurred me, and I managed to yank this out, on the left is the newbie Novak (D)jokovic, being all-in-one. And on the right is an old fave, you have to be 0-40 down to start the boom boom.

Friday, September 07, 2007

Flip rows, columns, not burgers

I heard a simple puzzle: starting with an all 0's nXn matrix, can you get any nXn target bit matrix using flip operations where each flip operation complements *each* element in a row or in a column. Trivially, this is not possible in general. Some of the other puzzles of this genre have operations where the sign of each row or column may be reversed, and the goal may be maximize the total sum of the numbers such as in Berlekamp's switching game (coding theory connection here). If anyone knows of novel puzzles of this genre, please let me know.

What coffee and pants do to you

What we think we do when we wake up, wear pants, drink coffee,and just be: draw pictures, prove theorems. What others do as advertised: celebrate wild, and smile sparkling huge.

Wednesday, September 05, 2007

Time Travel

I got an email from someone who I knew in high school, and notwithstanding the whys and whynots, this person remembered me as "thin and dark". What nature, time and NY have done to me: I am no longer thin and I am and always was less handsome than "dark". The email, for a moment, pushed me to travel back in time, but I went past high school and hit the earlier boyhood of fun counting bananas (my introduction to arithmetic and eventually math). That is the problem with time travel, it is hard to get it right. Alan Lightman has a somewhat lightweight, marginally enjoyable fiction based on different hypotheses about time: what if the speed of time decreased with height over the ground, what if time gradually came to stop at a singular point on the Earth's surface, etc.

Triumphant iPhone

On 6/29/07, the iPhone was released. By now, the world has found the YouTube way to react to the Phone, Bill and Battery.

Tuesday, September 04, 2007

Top X (Contd)

I remember the STOC/FOCS bibliography that David Johnson did a while ago (from 91, can't find an online copy). I was in grad school then and was infinitely interested in the top X lists, eg., the list of top X researchers with all time high STOC/FOCS publications (the top was Andy Yao then with Avi Wigderson on his heels if my foggy memory is correct). These days, it has become somewhat more easier to compile such lists, one just works with favorite data source such as DBLP (still, there are challenges). Here is an interesting study by Marios Hadjieleftheriou from AT&T. The focus (and perhaps the bias in DBLP) is on Database Research but towards the end, it has some nice lists on STOC/FOCS and even, gasp, SODA.

Sunday, September 02, 2007

Journal Editorial Boards

There has been a lot of discussion about the size of conference PCs and their mix, and perhaps also journal editorial boards. First let me (us?) thank the people doing the hard work on these PCs and editorial boards. Second, should we be expanding these journal editorial boards to disperse the work better? I don't usually check out journals, boards and websites, but took a quick look at:JACM (23), SICOMP (27) and TALG (26) -- all seem to have put together a fantastic set of researchers, but seem lean?


WINE, not Wine. The 3rd Intl Workshop on Internet and Network Economics (WINE) will be in San Diego this year. The website has a Koala and 2 Giraffes. The list of accepted papers has been out for a while: lot of potentially interesting papers on sponsored search auctions.

Reporting a Discovery: Copenhagen.

Even now, centuries after lands got discovered, flags planted and civilizations collided and in some cases mixed, one has a sense of discovering places, sometimes as small as a cafe, a hike route, or in rare cases, a city. I visited Copenhagen for the first time, and thought it was a personal discovery: walkable, liveable, hordes of bicycling natives, art galleries, cafes, old buildings, sailboats, and surprises. I walked onto a street party around midnite, a concert in the park, and a routine trip to the art museum (uncrowded, free and a soothing experience) had a stunning special exhibition of scuplture by Jorgen Haugen Sorensen. Not for the weak-stomached. Amid giving talks at Aarhus and Copenhagen, meeting students and potential recruits, and visiting Google office, thanks to Mikkel Thorup, I eked out a day of fun.

Saturday, September 01, 2007

When Algorithms Shrug

World has visualized what happens when intellectuals shrug thanks to Ayn Rand, and it is popular in fiction to visualize when computers shrug, say due to some coordinated, distributed attack, or whatever. What we saw the past month in the wall street is the computers and communication infrastructure staying intact, intellectuals and media remaining engaged, but the sophisticated algorithms (that turn data into trading strategies for hedge funds) shrug, and the market tumbled. I am no expert, but I hear that majority of hedge funds have suffered (see their Quants' letters to clients), including the impossibly-dominant Renaissance Technologies of the legendary Jim Simons.