Cheering Up

One moment you are trying to unwind and the other, you cheer up looking at the label: there has to be an Algo Don version of "I'll make him an offer he can't refuse. ", and other euphemisms.

Waiting for SuperBowl XLIII

Baseball has moved out, basketball is in The House, but some are waiting for the moment when the two masses meet at the line of scrimmage and the game begins with a snap, others are waiting for the sacks, blitzes, touchdown dances, and yet others for the commercials. On the left is the perennially creative Pepsi.

Going Broad in Ad Auctions

Between two extremes of algorithms theory and algorithm engineering, one is some times in the middle doing applied algorithms research. Then you don't want to be too close to reality, eg., think about cache misses, or too far, eg., optimize over the entire parameter space. Algorithms researchers have discovered the fun and challenge of walking this divide: formulate problems tastefully, find new algorithmic techniques, and push the solutions into psyche of practitioners and hope for impact.

My coauthors (Eyal Even-Dar, Yishay Mansour, Vahab Mirrokni and Uri Nadav) and I study how advertisers bid in sponsored search auctions. Advertisers have a set of keywords in their mind and have to figure out how much to bid on each, given constraints such as their budget, goals such as maximizing their profit or the clicks, and statistics such as what each bid will yield in expectation.

Close to reality, applied algorithms research kicks in. Auctioneers --- Google, Yahoo! and Microsoft --- let advertisers bid "broad" on keywords so their ads will qualify automatically for auctions even when users type variations of keywords. Advertisers can not cover every keyword variation in their bidding set explicitly, and find the broad match feature essential in practice. The difficulty is that a single bid now applies implicitly to several auctions, each with different value to the advertiser. Biding decisions now become nontrivial. We formulate associated problems and provide exact/approximate solutions in a forthcoming WWW09 paper.

Those who are interested in this topic may also want to look at this paper that studies the dual view of an auctioneer, ie., revenue, efficiency and equilibrium properties of broad match auctions (paper appeared in Workshop on Ad Auctions 08).

Data Streams in Barbados

Denis Therien (humor that you can hear rustle even over emails!) has long organized the Annual Workshop on Computational Complexity at Barbados. This year I will give lectures on Data Streams. This is not like giving a talk to the general algorithmic audience where you inspire and show some technical gems, or like giving a summer course to the graduate students where you develop the material methodically so the structure falls into place and exercises follow. I need to get into detailed proofs and leave the audience of seasoned researchers at the cusp of difficult, important open problems. Here is my tentative plan.

Basic data stream models & motivations Sketches for forward distribution problems (quantiles, heavy hitters, geometric problems, linear algebraic problems) Distinct sampling for inverse distribution problems (distinct elements, rarity, graph matching) Lower bounds (frequency moments, general graph properties) Other models (continuous communication complexity, probabilistic streams, MapReduce, multipass) Connection to other areas (sparse approximation and compressed sensing, embeddings, machine learning)

Now comes the call: please send me comments, criticisms, suggestions, and slides of your results if you are willing, so I can piece together the best coverage of material in this area.

Wish List: How to write a reference letter

Continuing a vague urge, I wish someone would author a short article on how to write a reference letter, North American style, in particular for graduate admissions. This will help faculty members elsewhere avoid overly coy letters or ones that praise a student for pleasant character or yet others that merely list dry stats of classroom performance.

Dance your PhD

Scientists get there before us. I am catching up on news from last year: "in the 2009 AAAS Science Dance Contest show style, ingenuity and humor as they portray their Ph.D. research in the form of dance." Details here and the YouTube videos of winners in grad student, postdoc and faculty categories are here. The point of course is to not just dance, but dance in a way that interprets your research. The popular choice winner interprets her thesis, "Single Molecule Measurements of Protelomerase TelK-DNA Complexes." We must make it a requirement of best paper award winners. :)

A break

It is just Tuesday and it already feels like it has been a long week, so here is some distraction for anyone feeling blue. For those who care, he says, "What's up? you arent gonna take a stance..."

Wish List: How to write a statement

Those who can do, just do it and change the world. Others write about it. Yet others, like in this case, write about the need to do it.

Many of us review application packages from students abroad for graduate schools. Besides the scores and transcripts, students submit a Statement (of Purpose, of Research). These are typically very poorly written with flowery sentences, emotional claims about ones' obsession with computers, mathematics and the academic world, and definitive view of what was destined. Notwithstanding the material on the web with general guidelines and paid help, will someone write a short note on how (not) to write a statement for graduate school in CS? I like short sentences in active voice, north american style.

Personal NYer

Anyone who has studied in country X (eg., India) and moved to country Y (e.g., US) for graduate school, has a story -- of triumph, hard work, luck, or entitlement. In my case, I have been asked many times why I went to grad school at the Courant Inst, NYU. I remember reading the New Yorker magazine --- issues several months late --- when I was in college in India. I loved the writing, sketches, font and even the discreet ads on the right. When I had to choose graduate school, I chose NY, which I thought was like in the NYer, mainly darkened sketches and outlines with a manageable geometry.

