Social H-Index

Happy New Year, Everyone!

I remember the STOC/FOCS bibliography that David Johnson compiled in mid 90's (pre-web).  It had a lot of interesting "top-k" lists. One list remained on my mind: authors with most number of single-authored STOC/FOCS papers. Andy Yao topped that list,  far above the rest.

How does one measure the impact of an author or a publication? The h-index aims to improve over raw counts of papers or citations by combining both, but considers authors in isolation and does not consider collaborations. My coauthors and I have been playing with extensions that "socialize" the h-index. The main idea is, a paper by authors (a,b) should count to the social score of a if it is one of the top papers of b. Now, what is a top paper, how to extend this to multiple authors, etc. are addressed in our paper that also has empirical results contrasting the solo h-index vs social h-index.

Being Sick

Best thing about being sick: reading a large pile of NYer magazines (paper edition). When I lived in NY, I read it front to back, these days I read it back to front.

The Dec 24--31 issue is fabulous with article gems from the turkish theater done by these village women to cutting through polar ice, rewilding in Holland and an utopian language. The book and music sections were keen observations, as usual.

Simons Research Fellowships in Big Data

This is a reminder of the upcoming deadline for applications for Research Fellowships at the newly created Simons Institute for the Theory of Computing at UC Berkeley.

Simons-Berkeley Research Fellowships are an opportunity for outstanding junior scientists (up to 6 years from PhD) to spend one or two semesters at the Institute in academic year 2013-14, in connection with one or more of its programs. The progam on Theoretical Foundations of Big Data Analysis runs in Fall 2013. Applicants who already hold junior faculty or postdoctoral positions are welcome to apply. In particular, applicants who hold, or expect to hold, postdoctoral appointments at other institutions are encouraged to apply to spend one semester as a Simons-Berkeley Fellow subject to the approval of the postdoctoral institution.

Further details and application instructions can be found here. The deadline is Jan 15, 2013.

Solving Problems?

I know that trying to solve a problem begets others, but we (should) start somewhere:

• Hurricanes. When low pressure zones emerge, can we create a low/high pressure high/low  temperature zone far away from population centers and draw away the damage?
• Hindu-Muslim Confrontation:  Can Pakistan and India merge?
• School Shooting:  Should each gun and bullet be wireless and location enabled so they can be shut off when they are close to population centers like malls, schools, etc.?

Read, Think, Fry

Why do I like Starbucks? They brought the NY Times paper edition to parts of the country where it would have been a challenge to find one otherwise.

I live in a neighborhood where everyone justifies their everyday activities in the larger arc of social good. So, I was thinking, how does the CEO of Starbucks justify his work? He helps Mathematicians seek and prove absolute truths, and helps build the foundation for all of Science and Engineering. So there.

Finally, I like fried food. But in Seattle they bread and fry Salmon, in UK, they bread and fry Mars bars and in India, they fry chicken until it tastes like samosa. No, No, No.

NY Area Theory: A day of theory turns 30

Zvi Galil started something a while ago: an annual one-day meeting at Columbia Univ in NY, get the best theory people to speak an hour each on some of the best theory results, often the recent/emerging/nascent ones. In one case, I remember Rao Kosaraju going through a proof with symbols a,...,k and missing a few eg., f, i, ... because he didnt need them once they were used in the intermediate versions of the proofs (which I am sure he did on the Amtrak train up from MD to NY! :)) Zvi set a high bar for a day of theory.

I sorta remember the white T-Shirt for the 25th anniversary of the day,  five palm imprints in black, graffiti style. The meeting is now semi-annual, and called the NY Area Theory Day, and its 30th edition takes place this Friday. The list of speakers looks awesome. Enjoy!

Aravind's White Board Talk

I  heard Aravind talk recently about the Lovasz's Local Lemma (LLL).  He spoke about the results in his JACM paper that builds on Moser and Tardos and gives improved constructive versions of LLL. In particular, they show an algorithm that is poly time in the number of underlying variables (and not in the total number of events) by looking at the core/kernel of the variables that define the events. He also spoke about some more recent work, but alas I spaced out. The whole body of work has a bunch of nice applications, eg, to the Santa Claus problem or the classic routing result of Leighton, Maggs and Rao (which I was happy to be reminded after so long!). In general, Aravind's talk was nostalgic with the Rodl's nibble, FKG and Janson's inequalities and other probabilistic tools. Aravind is a master,  not only in applying these methods when they are effective and extending them,  but also quite comfortable in  ``inverse'' step of hacking complex problem spaces into portions where these tools can be applied. Aravind is a poly-algorithmicist, and beyond his work in combinatorics, graph theory and probability, he has some nice stuff in networking, auctions and social structures as well.

Story of the Flood

A classic short story in its entirety: "When he awoke, the dinosaur was still there."

What I lost in my NY apartment due to the flooding by Sandy:

Half a lifetime of all the paintings I did, gifts I got, photos I took and things I made. Now I can go to the afterlife clutching only my research papers to show.

Simons

Simons related announcements:

• The Simons Institute for the Theory of Computing has a webpage. Lot of good information here from upcoming programs to call for Research Fellows which looks very interesting.
• Simons Science Series of talks continues with Ingrid Daubechies on Oct 24.
• NY Area CS and Economics Day (NYCE) continues for the 5th year. The early meetings were hosted by the NY academy of sciences in downtown NY, but Simons foundations will host the upcoming edition on Dec 3.

Airline Travel Tales