The NYer continues to thrill me. The Jan 12th edition has many gems. One a quote from Hilary Clinton about Bill, "He's never met a sentence he couldn't fool with." Another, a review of the film Defiance about the survival of a group of Jewish people in a forest during World War II, says: "The farmers or workingclass men who could shoot, gut an animal, and build a shelter were sought out as protectors by the women, including the educated, upper-class women; the formerly desirable scholars of Hegel, Marx and the Talmud were not." It is a time of reversals.

Secretary of X

US has the Secretary of State, (Under?) Secretary of Science. Should we have a Secretary of the Arts? There is a petition effort here.

Outdated spams and outed scams

While being good at filtering offers of medication, body enlargements, $'s from estates, and many others, the spam filters also had to get good at identifying scam offers of funding grants via emails. "We bring to your notice the decision by the board of trustees of The European Union to choose you as one of the final recipients of a cash grant/donation for your own personal, educational, and business development (SME funding). To promote growth and creating new jobs in the European economy, we are giving out a yearly donation of £402,000.00 (four hundred and two thousand pounds) to 10 lucky recipients who have been selected from over 25,000 websites all over the globe, as funding/aid from the European Union, European Commission, and the United Nations in accordance with enabling acts of Parliament". The email further gave a contact at EU offices.

This scam originated may be one year ago, and has been outed. Then, why do these emails continue to circulate? Similarly, one gets spam comments on ancient blog entries that presumably hardly anyone reads. Is there non-zero utility in scamming via outed scams and outdated blogs?

Winding the week down: Mathematicians Score

Mathematicians Land Top Spot in New Ranking of Best and Worst Occupations in the U.S. So says the journal. Why? Here comes the backhanded slap:"According to the study, mathematicians fared best in part because they typically work in favorable conditions -- indoors and in places free of toxic fumes or noise -- unlike those toward the bottom of the list like sewage-plant operator, painter and bricklayer. They also aren't expected to do any heavy lifting, crawling or crouching -- attributes associated with occupations such as firefighter, auto mechanic and plumber."Anyway, it is fun to see the lists:

The Best	The Worst
1. Mathematician	200. Lumberjack
2. Actuary	199. Dairy Farmer
3. Statistician	198. Taxi Driver
4. Biologist	197. Seaman
5. Software Engineer	196. EMT
6. Computer Systems Analyst	195. Roofer
7. Historian	194. Garbage Collector
8. Sociologist	193. Welder
9. Industrial Designer	192. Roustabout
10. Accountant	191. Ironworker
11. Economist	190. Construction Worker
12. Philosopher	189. Mail Carrier
13. Physicist	188. Sheet Metal Worker

Following Research

Sometimes one follows research in an immersive way: you know all the results and techniques in an area, follow new conf submissions as an expert referee and may even be the gatekeeper for that area. You can be immersive in only a few areas. Other times one follows research from the sidelines: you go to talks, read abstracts, be aware of open problems in the area. You can be such an voyeur in many areas. Finally, and this is my favorite, some times I follow an area from far to the left field. I grab a few hours, and do a quick review of recent conferences and catch up, or pick a single-authored paper (they are often written with a lot of care) and follow one technical result to the extent I can reproduce the proofs. Recently, I browsed through WOSN to figure out what social network data analysis problems are of interest now, and have begun reading Mikkel Thorup's SODA09 paper on string hashing for linear probing.

ps: Claire Mathieu did a few tweaks to the SODA conference (the printed program had abstracts and proceedings finally in CD), and they really worked.

Time Capsule

At Hachinohe, Japan, I was waiting at the train station when a girl (scout, as it turned out) and her mother approached and gave me what they called a cookie. It was soft, warm, and delicious; when pressed, they said it was the sembe, a local specialty.

The girl looked composed and determined and was clearly the one who had the idea to approach me. The mom was a little reluctant at first, and then increasingly engaged, as the girl looked on. It was the day of the first snow during my trip to Japan. It was the beginning of a three hour train journey through snow, mountains and tunnels into Hokkaido. It was the evening, sun more or less down, buildings grey, and the lights unable to do much more than be dull.

Slowly as the train started climbing, snow piling on tree tops, it occurred to me that someday in the future, she would be a grown up, she would have learned to speak English, may be she would have a bad day and remember a good moment, remember the sembe she gave a stranger who was studying the glass mural in the station, she will google "Hachinohe cookie" and would find this blog entry, dated but indelible on the internet.

People fret that blogs are stored forever, what if something innocent of today proves embarassing in the future. I fret too, but this post is more a wish that someone, a particular one, will someday discover what I say today.

More Compressed Sensing

In preparation for SODA, I checked out the program, marking off talks I wanted to hear, some on Compressed Sensing, and by the process of browsing via osmotic links and slowly morphing topics, I eventually reached the site for the Geometry and Algorithms meeting at the Center for Computational Intractibility. A lot of great talks here, and now, they are on hi-res video. (I havent got the audio to work yet!). Enjoy.

It is always interesting to see the simple CS ideas reach out to new areas from centralized L_0 to L_1, to distributed CS, to devices and hardware, and now to secrecy. Yaron Rachlin and Dror Baron explore whether CS measurements provide secrecy about the underlying signals, and what can be salvaged.