When airplanes work, they are great, getting us from A to B in a swish, with many channels of entertainment (forget the food, I am surprised someone hasn't worked out a business model where I can order great food online and they will deliver it to me fresh and hot, past the security just before I board, sorta like Mumbai Dabbawalas). When they dont:

• I was stuck on the tarmac with an engine problem and the pilot says, "Electrons are running around in the computer not listening to us. We are trying to talk to them."
• The other day, the pilot starts the engines, they shut down for some reason, and he announces on the PA, "We will try to switch the engines on in the reverse order and see if that works."
• Recently heard (due to United/Continental merger, the staff are not crosstrained on others' equipments and there is chaos on board during most flights): "We seemed to have keyed in the wrong entertainment code, we have to wait for this movie to finish and start with the new program in your entertainment guide."

Finally, no matter the circumstances, airports are very badly designed.  Hub-and-spoke model sucks, transfers take far too long, instead of bringing airplanes to people, people walk along many spokes, spines, and multiple security lines.  Try Frankfurt transfer! Amsterdam has accepted the horror and has a tiny Rijksmuseum in the airport to distract you.

Quick trip to NY

I spent the weekend in NY.  In NY, everything changes between any two visits, places you know will die,  from that debris will rise new stories. My days intersected --- sometimes obliquely --- with

• time in MSR NYC office, 
• wedding in Musician John Popper's family, 
• Usher's party at Casa La Femme,  
• new Michelin 3 star Atera by Mike Lightner, 
• Shaineal Shah's Xocolatti, and 
• I had comfort food (matzo ball soup and kasha).  

I had a conversation about Tucker cars and the business of cinematography ("business of rejections" claims Ivan) that cheered me. Note to the world: real estate is back beyond the 1%.

Films: Foreign, Bolly, Animation and Beyond

On the flight back from India, I watched Thermae Romae, a two-period piece in which an architect who designs baths in ancient, royal Rome time-travels back and forth to the baths of modern middleclass Japan. It is a great premise to tie these two baths-immersed cultures together across time and space, and a casting challenge to have grand Roman scenes with Japanese actors in them. The film is comic with a Roberto Benigni like Banana, a toga that becomes the Samurai garb, the  line by a Japanese traveler to ancient Rome, "That Marcus?" and others. This is not the top example of Japanese filmmaking, but it occurs to me that Bollywood that "draws" from the west should turn to Japan too. I was told, I should address this tip to SRK.

In addition, I watched Kitsutsuki to Ame about a woodsman in a remote town who gets drawn into the making of a Zombie movie by a visiting film crew. One learns "Zombies cant run" and there is a fun finale when humans and Zombies wait for a break in the rain for the shooting to begin. I also watched a couple of other HK/China flicks like Dai Chui Bo.

Time traveling to present times. Like last year, I had passes to the Palo Alto International Film Festival (PAIFF) that just concluded. Last year I used it for VIP parties and lounges, panel discussion with filmmakers and other things, but this year I mainly used it to watch childrens movies. Palo Alto has an interesting place in film making history, and their promo has the sprinting horse, a reminder of the first killer-app for making moving pictures.

This is Palo Alto, no event is complete without local entrepreneurs and new startup technologies. Before the films, you could use theater wifi to access voteiff.com and play trivia, and results appeared real time on the screen! Also, the FF showcased some nice animation technology, melding handdrawn animations into disney-esque and 3D.

More India

Here people use run length compression: the telephone number 9220008211 becomes  9, double 2, triple 0, 82 double 1.

The govt has interesting ways to "distort" the market. In one of the states, every working person is guaranteed -- by govt -- like 150 days of work per year at say 100 Rupees/day. This means even half-working person turns up to do the govt sponsored work (carry construction materials), does some fraction of work,  and  the businesses go along since they would rather get a fraction than none, and this alternate source of income means labor costs have gone up tremendously for comparable or lesser valued work at homes, businesses etc. I also heard the govt gives free laptops to high school kids in govt schools. No network connection.

On education: I spoke to a school teacher and they said one of their biggest challenges was optimizing which subsystems to run using an inverter of limited capacity during the electric power cuts  that occur throughout the day (senior students with approaching exams get to keep their fans working, students in grades 1--3 get A/C, etc ).

Finally, people speak in analogies. "What you propose is like in that movie.." This kills me. All analogies are wrong, some more than others. Analogies are correct only at the high level.

India etc

I am in a hotel in India, lobby and pool teeming with  Cricket stars of India and New Zealand who are facing off on the field nearby. Here is a colorful website of  IncredibleIndia  --- you may have seen their ads in US --- and a website of Indian govt which provides a lot of info.

From a conversation: Buddha understood the Universe. Not just our world, but the entire Universe. I imagine one who understands the Universe becomes really quiet.

A conversation triggered the following  analogy: Famous sports players (eg., Basketball) have a few opportunities when they near retirement such as becoming a coach (tell others what to do) or a TV commentator (discuss what others do). Michael Jordan --- not of Machine Learning fame --- did something new in his third act. He became  a player for Wizards, inspiring the young players by being in the court with them, and willing them to become better by his workout regime, play on the court, and his overall mental posture. I really like this model that transends mentoring from sidelines, but see very little of it.

Sneaking into Italy

I needed a break and managed to sneak into Italy briefly. I was lucky. I met Tara Gandhi, the great granddaughter of Mahatma Gandhi. She spoke to me in Tamil and Bengali, and to the others in what appeared to be flawless Italian! She was really inspiring, both in her graceful demeanor, and in her words, bringing message of friendship, beauty and strength through non-violence.

I also got to see part of the Ms Italy beauty contest at the stunning Montecatini Terme. What can I say about the contestants: gods or genes give us our eyes (all sparkling), humans give us the hair (all flawless) and the rest of the attitude is all ours. A psychologist who spoke to the contestants reported several said the person they admired was Steve Jobs. Hard to escape computers (science).

Personal, homepage and stuff Indian

Bruce Maggs jokes that he used to know me when I was Indian. :)  I, of course, am an Indian, was always an Indian, as Frost would have said.  For personal and family reasons, I am going to be India-focused for the next few years, spending time between US and Bangalore.  I will insure this does not change anything work/social for most of my contacts,  so let me go past this announcement and say something potentially more interesting:

• I had a Web -1.0 homepage from 2002. Thanks to Sandy (Technicolor), I now have an updated homepage, check it out. It should render nicely on tablet and phone, laptop and desktop.
• Bruce Maggs stumped me with this frustrating challenge: Name an Indian, living now in India and known to many people in US. 

On Facebook

I am not an expert, but people ask me to talk about Facebook's business. Here is a silly answer. Say Facebook has 1B users and each is able and inclined to buy a single share of Facebook for USD 40, a onetime transaction, no annual fees.  That is 40B dollars that Facebook can invest, and using what private hedge funds "guarantee" --- 3% of free spending money after maintaining capital, adjusted for inflation --- have 1.2B dollars of spending money per year, for perpetuity! You can maintain a decent Engineering and Infrastructure operation for that budget. Make those shares non-voting. 

What people like about the Bay area

I often have a question in mind, a question for which it is not important what is my answer, but I need to know the answers of the human diaspora, not an unique answer but the variations. More than a decade ago, I asked people, "What does the phrase Safe Love mean to you?" and the experience filled a short story I didn't get to publish yet. These days I ask transplants to the Bay Area (not the natives), "What do you like about the Bay area?", and the answers worth remembering have been:

• Fresh fruits
• Humming birds
• Near-zero humidity 

Oldtime Tweets

I had a conversation with someone who reminded me there were oneliners, before there were tweets; the oneliners didnt need hyperlinks, only a lot of thought from the audience to find the hidden links.

• What  any research area needs: A Howard Roark.
• The reason I hate Apple: The Genius Bar.  
• Terence Tao is the Kevin Bacon of Google+
• What I look for in the Bay area: NY expats.

Summer School on Markets, Trento

Summer schools, like the one on Market Design at Trento, are mental islands: you get out of your context of every day, meet new people, in particular students,  you learn about some topic and world seems full of possibilities.

The summer school was run by Dan Friedman and David Parkes, who make a powerful Venn Diagram covering CS and Econ among their research interests, with help from Axel Leijonhufvud and Enrico Zaninotto. The Trento schools have a dagstuhlesque history. There were 20+ students from Econ -- CS -- Applied Math spectrum. They formed groups, did research projects during the week, and presented their work on the last day.  Example projects included improved matching markets and auction design with information revelation costs. I didnt get as much time as I wanted to interact with the students on specific research projects, but enjoyed talking to several. It was two weeks long, but I missed much of the first week due to travel to Edinburgh for ICML, so my notes are spotty.

Lectures: Dan F and David P anchored the lectures, providing intro and glue lectures to solder together the lectures of guest lecturers.  Peter Cramton spoke about electricity markets. It is reassuring to have bona fide economists so deeply embedded. Estille Cantillon spoke about mechanisms for matching students to schools in Belgium, this was a great example of Economist in the Field! Tuomas Sandholm spoke about kidney exchanges and  expressive auctions. I lectured on problems in Ad Exchanges.  I liked Dan's definition of recommendation in a utility (and hence, for me, repeated games framework); David's lecture on combinatorial exchanges in which he posed many open problems; and, a talk with Peter Cramton on what were the a handful of fundamental concepts of Economics. Thinking about the marginal effects emerged as a central tenet, and it came up again in a conversation with Zhenyu Lai when he proposed a target for carbon trading that all countries could adopt. 

• It is so difficult to travel within Europe by air. There are few direct flights and when they are by EasyJet/RyanAir, they run in the middle of the day and the entire day is consumed traveling. My proposal to EU: start a pan-EU airline or two, kill off the struggling ones supported by individual countries that are flailing.
• The summer school had sparse Internet access. As a result, no, I didnt get more done, I spent more time fretting there was no Internet access.

My Blog

The other day someone asked, paraphrased, "when you write a blog entry, what  do you optimize for the audience"?  Google and other search engines optimize so its visitors who pose a query get quickly or instantly to what they want. Yahoo and other portals optimize so visitors instantly view all they care about on a single page. I have a vision I optimize for: I wish the visitors will scan my blog entry coarsely, get a nugget or two of interest, chuckle or frown or perk up, maybe retrace over a portion of the entry to resolve the nugget better, and soon pivot, go on with their every day lives. But the nugget should linger beyond those few seconds they spend at the blog entry, should resurface later in their psyche, and have some long term utility. 

ps: I couldnt think of a metaphor for this effect I want to induce --- slingshot, catapult, pivot --- nothing captures the whirr.

ICML 2012

When I gave a plenary talk at SODA in 03, I had to give the talk a day earlier because the slotted speaker could not make it to the time slot. At ICML, where I was slotted to give the plenary talk at 8:40AM on the first day, I could not make it to the location and the hosts (Andrew McCallum and Joelle Pineau and Charles Sutton), very graciously, scheduled me at 7 PM the same day by carving out a new slot. This tale of two slots worked out well for many: the North Americans who had flown in and had sheepishly slept thru my early AM slot could make it to my evening slot; the attendees had the poster session just before my talk and had a chance to grab some beer and snacks; and, I could go over the standard 50 min --1 hour slot because I was *only* standing between the audience and their dinner.

I spoke about streaming, summarizing the by-now standard material on sketches, l_0 samples and their applications, in particular to compressed sensing and graph algorithms resp. For the latter, I highlighted the work of Ahn, Guha and McGregor on graph connectivity problems using l_0 sketches. Then I discussed new directions: (1) new models of learning algorithms in distributed world where the goal is to minimize the communication (I highlighted recent work by Daume+Phillips+Venkatsubramanian, Blum+Balcan+Fine+Mansour, see here). (2) Continual distributed streaming (highlighted Cormode+M+Yi) and (3) Pan-privacy (I highlighted this work of Dwork, Naor, Pitassi, Rothblum, and Yekhanin). Besides gratuituous jokes, puzzles and comments on recommendations, that was the talk. From the questions afterwards, it seemed like the audience took in the hashing part of it and discussed ways to use it, I hope the other parts will percolate in later. Over dinner:

• Some in ML learn about developments in TCS world (solely?) by reading Michael Mitzenmacher's blog. Michael: you are carrying us, mate!
• Like all communities, ICML is tinkering with the conf. One of the suggestions concerned making reviews (think reviewoverflow) public. A central suggestion will be to separate/delink the identities of authors from reviewers (which you can do on the web) but make identity persistent. 
• Someone asked me how many pairs of shoes (2) and glasses (6) I had while traveling. I said only 2 shoes because very few extroverted mathematicians at ICML to look at my shoes, the ref to the joke was lost in some cases.
• Finally, I saw printed NY Times in French. 

Collages from Baerden to Bradford

I am a huge fan of collages. Romare Baerden is collages then, pieces of debris creating incredible 3D worlds of neighborhoods, music bands and reality; Collages now is Mark Bradford, an incredibly talented artists who works with wax paper used in hair salons and layered posters and claws out deep, nuanced scapes. Thanks to Whitney for helping world discover Mark.

Newness in SF Area

I have decided to go new. Shoes, only cydwoq. Buy them at Bulo in San Francisco and say hi to Enrico.  Glasses, J. F. Rey, Paolo Seminara and Jonathan Cate. Buy them at Next Eyewear at Oakland.

BRIC conferences

Two upcoming meetings are interesting (anything in B and I?):

• The 7th Intl CS Symposium in Russia, July3--7. Opening lecture by Vijay Vazirani and Piotr Indyk is an invited speaker
•  China theory week at Aarhus, Aug 13--17. Invited talks by Christos Papadimitriou, Vijay Vazirani and Eric Allender. 

Upcoming meetings

• Graph lab workshop July 9, SF. 
• Massive data sets MMDS. July 11--13, Stanford.
• Algorithmic game theory summer school, July 14--21, Greece.
•  v2.0 of sparsity workshop

Thoughts

On scale: Rakesh Agarwal and I spoke recently. A goal would be 10 Million sized online class room!

On NY: It survived the assault, going from "WALK/DONT WALK" to nonverbal "red hand/white silhouette".  Folks still read on subways, and the city remains a readers town.

On puzzle: A long time ago, I had a function calculator and a lot of time. So, I worked on the puzzle of starting from a 0 in the display and generating any arbitrary integer, only using function keys (arithmetic operators, sin/inv sin, log/exp, etc, all unary operations). Any pointers to this puzzle or its variants welcome.

On lingo: I heard of SoLoMo, and it is not about real estate. Social/Local/Mobile. Advertising.

Algorithms Day at Google, NYC

Google NY folks organized an Algorithms Research day following STOC and invited a bunch of STOC attendees. Vahab orchestrated the day, and from what I could see, the team of Nitish, MohammadHossein, Silvio and Jon helped out, may be others too, behind the scenes where I couldnt see. The team did a great job!

Eva Tardos, our newest Godel winner, started the day and talked about sequential auction. Bidders know order of auctions.  v_i(A_i) for items A_i for i. n bidders, m items. Goal: social welfare. Agents strategic. Solution concept: subgame perfect eq (for each subgame history). They looked at PoA of complete as well as incomplete information case.  The talk had an interesting example (Dining Bidders) that showed some of the nuances, and had one nontrivial bidding strategy (and its variant for analysis): each player draws  a random sample of value from others values and uses that to strategize. Costas and Moses asked what value distributions challenge the analysis and how the PoA of 3 is affected by the distribution. I asked, if the order of auctions can be determined and how that affects PoA.

Eyal Manor, the Engg Director for Ad Exchange (AdX), spoke next.  Q & A was the key, this was clearly an opportunity for researchers to get answers from a key person in AdX.  Bobby asked, why push bids for each impression sold, why not let ad networks push bids in a flexible way in small bulks. Eyal's answer was,  real time strategies seem important to AdX players.  Someone asked, there is information asymmetry, can AdX equalize the information available to all parties. Eyal answered that AdX did not own all the information in the ecosystem, publishers and other players do, and their data is private or secret. Eva asked, is BlueKai a pain in AdX operations? Eyal said they were good partners. Eva pointed out that Economics says what data should be shared: platforms should share, buyers should not have to share. Again, the issue is data is owned by many parties. Moses asked, what data are not shared. Eyal gave the example of someone day bought a ticket, bank login etc.

Alfred, VP of Google Research, spoke via video. He used the occasion to let folks know that Google was providing some space for Cornell's operations in NY, which is good news for Academia. Alfred couldnt resist posing some technical  challenges: we dont understand fairness of auctions to individual users; we have complex auctioning systems and very sophisticated distributed systems, how do we quantity and control risk?

There were several other talks during the day (bobby, gagan, mohammad, andrew mcgregor, et al) which I am unable to summarize here. Vahab gave an excellent overview of research in Google NY and provided pointers to folks who were experts in different projects. Towards the end, Mukund spoke about some interesting problems with interpreting sales data, and our other new Godel Prize winner Tim spoke about simple and optimal auctions.

Prabhakar called me an old timer, and I felt like one, slightly out of touch with it all. I ran the first of such meetings in 2009 after SODA, and it is great to see the continuing tradition. It was also good to catch up with Sanjeev, Stefano, Sampath, Seffi and others, that is just the S's.

On Generations

My dad worked in a coal mine for some time. He took me to work one day when I was a boy. I passed massive stalks billowing smoke, periodic loud noise from thumping machines, whirring conveyor belts carrying coal chunks, dust, stink and debris everywhere. I probably walked out with a piece of coal in my pocket and dirty hands.

Now when I take my daughter to work, I show her grey floors, neutral color walls, copier machines, and flat screens. The only thing that sputters, spits out hot water and steam, and makes noise is the Cappucino machine. She leaves clutching markers.  I hope in 20+ years she can find poetic words to think of her visit to her dad's office. 

On Dining Astronomers

Recently, as part of a Berkeley meeting, I had outdoors dinner with a group that comprised Astronomers. There was a  serious side to the conversation, but I am going to focus on the friv:

• Breaking off from a conversating group, holding a drink, one of them said, "Excuse me, I have to go start a telescope."
• Talking about the impact of research, one of them said, "I mean, it is NOT earth-shattering". It occurred to me that Astronomers should not aim for earth-shattering research.
• Finally, one of said, "We have astronomical data". To a half spaced-out Computer Scientist, it sounded like data Beyond Big. 

The astronomers convinced me that their work is difficult, because they can ONLY observe and study the data: all mining and no experimentation, but still fun. Outdoors dinner meant mosquitos, but as someone pointed out, even mosquitos are laid back in Berkeley. 

Are you being Creative?

I had lunch with several educators and the conversation started with the observation that many of the modern Internet companies treat their employees very nicely with great, free food, time to develop their own projects, and contribution to their volunteering activities away from work. Why do they do it? Answer is, they want their employees be creative: you dont want your software engineer to come to work in the morning at 9 AM and ask, "What do you want me to code?", but you want them to be at work and ask, "What can I do to make things newer, better, slam dunker, .?". Now, the question is, why dont universities do the same to their employees, say faculty members? Dont universities want professors to be creative?

ps: The conversation later turned to, "Are we -- professors -- asking our students to be creative?" Not one educator at the table thought we make our students creative. I need  a more optimistic answer from the World. 

Ad Exchange Research Contd

Here are my two recently released papers on ad exchange research:

• Doubleclick ad exchange auction. Y. Mansour, S. Muthukrishnan and N. Nisan. ArXivs.  
• Strictly-Black-Box Zero-Knowledge and efficient validation of financial transactions. M. Rabin, Y. Mansour, S. Muthukrishnan and M. Yung. ICALP 2012.  

In the first paper, we present a simple auction called the Optional Second Price (OSP) auction that is currently used in Doubleclick Ad Exchange. In the second paper, we present an efficient protocol for running OSPs in a provably trust worthy way.

Sculpture, Then and Now

Sculpture Then: the Terra Cota soldiers in Emperor's Tomb in China from 3rd century BC has great scale and scope. I have always assumed the soldiers were for the protection of the Emperor in after life. But the tombs reveal more of course: eg., the organization structure of their society (as discussed here). But I loved the recent take by NY Times that he needed the army for this ultimate ambition of (having conquered China and History) conquering the heavens. Now the whole tomb makes sense!

Sculpure Now: Anish Kapoor is the 21st Century maestro. I managed to see his two exhibits at Chelsea Galleries recently: saw his concrete pourings for the first time and was awed. I was also with a friend in kurta with long hair, and the audience walked around us peering curiously at him, mentally calling him Anish. Salman Rushdie was in the audience too, undisturbed in NY audience. ps: Sneaked into Kitano Jazz and heard Toshiko Akiyoshi.

Research Strikes

The long arm of research.  A paper 3 years ago by Balachander Krishnamurthy and Craig Willis that measured the leak of online personal information to third parties is cited in an FTC investigation that eventually leads to a MySpace violation citation. See the Forbes article, and Ed's FTC announcement. 

2 Thoughts

I saw my 8-month old do the familiar pinched-two-finger-zoom-out gesture of iPhone/iPad when she saw an Anish Kapoor sculpture. Now this has an obvious amusement to it (8 month old, iPad, Apple's genius and so on), but if you know the scale of Anish's work, this is vaguely philosophical.

The other day over research, we said, "Let us go bandit on this". 

Turing Celebrations This Side of the Atlantic

Princeton has been the heart for the past 100+ years, from Einstein to Nash, von Neumann, Turing and many others, pumping scientific blood through the world. Turing Centennial Celebration will be held May 10--12 at Princeton with an excellent program. Enjoy!

Researchers Will Find a Way

Researchers previously at Yahoo! from algorithms to databases and machine learning, are finding new homes in (Google, LinkedIn, Microsoft, ... ) Researchers find a way. 

Beets on Hands

Cooked beets for lunch today,
Hands and shiny MacBook Air are still red.
The perils of mixing cooking with email.

Online Free Courses

We know the examples of free online courses with 100k+ students each from Stanford in CS, are there similar developments in Engg/Medical School/Business School/Arts or whatever?

A Claim

If you do applied algorithms, at some point you are going to code/advocate/analyze hubs-and-authority iteration.

Some numbers

Some numbers in news:

• Microsoft paid AOL $1B+ for <900 patents for an average price of $1.3M. I dont know the max, min and median value of a patent in this portfolio. I have been skeptical in the past with researchers' explaining their super algorithms to me how to ``value'' a portfolio of items including patents, I wonder if any of them would have estimated this value.
• A few months ago, Mitt Romney released details of his tax returns. One number is on taxable income of $21.7M, he paid $3M in taxes. While media has focused on the effective tax rate of 13.8%, but some of the others focus on a different rate. It is estimated that his net assets are like $200M, but some fraction (<1/2) of it generates taxable income. How does he make 20%+ return a year on his assets?

Mechanism Design and Commuting

Balaji Prabhakar has been successful running large scale incentive programs in real life in Bangalore and Singapore to alter social behavior (in scale more than a carefully curated marketing study group, less than wild experiment online for 1% of website visitors). Pretty amazing he got these programs running! Now he is running an interesting experiment in Stanford involving congestion and parking relief incentives.

A Puzzle

It has been a while. Consider array A[1..n,1..n] such that any rectangle A[i...j,k...l] has at least one element that appears exactly once in the rectangle. What is the smallest number distinct elements A can have?

Some Almost Technical Thoughts

Ask an Engineer to draw a straight line through 3 arbitrary points on plane, and the Engineer asks, how thick can the line be? People always says this like it is a joke on Engineers, but I really think these Engineers are smart!

Then there is the story of The Hare and the Tortoise. The Hare, confident of winning the race against the Tortoise, stops to look around, smell roses, eat carrots, take a nap, and ultimately loses the race to the slow but steady Tortoise. When I hear this story, I think, if I were the slow and steady Tortoise, I too will still stop, smell roses, eat and nap, along the way.

A colleague, in natural flow of conversation, told me, (s)he was thinking of problems with the``career graph''. There are so many graphs, social, societal, vehicular, .. whatever, why not the career graph.

Open Source DB Algorithms

Joe Hellerstein and others have built MADlib, an open source library for statistical and machine learning analysis with SQL on multiple machines. Algorithms researchers explore and analyze specific algorithms for specific problems (``point solutions'') and a way to use them in practice is to grab the data from database and write your C++/Java Code. In my mind and others', it has been a much-needed intellectual exercise: how and how much of such specialized analyses can be pushed into SQL. Joe and others have taken the exercise further and have built the bones for doing it. Joe is a persuasive thinker, and here is his blog. If you have spare programming cycles, contribute!

Workshop on Ad Auctions 2012

Nikhil Devanur, Gagan Goel, Mallesh Pai and David Parkes are organizing the Ad Auctions workshop this year, as usual colocated with ACM EC conference. More info here. The deadline is Apr 7th and the meeting will be in Valencia, Spain. This is a true workshop, an audience of 100 or so of folks who know the stuff, and you can have a high bandwidth conversations.

Big Data Workshops

There are two upcoming workshops that explore big data: algorithms, machine learning, databases, all else:

• From Data to Knowledge: Machine-Learning with Real-time and Streaming Applications, UC, Berkeley, May 7--11
• Big Data at Large: Algorithms and Applications, at Duke Univ, June 14--15

The Trumpet

My second favorite music instrument is the Trumpet. I got to hear an hour of trumpet, part performance, part education, at the Habst Theater yesterday, March 10, as part of SFJazz. This was a low key performance, but starved that I am, I was reminded me of all kinds of voices, Zora and Billie, Bolden and Keppard. Let me showcase here, a piece of Louis Armstrong: if you watch the piece on the left, you will see satchmo grab the trumpet at 1:10 and you will want to watch him, as he wails all the way to the end.

Postdocs Needed

The job market is probably a little more clearer now than say at the start of the year. Owing to various funds available at Rutgers, we are seeking one postdoctoral visitor in each of the following research areas (total of 3):

• Sparse approximation, compressed sensing, coding/decoding, and applications.
• Ad exchanges: auction design, optimization, learning and data mining; more generally, display ads.
• Privacy (inclusive) and game theory.

Please email me with a CV if you are interested. Thank you. Needless to say Rutgers area is great for theory, algorithms, databases, data mining folks.

Theoretical CSist In News: Prabhakar R.

It is nice when there is so much coverage when a theoretical computer scientist (I know Prabhakar Raghavan transcends CS, much less TCS) changes jobs.

FYI: Market Design Summer School Deadline

13th Trento Summer School, Intensive course in "Market Design: Theory and Pragmatics", June 25 - July 6, 2012, held in Trento Hotel Villa Madruzzo. Co-Directors: Dan Friedman, Economics Department, Santa Cruz University CA, and David Parkes, School of Engineering and Applied Sciences, Harvard University. Applications are due by Saturday, 17 march 2012.

The Trento Summer Schools are intended for advanced graduate students and post-doctoral scholars in economics, computer science and operations research. People interested in participating in the Summer School are encouraged to apply by submitting a curriculum vitae, a two-page essay describing their interest in Market Design, a course transcript from their PhD program, including advanced examinations passed, two letters of recommendation, and statements about their current or projected research, along with relevant research papers, if any. Applications are due by Saturday, 17 march 2012. Persons interested in participating in the Summer School should follow the application procedure. Admissions decisions will be announced by 10 April 2012.

ps: My student Darja pointed out this other summer school at CMU in Aug 2012, which also sounds very interesting. Deadline to apply April 15.

On Softwaring...

Sometimes you produce algorithms that you believe should be useful, and then you might just go little further, and produce pseudocode or even code. You dont want to do this for all the theory results one produces, only for the ones you think this will be worth the effort. And then you do outreach: you have to take it to the applied communities that will care. Here are two examples.

• Count-Min Sketch. Many pieces of code exist for count-min sketch, but we thought it will be worthwhile to draw attention of many software professional. So, we wrote an expository article in IEEE Software recently, in a special theme of "Algorithms for Today's Practitioners", edited by Giuseppe Prencipe, University of Pisa, Cesare Zavattari, CrowdEngineering, Alessandro Tommasi, CrowdEngineering, and John Favaro, Intecs SpA.
• Approximating Fourier Transform. Over the past two decades, there have been several algorthms to approximate fourier representation of signals. I really liked this expository article, "A Tutorial on Fourier Sampling, How to apply it to problems" in IEEE Signal Processing Magazine, by Anna Gilbert, Martin Strauss and Joel Tropp who took our complicated algorithms and developed it into a workable psuedocode.
• Going beyond the above, there is a very nice, recent, related work by Haitham Hassanieh, Piotr Indyk ,Dina Katabi, and Eric Price in which they improve FFT for k-sparse signals. This is big. See their page on sFFT for details. This paper got a lot of press (eg., IEEE Spectrum news, authors promise code soon), deservedly.
  

Scienceography Contd

The Scienceography paper will appear in FUN 2012. Since our scienceography paper studies among other things comments in the latex version of papers in arxivs and our paper was uploaded to arxivs, self referentiality demanded that of course we leave a sneaky comment in our paper! Those who discovered the comment and followed it through were part of an interesting experiment. :)

ps: People have suggested many things for us to study, thanks for the suggestions, we will follow up.

Sneaking into Cities

I sneaked into cities the past few days.

• First there was Paris, I have never seen another culture so obviously and immediately focused on being creative or different. The undulating escalators and angled tube walkways of CDG is the first signal as you land in Paris.
• Then, there was NY, where I thought I heard a man in a bar say when asked what he wanted in a city (I may have heard it wrong, but I like my version), "Nothing much, a decent newspaper, folks to make the news in it, and when I put my hand up at the street corner, there should be a taxi,"
• Finally, there was Las Vegas, I came back with the stink of cigarettes from the carpets and not a mot in sight.

NITRD Symposium in DC

This week there is the invitation-only symposium in Washington, DC, that explores the accomplishments and prospects of the coordinated effort -- now referred to as the Federal Networking and Information Technology Research and Development (NITRD) Program, and involving 15 Federal agencies as full partners. The program seems interesting, and seems to represent a great group of agencies (national archives, yes!) with topics from privacy, network security, health, high performance computing and so on. Also, looks like there will be some focus on big data and "big ideas" for the future. Finally, it is all webcast live. Enjoy!

ps: Two decades of game changing breakthroughs in networking and information technology celebrated by this meeting didnt seem to have overlapped with Algorithms/Theory/Databases, may be the next two decades will be different?

pps: Btw, check out the invitation-only symposium, "Computing Research that Changed the World: Reflections and Perspectives," at the Library of Congress in 2009. Great speakers, and their talks are online.

On How Science gets Written

Here is a recent research. The starting point is the observation that arXiv stores papers in LaTeX form! So we crawl them and analyze what we can mine from LaTeX form --- the “source code” of scientific papers --- that is difficult or impossible to do with the "finished product" like PDF or PS (think "comments" for example. :)). Beyond this amusement, there is a bigger point: there is a large pipeline of how science is

• conceived (apple hits Newton's head or Archimedes runs the streets of Syracusa: the stuff for science novels),
  
• executed (experiments, proofs in cafes: stuff that movies show with soundtrack),
  
• communicated (written, published, presented) and
  
• ultimately impacts the world (citation analysis, analysis of social network of researchers: the stuff that holds academia together).

Traditionally, we have little visibility into large parts of this pipeline; our argument is that now with emerging large scale data, we can make study of this pipeline itself an object of principled study.

We focus on how science is written, an area we call Scienceography. Our study identifies broad patterns and trends in two example areas—computer science and mathematics—as well as highlights key differences in the way that science is written in these fields. (Party Puzzle: What math operator symbol is most commonly used in CS vs Math?). Comments/suggestions for other studies very welcome (yes, this is only the beginning). Also, serious caveat: this is a data analysis paper, don't expect well packaged principles or theorems.

On Compression

Compression is a research area with many branches. I will focus on lossless compression; lossy compression has a huge history with its recent renaissance thanks to compressed sensing, not-too-recent resurgence due to wavelets for image and video standards, and other constant hums.

In lossless compression, there was the early pioneering work of Lempel-Ziv (LZ) in 70's. Since then there have been various extensions: Ziv worked on extending the"context" into various forms of universality; LZ method got applied to objects other than strings, from file versions to tables, graphs, web, grammars, etc; heuristics were developed using different chunking techniques or suitable dictionaries; and so on. But the general consensus when you spoke to people is that at the highest level, compression involved replacing copies of an object with references to a single copy, and you can perhaps eke out some small constant factor tradeoffs, but no further.

Are there major breakthroughs in compression? Doubtless one breakthrough has been the Burrows-Wheeler (BW) approach. The first time I saw it was in mid 90's and it was very unusual, almost magical. I couldnt tell how far this method will go. Now, not only is this a commonly used compression scheme based on BW (bzip), but we have clear theoretical analysis of its compression ratio which is asymptotically better than LZ, and interestingly, it has been used for indexing and made available in far more applications than LZ or simply compression. That is a good story of Algorithms in the Field.

I am working on next steps following the last year's workshop on Algorithms in the Field (8F), and to determine if there are other brewing new ideas in compression.

Travel and Art

Here is the challenge: Visit all eleven Gagosian Gallery locations --- NY to Europe to Hong Kong and back via LA --- during the exhibition The Complete Spot Paintings 1986–2011 and receive a signed spot print by Damien Hirst, dedicated personally to you. My zany friend Gilles did this, go Gilles! What of Damien Hirst? New Yorker says, "Buying one, you can hang it on your wall like a framed diploma from Smartypants U."

Summer School on Market Design

XIII Summer School organized by the Department of Economics of the University of Trento (Italy) will be during 25 June - 06 July 2012, on “Market Design: Theory and Pragmatics”. Students, post-docs and visitors who are interested will get more information about the application process here; the deadline is March 17.

On Sadness and Other Topics

I am reminded of The Prophet who prepares to leave and people gather around him, ask him to address the issues of human condition. Anyway, here is something on human condition.

• What of sadness? In Congo, they have delestage (literally power cut, in french): Older children eat today, young one tomorrow, some days all children eat and no adults, some days only adults. "If today we eat, tomorrow we'll drink tea".
• What of struggle? Children in the picture cross the Ciberang River clinging to the remaining side of a collapsed bridge to get to their school.
• What of love? I am reminded of an old quote, "Love is the moment when a man who needs shave becomes the man with a beard." Let me add, "And Love is also the moment when a man with a beard becomes the man who needs a shave".

Google Updates

Google announced on Thursday in their earnings call that: "In addition to the $5 billion run rate for display, Google reported that its DoubleClick ad exchange had 130% growth in spending year-over-year. One driver of display growth was marketer interest in buying for specific audience categories -- such as hybrid-car buyers or adventure travelers -- which the technology now can target, according to SVP-Advertising Susan Wojcicki." So AdX is growing.

I have been playing with interactive graphing built into Google search. I enjoy typing in functions like sin(1/x)+x^2 = in the box and playing with the graph, zooming, reading off values, etc. (sometimes you see a little message at the bottom, if the function is not plotted correctly and an explanation why).

EPFL visit

I managed to make it to EPFL, Lausanne, a few months ago. EPFL has a great collection of researchers in communication/information theory, and it is always a pleasure to visit:

• I discussed with Jean-Pierre Hubaux and Nevena Vratonjic about privacy and security in online advertising. They have a paper that studies the following question. ISPs can (a) cooperate with ad networks with direct traffic as usual, or (b) modify the traffic on the fly such that can divert part of the online advertising revenue for themselves. If this diversion becomes material, ad networks can secure the connection so ISPs can not divert the traffic. The paper studies the game theory between ISPs and ad networks and figures out the various equilibria.
• I discussed the problem of identifying the same people/nodes/personas in two social networks, this is a popular problem to data mining community with no principled approach I know. Mathias (Matt) Grossglauser and Pedram Pedarsani take an interesting approach to this problem. Say there is an underlying network is an instance of G(n,p), the standard random graph. Consider G1 and G2, driving from the this instance by sampling each edge with prob s. Then, given only G1 and G2, can one retrieve the mapping of identical nodes? This is a coding theoretic way to approach the problem. The authors show that under certain conditions dependent on n,p and s, one can retrieve the entire mapping!

Matt, who has returned to EPFL after several years heading Nokia Research, was a great host and we were two geeks in the sauna, sweating, but still discussing puzzles. Over one dinner, I talked with Patrick Thiran and Martin Vetterli about compressed sensing and other problems. Over the other dinner, I discussed with the highly energetic Christoph Koch (who has meandered through research in logic to XML and databases) about theory and databases, and eventually debated the issue: does a research community like theory or databases tend to largely agree each year on how to rank the star candidates on the job market? And what does it mean, when the rank orders differ. I also had a great discussion with Katerina Argyraki about some streaming network measurement questions I should really think about. Some of the discussions veered to good natured debate whether international conferences had a strong US vs EU bias.

Lausanne has Art. One of my favorite ``museums'' in the world is collection de l'Art Brut at Lausanne, but I didnt get a chance to visit. Matt and I had a magic moment at Fondation de l'Hermitage when we stumbled onto a room full of crates marked Van Gogh, Bonnard, Vallotton etc. (obviously crates destined to deliver the masterpieces!). Finally, since the last time I was at Lausanne, the campus has a new building, the incredible, innovative Rolex Learning Center: a great fluid, undulating space that naturally finds sectional uses without explicit interior walls.

India: Good, Bad, and Beyond

There is the good in India: wireless access is a great success story, despite the general inefficiency, nearly everyone has cellphones, they work, and they are affordable (even for data, I pay $10 for 4GB).

Then, there is the bad: the various forms that need to be filled out drive people and clerks to panic, and ultimately to a statis: what goes in these ambiguous fields, do the signatures match precisely, is the form/check/currency torn/creased somewhere, and so on.

Finally, there is the beyond bad: people wall their houses, office buildings, and keep things clean within their ``personal'' space, but discard trash just over the walls on to the ``public'' space. Often neighbors swap trash onto each others' public spaces! Forget microloans, I would love to see an economically viable model to collect and process trash in India.

In pictures: food with many dishes; "how to calculate your mortgage payment" by a local newspaper; two trees help announce the theory day.

India Theory Day

Satya Lokam, Ravi Kannan and others at MSR hosted the India Theory Day at Bangalore. It is a little spooky to fly several hours, drive to some office, see Kunal Talwar, George Varghese, Deeparnab Chakrabarty, Amit Deshpande, and others from a more immediate context in my working mind.

Eva Tardos spoke about the Generalized Second Price (GSP) auction. She reviewed by now well-known analyses of GSP that PoS=1 and PoA is like 1.6 or 1.2 depending. Her talk focused on the role of uncertainty. In particular, assuming separability, bidder i in position j will get expected value \alpha_i \beta_j v_i where \alpha_i depends on bidder, \beta_j on the position. While bidder i knows value v_i, they dont know the other parameters, and even if they know the distribution of these parameters, they dont know the instantiation of the click probability in any particular auction. In presence of this uncertainty, GSP does not have efficient Nash equilibrium, and the result was that PoA is bounded by like 2.93. The O(1) PoA result is easy to motivate by considering the shading strategy of letting bid of i be v_i/2 (the best bound needs a more detailed strategy). Likewise, this strategy also has direct no-regret learning interpretation, and similar results follow for revenue as well under MHR assumption like Myerson. This research is much-needed, GSP is widely used and it is remarkable how little we know about it.

Other speakers: Mike Saks spoke about his very nice results on finding LIS in sampling and streaming models; Amit Kumar gave a near encyclopedic discussion of approximate clustering; Alas, I missed Nikhil Bansal's talk on randomized rounding; Nisheeth Vishnoi gave a short, rapid talk on closest vector problems with preprocessing, his brain seemingly whirring even as he stated complicated results.

On the earlier day, I gave a general introductory talk on ad auctions and met several researchers from other areas (Venkat: talked about difficulties of localizing even with compass and accelerometer, Kumaran: translating Indian languages; Sriram: language verification). Over dinner, we debated what was the great intellectutal work of 20th century: Einstein's, Turing's or Watson-Crick's? Deeparnab stretched with the observation that Einstein's work will be relevant even if there were non-carbon lifeforms!

NII Shonan Meeting: Social

Socially, Japan is awesome. I took an evening off to look for Yasuda's new sushi place in Tokyo with my friend Luigi. Alas, I failed (btw Jun Tarui may have found the true one), but an arbitrary couple we stopped to ask about good restaurants in the neighborhood, walked us around to show us several restaurants for us to pick (we protested we didn't want to interrupt their evening plans, they said, "We ate a large meal, we need to walk it off anyway!").

What is International travel without movies on the airplane? I watched Egyptian movie, Al Kebar: this was reminiscent of 70's bollywood, men and women, friends and love, caught across the lines of law. The consensus in US is that Egypt has the potential to be a top 10 Economy within the next 10 years, this movie is just the past.

Finally, sundries: a superb calligraphic exhibition at the National Art Center in Tokyo; fruits, individually sweatered; and, a symmetric gallery of chopsticks.

NII Shonan Meeting: Work

Suresh has blogged extensively about the workshop on large scale distributed computing, so I have only \eps to add. Btw, talk abstracts and slides can be found here.

At high level, there were three models discussed: streaming (S); mapreduce/DHTs based computing (M); distributed, continuous monitoring (DCM). New variations of these models continue to be identified, and while probably algorithmic techniques for S are probably the most developed, increasingly more results are appearing in M and DCM. Eventually, it will be nice to see some general reductions and relationships between these models. There were several database researchers at the meeting.

About specific problems: Qin Zhang talked about tight bounds for various frequency moments in DCM closing out several open problems; Amr Abbadi rose to the occasion to engage the theoretician by posing a simple social network based variants of heavy hitters that is challenging; Suresh spoke about a nice formulation of distributed learning. Minos Garofalakis talked about some nifty prediction schemes so that individual, distributed sensors need to hardly send any bits to the center, and yet the center can track sophisticated functions on the sensor readings. I liked Amr's comment how DCM is related to view maintenance in databases.