my slice of pizza

Summer School on Market Design

2012-01-31T06:11:00.000-08:00

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

2012-01-21T22:07:00.000-08:00

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

2012-01-21T19:25:00.000-08:00

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

2012-01-21T15:24:00.001-08:00

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

2012-01-21T13:51:00.000-08:00

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

2012-01-21T12:44:00.000-08:00

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

2012-01-21T12:06:00.000-08:00

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

2012-01-21T10:06:00.001-08:00

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.

Rain Talk: Security Games

2011-12-24T09:20:00.001-08:00

Vincent Conitzer --- who, as Ashish pointed out, is a PolyCS person of AI, Theory and Economics --- talked at the RAIN seminar a few weeks ago. I am familiar with Milind Tambe's work at USC on game theory + physical security. What is remarkable about that work is that it breaks beyond academia and they have been phenomenally successful in getting their solutions deployed in airports for screening, flights for scheduling air marshals, coast guard inspections and so on. I have always been keen on hearing the research issues involved behind theses achievements and Vincent precisely addressed that and did a great job.

In particular, he focused on security games and asked: what equilibrium should one select? How does one model temporal/information structure? What are suitable structures for utility functions? And, do algorithms scale? Security strategies can be observed by intruders and thus this setting can be formalized as a commitment game where one party goes first and commits to a strategy and the other picks a strategy after observing the commitment. Commitment can be to pure or mixed (stackelberg games) strategies and can be viewed as extensive-form games (finite or infinite resp). Vincent described how the optimal mixed strategy can be determined via a set of LPs, and this has nice properties (agrees with Nash in zero-sum, leader has at least as good a payoff as Nash, no equilibrium selection problems, etc). Then Vincent reviewed concepts of correlated equilibria and the associated LP. After that the talk focused on LP for optimal correlated strategy to commit. He also went through several examples of security and resource allocation games, discussed compact LP issues, and so on.

For finale, Vincent had a great slide, pointing out where CS was pushing the boundaries of game theory. It is an amoeba with many protusions. I say, invite Vincent to give a talk, ask him to show you.

Music in Two Parts

2011-12-23T23:04:00.000-08:00

I can't make music, and have little if any music taste. Still, there is music I like. My fave is Woody Guthrie (who should simply be known as The Source). On the left is one of his children's songs. For grownup me, workin hard blues.

Likewise I have no ballet sense. Still, I decided to see The Nutcracker. Seeking something different, I went to the Oakland version, not SF or NY. The show may be light on Fouetté en tournant or tombé, but the production was tight, the Paramount theater was magnificient, costumes deserve a real review from a real local newspaper.

Research Sickness

2011-12-05T15:45:00.000-08:00

In Zen and the Art of Motorcycle Maintenance: An Inquiry into Values, Phaedrus discusses several metaphors about the challenges to doing quality work, be it hiking mountains or maintaining motorcycle repair shops. I was out on the Ocean -- when I am in a self-analysis mode more than usual --- and noticed the following apt metphaor, for doing research: It is difficult to keep ones eyes focused on the horizon, with so many shifting waves that are close.

MassDAL 2.0

2011-12-05T15:08:00.000-08:00

People ask me about my lab (MassDAL for Massive Data Analysis Lab) at Rutgers.

Here is the page as I set up 8+ years ago, so totally web 1.0. During that 1.0 phase, we worked on data streams and blog data analysis; Graham Cormode, a postdoc visitor, went on to greatness; 6 students finished their PhDs and 4 their MS, and you can see at that page where they are now; we collaborated with Narus, AT&T, Telcordia, Sprint, and of course the Govt.

Now, it is 2.0 time. I really should update the page to be more say html 5, and may be call it "BigDAL" in keeping with the fashion. :) Seriously though, we have new batch of students: Alex (Differential Privacy, Discrepancy theory), Brian (Communication graphs analysis), Darja (Ad auctions), Jinyun (Recommendations), Priya (Graph learning), and Qiang (Stochastic streams). We have a Fulbright Scholar visiting: Magdalena Punceva (p2p social networks). We have a spirited team of 7 students analyzing display ads (Aparna, Lavanya, Edan, Shyamsundar, Vinay and Vasisht). Students collaborate with Narus, Technicolor, Google, and of course the Govt. We work on social network analysis, internet ads, data streams, and theory.

Data Challenges

2011-12-03T08:10:00.000-08:00

Here are two recent ones:

Heritage data challenge, the goal is to "identify patients who will be admitted to a hospital within the next year, using historical claims data".
Nokia data challenge, the opportunity is to analyze mobile data. Registration deadline is Dec 7.

Back with Big Data Streams

2011-12-03T05:04:00.001-08:00

I am slowly getting back to thinking about streams. In the past few years, new systems seem to have emerged that process streams.

See the upcoming meeting in NY on Twitter's Cassandra and open source platform Storm (for continuous queries, distributed query processing, fault tolerance)
Yahoo's S4 distributed stream platform which is a "general-purpose, distributed, scalable, partially fault-tolerant, pluggable platform that allows programmers to easily develop applications for processing continuous unbounded streams of data."

SF Personal

2011-11-23T10:35:00.000-08:00

People ask me how I am doing in the Bay Area.

Last night I made it to 2 (out of 3) acts of Giacomo Puccini's Turandot. The Opera is heft and girth in garments and I watched from the box with Champagne on the side. When it ended, the audience leaving the Opera were treated to an opportunistic tenor on the street. SF is a city after all. I jaywalked a few blocks to be additionally sure.

City people have tattoos. In NY, the tattoo is there even if it is unseen, it is deep, and it comes out only when the shirt does. In LA too the tattoo is deep, but the shirt is always out, and so is the tattoo. In SF, the shirt is on, but the tattoo is out and seems shallow so far.

Finally, people ask me if I paint any more. Do I?

Call For Workshops (STOC May 19, 2012, NY)

2011-11-08T11:25:00.000-08:00

On Saturday May 19, immediately preceding the main conference, STOC 2012 will be holding a combined tutorial and workshop day at NYU, with tutorials in the morning and workshops in the afternoon. Call for workshops is here. Details: 2 pages, deadline Dec 2, email to stoc12workshops@gmail.com. The format of workshops is open.

Hiring in Ads

2011-10-30T23:24:00.000-07:00

NYT article that data analysts, mathematicians and engineers are needed to run modern ad machinery:

“You have to get very close to technology,” Ms. Kent-Smith said. “You have to get your hands in it.”

The Ad:tech conference will be held at the Jacob K. Javits Convention Center in Manhattan from Nov. 8 to 10, and will include a panel on how marketers can build a digitally skilled “brand dream team.”

Video hangout with the World: Update

2011-10-30T09:59:00.000-07:00

Last week was the first experiment with two hosts focused on a topic. The topic was Compressed Sensing (CS), and the main host was Igor Carron. There were 10+ people trying to get on the call at various times and not all could get on. Igor was in and out due to technical problems. Bottomline: our technique for video hangout with the world will keep improving, and we need another session later where Igor will have a platform to address the many issues that come up, with his encyclopedic insights into CS.

Last week, we talked about:

Functional CS. Minimize number of measurements needed to not reconstruct the signal, but estimate various functions of the signal. Streaming algorithms can be seen to be in this genre, but they dont provide the typical for-all signals guarantee or provide insights on what is a suitable notion of class of all ``compressible'' signals for a function of interest. Eric Tramel who was in the call and has image analysis background, proposed ``smoothness'' or total variation distance as a function to estimate. Defined as \sum_i (A[i]-A[i-1])^2, this does not seem to be a new problem: it is L_2 norm squared, and inner product. But some variation of this may be of interest. Some old thoughts on functional CS is here.
Linear measurements are the key to compressed sensing. What is the status on building hardware that will do linear measurements from analog signals that is faster/more efficiently than standard Nyquist sampling?
What is the status of CS for arbitrary dictionaries (not necessarily, orthonormal). Did any new algorithmic technique beyond usual pursuit + group testing algorithms get developed?
What are the latest developments in CS for matrix approximation?
What are recent CS conferences? Examples: 1, 2, ..

Lo Lee Ta, The Three Trips

2011-10-29T09:02:00.000-07:00

Long straight hair and glasses framing her face,
her long longs draped over,
she lolled by the tall windows,
with flickering eyelids, hair tugs and occasional smiles,
reading Lolita between sideways looks.

In the morning light of a Saturday at Starbucks on Sharon Heights,
anyone can be Lolita and anybody can be Nabokov.

+ for LA

2011-10-29T08:21:00.000-07:00

On why I connect with LA: murals galore (more like the one on the left). Now, murals and ads, artists and patrons collide.

A New Yorker Snaps

2011-10-22T05:57:00.001-07:00

This new yorker snapped and drove 30+ min to a place called, "a slice of new york" in San Jose. The pizza was 1/3rd as good as in NY and the place used 3 times as many employees as a standard pizza place in NY. I am sure Californians looking for their slice in NY will only get pizza 1/3rd as good as in California, but that will be served with only 1/3rd as many employees. :)

Video Hangout With the World: Expert Guests

2011-10-22T05:42:00.000-07:00

I will have help in the weekly video hangout with the world.

Wed Oct 26: Compressed Sensing blog's Igor Carron will be the maestro discussing compressed sensing: math, algorithms, applications.
Wed Nov 9: Algorithmic Game Theory/Economics blog's Noam Nisan will be the maestro discussing mechanism design, in particular, auctions: ads, combinatorial, whatever.
Wed Nov 16: Polylog blog's Andrew McGregor will be the maestro, discussing data stream algorithms and applications.

I am excited, Igor, Noam and Andrew are experts and I invite people with questions, solutions, discussion points to join us.

Instructions: invite muthubyshance@gmail.com into your circle on your Google+ or email me, I will add you to my video hangout circle; then, at the suitable time, go to our Google+, you will see me hanging out, join the hangout!)
Time: Wednesdays 8 AM -- 9 AM pacific time in US.

Video Hangout With the World, Update

2011-10-19T09:00:00.000-07:00

In the past 3 weeks, we have discussed:

What is a suitable approximation for an SQL query? The point is, the correct output is a multi-set of tuples with several attribute values. A definition of an approximate output is not immediately clear. If one were to define a distance between possible outputs, weighted sum of errors over attributes is not necessarily the most informative. Set similarity is not necessarily the best answer either, for example because attribute values have a meaning. (Say the correct answer is {10,20,30}; {10,20} is a similar set, but {9,19,31} may be a good approximate output.) Some sort of "matching" constraint should be implicit. A related paper is from VLDB 99 by Ioannidis and Poosala called "Histogram-Based Approximation of Set-Valued Query-Answers". There are a lot of nice theory problems lurking here.
What are interesting algorithms problems one can abstract from Informatics Olympiads, math puzzle sites? The solution hopefully involves something more than dynamic programming.
Data structure problems where outputs should be in some specified order. Say the output is of size k, then in O(klog k) additive time, one can output any specified order, assuming output items can be compared. Are there problems where one can do + O(k) only or without knowing k ahead of time?
Specific problems: 2d image listing (rather than document listing) problem. This leads to the following "simpler" problem. Given n lists of length l that can be preprocessed, at query time, k < n lists are identified, and the goal is to output the intersection of these k lists in time like k, log l or poly in that. Any ideas?

We have persevered through bad connections, too many or too few on the hangout and so on, and we are still rolling.

Weekend

2011-10-19T06:47:00.000-07:00

I spent the weekend riding the rocky mountains of Nevada in a 4WD pickup truck. These vehicles, innocent on the Highways, can grip rocks, climb, spin, spit them out and forge ahead, up or down, treading where there are no tracks, just rocks, sage brushes and emptiness managed by the Federal Bureau of Land Management (plus empty shells from guns fired by a few pioneers who had ventured before). Note to self: must get one of these 4WDs!

Palo Alto Talks

2011-10-19T05:24:00.001-07:00

Last week was a whirl of talks.

Bob Tarjan started his lectures on algorithms+data structures with amortized analysis. The simple example of counting the number of bit operations needed to increment n times, led to potential function based analysis and nice exercises of getting worst case bounds (via redundant codes, still with O(log n) bits). Qiqi Yan asked if there was a way to appeal to LP Duality to get worst case bounds in general. Then, Bob introduced different "heap" representations from the standard to tournament (n values are leaves of a tournament), half full (replace winners by empty slots), right full (make all empties the left branch), compressed (keep links to successive winners), and finally to half ordered representation by linking the siblings. Those who know Bob or read his monograph know, he is superbly efficient with his words. I mentored myself from his monograph when I was a graduate student, and this is now an in-person treat!
Vijay Vazirani spoke about markets. He started with the Arrow-Debreu (AD) model that shows that there are prices for a supply that will satisfy every demand and clear the market precisely. This result has many implications and issues (not unique even beyond scaling, pareto optimality, every pareto optimal allocation comes from equilibrium after redistribution of wealth, dynamics? etc). Vijay spoke about his joint work with Kamal Jain on studying this problem with digital goods with no cost to infinite supplies and challenge is to envision a nontrivial market that doesn't allow equilibriums when everyone gets every copy of the digital good. He proposed a model that involved grouping items into semantic categories with full substitutability within each for uniform prices, and a rich context with cardinal and ordinal preferences. Now supply/demand constraints become more intricate, some bundles are forbidden, and the entire edifice of AD has to be reconstructed. This is a grand problem where Vijay's natural ebullience keeps the audience engaged through the myraid details of formulations. He left open even grander problems of pricing items like theorems, financial advice and innovations.

Talks are one-sided. I managed to have two-sided conversations not only with Bob and Vijay, but also Ashish and Tim over dinner. Tim is going through energy spins, waxing and waning with the weekly cycles of his teaching, and he shared a key insight (or two! :)): some textbooks are for professors and others are for students. In Algorithms, we know which is which. My favorite professors' text is the monograph by Dexter Kozen, The Design and Analysis of Algorithms. Ashish, who can quietly float to the top of any topic, described the excitement of molecular machines which can trot along biological material and repair strands.

Shout Out to "Occupy Wall Street"

2011-10-19T05:15:00.000-07:00

This is a shout out. Finally, we hear more voices and narratives in the mix than what has consumed us the past 3 years of this financial mess. We are the 99%! (T-shirts).

RAIN Talk

2011-10-06T22:58:00.000-07:00

Research on Algorithms and Incentives in Networks (RAIN) seminar at Stanford is on Wednesdays. Yesterday, Ashish Goel started off the series for the Academic Year introducing the new faculty (Kostas andMohsen) and introduced the first speaker of the series: Jure Leskovec.

Jure set out the goal nicely. Consider large networks (collaboration, citation, web, telecom whatever). They have some modular structure (overlapping or disjoint clusters), but how do we form a picture of their structure, how do we formalize this picture? He summarized his approach as "computational experiments", that is, start with data, formulate some atomic notions, tweak, identify some initial structure, peel and find more, all the while formulating and solving interesting computational problems on networks.

Technically, he started with conductance of a set of nodes (number of cut edges/sum of degrees) and defined the network conductance profile (NCP) as min conductance for each size k of the set of nodes. You can compute this using spectral, multicommodity flow or SDP techniques, Metis and others. He showed the NCP of many networks (V shaped). Ramesh Johari asked why doesnt the profile contain for each k, the number of sets of size k of nodes that achieve the min conductance. Yoav Shahom asked more generally why not look at the entire distribution of conductance versus sets. A: doesnt change the main observations.Amin Saberi asked whether the picture showed NCP or Intractability profile. A: you can use lower bounds on SDPs and optimizations to convince oneself that the curves are right. He then zoomed in on the down and up parts separately and eventually worked the crowd to figuring out the structure of the network that it has a periphery of "whiskers", you can peel then off (by focusing on largest biconnected components) and you will find similar structure again, and so on. He proceeded to taking labeled data of users belonging to various communities as ground truth, and showed series of analyses of probabilistic parameters of potential models that would generate such networks. Among other things, overlaps of these communities is dense.

Jure is a top data miner and like any good data miner, he is more than the sum of the plots he shows: behind each plot, is the sweat of many other plots and analyses that are mere carcasses on the way.

NAE Frontiers Meeting

2011-10-02T08:31:00.000-07:00

The National Academy of Engineering (NAE) runs a Frontiers of Engg (FOE) meeting annually at the Beckman center in Irvine, with 100+ bright engineers from bio to brick+martar, computers and beyond, interacting with each other over 2.5 days. I was in this main meeting in 2002 (found it intellectually very exciting), and also the US/German version a few years later.

They have a US version of the FOE. It was recently held in Mountain View, CA, at the Google headquarters. At NAE, Janet Hunziker has been quarterbacking these meetings for a long time, and at Google, Lisa McCracken who handles so many of our CS conferences so effectively, stepped up, and together they seemed to have pulled off an awesome meeting. When NAE discussed 2011 version four years ago, I connected them with Google, so I scored a ticket to the reception dinner and got to meet the participants (Michael Cafarella, Evgeniy Gabrilovich and Lisa Zhang from our communities were invited to the meeting, among others).

Alfred Spector was the dinner speaker. He started with the observation that in early days of CS, it was 50% math, logical proofs and analytics (think Knuth, Dijkstra), now it is large % empirical, more like natural sciences, because we use and enable an external world. A good example is spelling correction, which morphed from (dictionaries, cognitive sciences, algorithms) -> (large data, parallelism) in an experiment with the world. He switched to discussing set of n grams from books in the history, study of regular vs irregular words, changes in uses of words, and eventually to laying out the agenda of "Digital Humanties" that CS researchers are carving. He went on to discuss various challenges like security, healthcare, education (individualize education?), etc. Questions from the audience: state of electrical power measurement by Google; why doesnt Google keep up healthcare software for people who continue to want it even though it is discontinued; personalization in larger, search context? comment; future of smartphone?; you provide sketch, language, picture, video tools. When will 3D and shapes be more prevalent? A: Chrome supports 3D. Alfred, already a NAW Fellow, is a virtuoso, his talk and answers were well calibrated, he timed it to catch his flight straight after the talk.

Quote from Thomas Edison on the dinner menu: "Everything comes to him who hustles while he waits." So I hustled after the dinner.

Quick NY Trip

2011-09-28T04:03:00.000-07:00

I had the guilty pleasure of a 2 days trip to NY city. My many thanks to the students who schlepped up to the city to work with me. Also, I walked into my favorite bagel place, and the owner says, "havent seen you a few days", and gives me my coffee -- 8 Oz, black, no sugar -- and my dollar back.

Managed to watch an "oldie" (of 1 year): cave of forgotten dreams, a 3D look into the Chauvet cave, charcoal cave paintings from 20k+ years ago by humans. The drawings are awesome, but the voice-over and the focus of the director and the film to dramatize the sociological aspects is really distracting. I was mostly focused on the technical aspects: was it one artist or many? different styles and strokes? any "erasure" and "modification" marks, or paintings the artist wanted to abandon or paintover? why didnt they paint plants and people, flowers and natural scenery, but only overwhelmingly horses and bison? etc.

Being in NY is about seeing things new. I watched the California is a place video about skateboarding in pools of foreclosed homes, cooawl!

War of References

2011-09-24T16:02:00.000-07:00

My post on Biases in References generated email and real conversations and one phenomenon that got abstracted:

Authors submit their paper q to a conf citing a paper p very prominently giving credit for prior work;
q gets accepted, authors submit a camera ready version with lukewarm reference to p making it sound contemporaneous;
After a few months/years, q is submitted, accepted and appears in the journal version, references to p now missing or p made to appear irrelevant.

The scenario above may be an extreme, but there seems to the case of citations that morph in tone, substance or even existence from submission to camera-ready to journal appearance of a paper.

Video Hangout Update

2011-09-24T15:31:00.001-07:00

My experiment of being on Google+ video hangout with the world for an hour each week is on. We have discussed:

Algorithms for learning a matching in graphs.
Algorithms for top k under funky similarity measures.
Algorithmic issues in H-index and its variants.
Is there any dataset in Computational Biology that needs a MapReduce system?
Stochastic histogram approximations.

What hasnt worked so far:

People seem to invite me on my regular gmail and not the one I set up for this purpose: muthubyshance@gmail.com (Instructions: invite muthubyshance@gmail.com into your circle on your Google+ or email me, I will add you to my video hangout circle; then, at the suitable time, go to our Google+, you will see me hanging out, join the hangout!)
Hangout time does not work for some, so people have been reaching out to me out of band.

Here are new parameters.

No hangout this Wednesday Sept 28, next hangout will be Oct 5.
From now on, hangouts will be Wednesdays 8--9 CA time, 11--12 NY Time.
I am considering the idea of having hangouts on specific topics in the future: MapReduce algorithms, Compressed Sensing and sparse approximation algorithms, Differental Privacy and its Extensions, Revenue optimal mechanisms, Ad Exchanges: new problems, etc, Any feedback will be highly appreciated.

BWCA Notes

2011-09-24T13:54:00.000-07:00

Here are very rough notes on Day 1. Tim tells me videos will be posted soon.

------
Tim started the workshop stating that Stanford Univ was doing a focused year of activity on theory of CS, and mentioned there will be workshops on social network algorithms and expanders in the future.

Avrim spoke about the premise that the objective we optimize in problems is usually a proxy for some underlying target. Assume: all c-approx are \eps close to desired target (eg., clustering to 1+\eps gives good grouping of proteins by functions). An example result [Blum, Balcan, Gupta 99] is then for c>1, can get O(\eps) close to target. He posed several open problems to attack this way: sparsest cut (focus on application to image processing, segment/partition. What if we assume that 10 approx has error \eps for image segmentation?), phylogenetic trees, other assumptions? (eg., most c-approx are close to the target), for "easy" problems, given arbitrary instance, find stable "portions" of solution. Eg., Bilu-Linial perturbation-stablity notion. Some of the questions: q1: as they say, clustering is either easy or not interesting. comments? A: key is difference between error and opt metric, not clustering opt per se. Alex q: are there smooth versions? like as property goes from structure to arbitrary, runing time automatically adjusts from quick to fast? A: Maybe look at PTAS examples? q: Is approx-stabilty a rare property? A meta theory? Therefore we should not use approx at all. A: Clustering does NOT have to be hard, so a formulation that makes it easy is not immediately challenging to the establishment. Tim: Any hardness results? So, the assumption is not too strong? Avrim is a researcher can drive the car with two gas pedals, one for math/CS techniques, one for formulation/abstraction/philosophy and can put the foot down on both or either as needed.

Nicole Immorlica spoke about PASS approximations, through the example of facility location. She made a clear argument that you wanted to consider variations that assume some property of the solution (not the instance). Cited the Kleinberg, Papadimitriou and Raghavan paper on catalog segmentation as an early example. She then described the PASS Framework: take a signature of the solution: for each facility, q_i, alpha_i, consider the recoverable value as a function of the signature, and do analysis in these terms. Greedy/LP gives additive error guarantees per facility, and provides guidance on choice of heuristics. Nicole is a clear speaker, often using simple examples to make the point.

Nina Balcan spoke about a very nice area, developing a discriminative theory of semi-supervised learning. Unlabeled data helps in many ways (self consistency, throw out hypotheses etc). Propose a new model. concept class + compatibility between the concept and data distribution. learn not C, but C under compatibility. Gives nice algorithms: First consider unlabeled data, choose a rep from a set of compatible hypotheses, then use labeled example to choose among these. How much unlabeled data is needed, how much can unlabeled data reduce number of labeled data needed? Pointed to Zhu survey 2010. Kakade, COLT 2008. q: Does this theory extent to active learning (where you get to pick questions)? Yes. Need to combine with compatiblity constraints. q: any killer applications? q: anything to choose from transitive SVM and … for any instance. A: run them in parallel and stop when justified.

Spielman spoke after lunch on smoothed complexity. He spoke about the role of the condition number in a phenomenally illustrative way. Theroem: ill conditioned ifff some row is near the span of the others. Eckert+Young: cond no = 1/distance to singular. Another condition no= ||A|| ||A^-1|| where || || is Frobenius. Gaussian elimination without pivoting: entires may not get large when submatrices are not ill-conditioned. matlab demo to show Gaussian elimination sucks. Towards the end of the talk, he spoke about solving set of polynomial equations, solving: n eq , degree d. a point in which Newton converges quadratically. (Smale def) Bezout theorem says many solutions. NP Hard. SAT x_i (1-x_i)=1 is poly clause. Recent result is a poly smoothed complexity. Result sounded amazing, need to follow up. Dan's talk and work makes theory research inspiring, as someone in the audience observed later, and no doubt others felt the same way.

After a break (I fell asleep some during the talks, I was tired, apologies to the speakers), Andrew Goldberg spoke about shortest path problems. The message was that there is science of algorithms: do, implement, observe, test, tweak, realgorithmize, and so on. In a great example of what algorithms research can do when thrown at a basic problem, Andrew gave a series of improvements to shortest path computations in particular, as they applied to road networks and map queries, relating VC Dimension to the complexity (HW: Unique shortest Path system in graphs has VC dimension \leq 2.) In road networks, there are transit edges which are natural and important and cut down on shortest paths to consider, store and compute with. Dijkistra's takes 2s for 18M vertices. Result now << 1s. q: Alex: reproducible experiments, are these reproducible?

Susanne Albers spoke about online competitive analysis. Paging, with resource augmentation. Paging/ k/k-h+1 competitive if OPT has h <= k pages for alg. For list update problem, proposed and analyzed a new locality model based on runs. q: Aranyak: What benchmark for running scheduling expos? A: Hard. sometimes need deadlines for energy efficiency. Tim: How many of these online algorithms are ideas that have usefulness elsewhere? online ad allocation will be an example.
----
Altogther, I thought the quality of the talks was very high on the first day. I could not follow the workshop with as much attention as it deserved on the second and third days (it was vaguely unsettling to hear Richard Karp talk using ppt slides. :))

BWCA at Stanford

2011-09-18T19:03:00.000-07:00

Beyond worst case analysis workshop starts tomorrow. Tim and Luca have put together a superlative program. I hope to learn as well as meet friends from afar, in time and space.

Life after a Tweet

2011-09-18T18:31:00.000-07:00

A tweet is short (and I am told, in china too, its substitute like Sina Weibo has a 140 characters upper bound! :)) and real time. What interests is life after the tweet.

When US went into Pakistan, US forces had practiced, had plenty of firepower and stealth, backup fighting force and eyes on the sky, I am sure. As we all now know, there was someone tweeting about the choppers even as the operation was underway, raising a severe security issue. Should US have considered shutting down twitter for an hour as a standard operational procedure before going in?
Then I heard the story of this woman on the radio who was unhappy with the service at the bar and tweeted. A few minutes later, the manager comes to the bar and escorts her out! Life after the tweet is also swift.

NYCE from Far

2011-09-16T14:45:00.000-07:00

NYCE in NY did take place and thanks to Gagan Goel, I managed to get the gestalt of being there (although alas, I had to miss the afternoon talks).

Research Real Estate

2011-09-16T14:41:00.000-07:00

Here is the view from our own Nitish Korula's office at Google Research, NY.

NYCE IV

2011-09-14T07:32:00.000-07:00

Thanks to the organizers Gagan, Mallesh, Richard, Sharad and Xi, NY area CS and Economics (NYCE) day is this Friday. The organizers have done a splendid job of recruiting a new space: NYU's Kimmel Center in the village.

There is a great set of speakers : Vincent Conitzer, Jonathan Levin, Preston McAfee, David Parkes, and Eva Tardos. The call for rump session talks/submissions has been vastly oversubscribed, so I expect a large participation. Alas, I wont be in NY this time physically.

Biases in References

2011-09-13T16:30:00.001-07:00

There is a lot of work on bibliographics. Is there a good study of the biases in references in research papers?

There are many, many ways to subtly over or under represent prior/earliest work. One might

not cite a prior work where it is needed, or
cite a later work while an earlier work is more appropriate, or
cite all relevant work but weight improperly by say placing a later work at the same level as the earliest work, by repeating references to a later work more, or slant natural language discussion towards the later work, and so on.

This may be done for

selfish reasons (self-citations),
social reasons (citations to students, friends, colleagues or ones we trust or know), or
antagonistic reasons (jealousy towards a perceived peer, animosity towards someone for a perceived past slight, competition with another group, and so on).

I see a lot of work on bias in the scientific opinion of an author, or bias in selection and so on, but very little on biases in references or systematic ways to analyze and quantify them.

Algorithmicist in the Field: Google+ Weekly

2011-09-04T12:07:00.000-07:00

Labor day weekend is a good landmark, interns are gone and stalled projects in research labs will restart; students are back at universities and new semester will begin; summer will end and fall will burst out; it is time for last hikes and new beginnings, etc.

I will be on video hangout on Google+ every week, Wednesdays 9 AM -- 10 AM EDT (NY Time). Anyone can join me on the hangout. The idea is, we can talk algorithms in theory, systems, field or otherwise; we can talk problems, solutions, patents, techniques or angst about the state of the world; we can look ahead and seek directions or look behind and summarize; we can talk courses, careers, conferences or about the cult of research; we can be students, professors, researchers, and be in any part of the world.

What you need to do, if you want to join me in my hangout:

Have a google+ account. If you dont have one, get an invite or email me at muthubyshance@gmail.com.
Go to Google+, add me (muthubyshance) to your circle and join my hangout anytime during the period specified above. If you cant find me or have problems, email me at muthubyshance@gmail.com. You will also get updates from me on google+ if I am in one of your circles.

This is obviously an experiment, but for some time, I wanted a channel to have real time conversation about our issues in addition to the existing channels of the single speaker on the pulpit mode (blogs/lectures) or the post and seek mode (of cstheory.stackexchange.com) or hunt and find the proper subset of people mode (of live conferences).

ps: This will start on Wed, Sept 7.

Two Algorithmic Problems

2011-09-04T06:31:00.000-07:00

Sometimes, an applied problem brings up a technical problem, simple or not, and it is fun. Here are two examples (from social networks):

Given an undirected graph G, output a set S of vertices (the neighbor-dominating set) so that each edge should have at least one common neighbor in S if the endpoints are not in S. This sounds related to vertex cover, dominating set etc., and there is a simple log approximation possible. The problem arose in an interesting proposal for decentralized social networks (as opposed to centralized ones like facebook) by my colleagues Lu Han, Liviu Iftode and Badri Nath of Rutgers CS and the paper will appear in the upcoming Social Computing 2011 conference.
Given a directed graph G, determine a mapping r from vertices to set of integers such that sum_{(u,v)\in E} max(r(u) − r(v) + 1,0) is minimized. The interpretation is as follows (and arose due to the work of my collagues Mangesh Gupte, Liviu Iftode and Pravin Shankar of Rutgers CS and REU visitor Jing Li): In social networks, where nodes are aware of their ranks, higher rank nodes are less likely to connect to lower rank nodes. Hence, directed edges that go from lower rank nodes to higher rank nodes are more prevalent than edges that go in the other direction. In particular, if r(u) < r(v) then, edge u → v is expected and does not cause any “agony” to u. However, if r(u) ≥ r(v), then edge u → v causes agony to the user u and the amount of agony depends on the difference between their ranks. We posit that the agony caused to u by each such reverse edge is equal to r(u) − r(v) + 1 (+1 is for technical reasons). Then the problem of finding best social hierarchy can be stated as above. Unlike a related way to formalize this problem as feedback arc set problem, this problem is solvable in polynomial time as we show in the paper that appears in WWW 2011.

VLDB 2011 Notes

2011-09-03T20:27:00.000-07:00

I managed to make it to VLDB at Seattle. The travel this time --- from SFO to SEA --- was a treat, with a taxi ride with Raghu, discussing what each of us were looking forward to learn at VLDB. On Tuesday, I got there in time for the receptions, the first hosted by Microsoft in the evening, and the second, hosted by Google, later. The party continued later, later. I stayed at Mayflower Park, an old fashioned hotel with, as is standard, grand lobby, a highly helpful bartender at the bar in the corner, staff in glittering buttons, and small rooms.

On Wednesday, David Campbell gave a plenary talk. He said that there was data ambient, models and modeling methods rare, and one could be very creative with questions. He used the example of ``digital shoebox'', dropping in all the data one could collect say with their smartphone, and interesting analyses you could do with the shoebox ("can you figure out how much time you spend in Florida in a year for tax purpose."). One in the audience asked, "what about digital shipping container?", that is, when you get data from many, will methods scale? He also spoke about the lifecycle of a query, how to validate data, hypotheses, etc. Audience asked about DB concerns, what happens when models change, patterns mature, how to admin the DB.

I attended the panel on maximizing impact with Ed Lazowska, David DeWitt, Juliana Freire, Ed Lazowska, Sam Madden, and Jennifer Widom.

Ed set up the discussion with pointing to the article of Bob Lucky about the diminishing influence of electrical engineers, and the iconic last engineer on the planet. Is that where database engineers are, even though this is the decade of data? He also pointed the audience to kaggle for data analysis competitions.
Sam did the crowdpleasing exercise of wordling VLDB paper titles for the past three decades and no one resisted the temptation to draw conclusions. Then he did a crowdsourcing exercise of (a) getting list of top 10 impactful ideas/achievements in database research in the past 10 years, and (b) top 10 new ideas for the future. Stream processing made top 4 in (a), yesss! In (b), there were several suggestions, including "data crumbs" by Alon Halevy, of anlayzing data we leave behind during our trail on the web.
Jennifer then led the discussion, focusing more on education and visibility. Why is AI or machine learning more popular than databases research among incoming student in this decade of data? The explanation was technical (students dont know real world and dont see the need for DB until much later) to marketing (students see driver-less car as AI, that is great image; in contrast, as Natasha put it, the DB product feels like a screwdriver or laptop, not necessarily fun), self-reflecting (shouldnt we take responsibility to go from data analysis ideas to eventual studies and code in an applied area) and educational (better examples than the employee/student example in text books). Joe Hellerstein, who has the incredible ability to capture and keep the intellectual attention of the crowd, kept the conversation focused on what DB community has to offer: getting inspiring ideas from other communities, doing DB magic of declarative languages, parallelization tools, etc. He also called for a simple language to teach DB basics and early programming in undergraduate days.
David steered the conversation towards the positives (DB students are finding jobs, startups companies are making deals, 50B database community is humming, etc) and lamented the challenges of having impact in practice, even in Industry.

The panel made sure the conversation did not turn to remaking conferences, and the panel dissolved into multiple conversations in the hallways. Should we be following developments at NoSQL conference?

Had terrific conversations with Amr, Divy, Hector, Laks, Joe H, and Surajit about research, and with Amol and Jignesh, about challenges of mentoring students.

100k+ Theory Students in the class?

2011-09-01T21:37:00.000-07:00

Stanford is running an experiment with free online courses in AI (by Peter Norvig and Sebastian Thrun) with 100k+ students, databases (by Jennifer Widom) with 40k+ students and machine learning (by Andrew Ng) with 40k+ students worldwide. Where is the free online course on Algorithms and Theory? These courses will have homeworks, office hours and grades.

West Coast Thoughts

2011-08-09T22:26:00.000-07:00

After scouring for cheeses, let me say: I hope someone does to Manchego what Sideways did to Merlot.

Moving means gifts, and I told a friend: Keep the gift close, keep the gifter closer.

The other day, I was in San Francisco and Google maps told me it was a 30 min walk to where I was meeting my friend. I thought, well, normal NY walk is twice as fast as locals and I can speed up some, so figured it will take me 10 min. Turned out it took 22 min. My explanation? Google maps personalizes directions and estimates, but didnt know I was going to speed up! :)

Personal: NY and Palo Alto

2011-08-01T01:52:00.000-07:00

As friends know, I recently moved to Palo Alto, CA, in a brave experiment in west coast living for a few months. I have always thought of myself as a mutt of a man, being able to pick up the worst traits of wherever I have lived, and if trend persists, I will internalize some of PA, CA.

Meanwhile, I wrestled some rare time off work and life, and managed to see:

Midnight in Paris. I am a Woody Allen fan and seeing his personal strides though the filmmaking landscape is always interesting. I was tickled by this movie. Who wont be, if you can ask Hemmingway for writing tips, or dine with Dali, or have Gertrude Stein as a critic, or need I say it, have Marion Cotillard as the muse. Here is NY times review, a little disappointing, it lays out the plot and does not quite decode Owen Wilson playing Woody. Btw, Woody, you should have done the Harlem Renaissance version!
Thanks to my friend Virginia, I saw Elko and Koma at the Lincoln Center. A fantastic outdoors dance performance on the reflecting pool. Incredibly slow movements (rippleless even floating away) as each performer in deadly white mask and wisp of clothing set the drama, come together to strike arched poses under the shadow of Henry Moore and the airplanes overhead, and eventually float away as exquisite flotsam and play out a sepulchral act, complete with floating candles, incense and drum beats (which reminded me of trips through Louisiana swamps). Here is the NY times review.

Teaching

2011-07-31T08:29:00.001-07:00

It occurred to me --- talking to professors about their students and labs researchers about their interns --- that there is a tendency to help those who can swim to swim faster and further, but how much do we help drowning students get ashore (at grad school level)?

Personal: Parenthood

2011-07-31T08:22:00.001-07:00

Friends ask me how is parenthood. Like grapes. When I was little, even though I dont recall it, I am sure my parents peeled the skin and deseeded each grape for me. Later, when I was a youth, even if I dont recall it, I must have picked grapes off for my romantic interest and shared a moment of togetherness like in music videos. These days, as a parent, I watch the kid so she doesnt choke on a grape, and eat whatever is left over so the plates can be washed. And if I had more time, this blog post would have been a haiku.

Algorithms in The Field (Update)

2011-07-31T08:07:00.000-07:00

Some updates:

Algorithms in The Field continues to be in focus. The new call from the Algorithmic Foundations division of NSF has it.
Thanks to Tanya for the tip, there is a center emphasizing "field academics" with an interesting graphic.

People ask me about algorithms in the field, and I say, "it is getting theory and applied researchers working together so early that you can not tell what came first, friends or facebook". :)

Two hats from Twitter

2011-07-31T06:08:00.000-07:00

People observe twitter for various reasons. I recently observed that in the research world, twitter, because of its policies that enable easy data access, has a great mindshare (just search for twi in ICWSM 2011). This blog is about two talks on twitter, by Ashish Goel, with two different hats worn comfortably.

Talk 1 was at Workshop on Ad Auctions on Monetization. He started with the observation that twitter supports both highly individualistic view so you can follow an individual or the aggregated view via tags and trends of many. He spoke about 3 products: promoted accounts (on the right, to follow), tweets in search (on top) and trends (on the right, via hashtags). The guiding philosophy with promotions is that they should conform to user's expectations of tweets and have follow-on effect. Ex, promoted trend leads to conversations, promoted accounts continue to deliver future impressions, promoted tweets lead to retweets, etc. Ashish released some impressive numbers on how these efforts were going, and few examples.

He then spoke about challenges. On the strategic side, there is need for novel promotion ideas. Twitter is not about time spent on the site, so these should be beyond display ads, and encourage twitter experience and follow-on. On the algorithm side, challenge is to work with a short window of time/data, and estimate one's current interest as well as estimate future follow-on effects of promotions, machine learning at the speed of thoughts/tweets. On the auction side, the challenge is to design pricing and allocation for extremes like promoted trends which has to reach many, and promoted accounts that are highly liquid. This talk was structured perfectly, with an overview of the products, main philosophy shown through the interaction between these products, specific numbers and examples, followed by what the audience wanted, namely, technical challenges. Nearly everyone in the audience appreciated one slide, where Ashish gave examples of suggestions from the research community that will NOT be valuable, these are throwoff ideas like, use keywords in tweets to target ads or show promotions in timeline or offer coupons, etc. Chances are twitter which has smart full time folks thinking about these issues would presumably have analyzed the many immediate suggestions already.

Talk 2 was at SIGMOD, where Ashish gave the keynote industry talk, on data models and management issues at Twitter. He started with the mission statement: instantly connect people everywhere to what's meaningful to them.

Problem 1: How to deliver tweets (several k's a sec, each going to more than avg degree of users, and has to be aggregated into timeline). A natual data model will compile tweets into tuples and apply map and reduce (MR) operations. However one needs some sort of continuous mapreduce (MR) system to be real time, but such systems are mainly in academic stage and robust versions have to be designed and made available at large. You could also discover duplicate tweets with a combination of continuous MR and locality-sensitive hashing (see some inspiration here). Problem 2: Search, real time relevance ranking of users and tweets, personalized. In the future, social graph and resonance scores. Some discussion here. Problem 3: Incremental Pagerank, maintain pagerank as edges, nodes arrive. He referenced the VLDB paper with roughly O(nlog n) solution where n is number of nodes, and m, the number of edges has minimal role, improving on the trivial O(nm).

The second data model Ashish explored for these problems was active DHTs (distributed hash tables with user-specified code) which are like continuous MR but with reducers able to communicate with each other. He then discussed maintaining suitable random walks on social graph via active DHTs (see here for db details) and its uses from incremental to personal pagerank. The third model Ashish spoke about was semi-streaming where there is memory to store row-IDs and some properties, but not all matrix entries. This seemed more suitable than "clever" graph partitioning because social graphs seem to be expanders that change rapidly. Many recommendations problems will be of interest in semi-streaming. He summarized with the excitement of mix of database and algorithmic challenges at Twitter.

Summary: These two talks, juxtaposed in time, were among the most informative and insightful I have heard of a tech business, able to move between sound business and solid technical concepts as needed, a rare and impressive achievement for a theory researcher. Ashish is one of those speakers who you appreciate when you hear their arguments, but with every question you ask, he peels more technical layers, and you appreciate how much more he knows and how much more depth there is, in other words, his talk is more than the total of his slides.

WITAP 11

2011-07-29T09:15:00.000-07:00

Workshop on Internet Tracking, Advertising and Privacy (WiTAP, if you get the pun) took place at Stanford on July 22.

Dan Boneh (who organizers credited with quarterbacking this meeting) started the workshop and introduced the amazing crypto+security group at Stanford, seminar series, mailing list, and link to course notes and certificate course programs.

Bala described his work on busting privacy issues via a series of papers that collect and analyze data, from '06. He said that people dont read papers, but people read WSJ. He talked about things getting worse with each paper, from web to social to mobile. Users assume they interact with first parties (web sites, social networks, telephone companies), but if you dig deeper, for a variety of reasons, second, third and other parties intervene in the conversation between the user and the first party. The reasons for this leakage could be because first parties outsource data collection and analysis for operations or mining or revenue, whatever. He talked about mechanics of leakage: flash cookies that are hard to delete and that respawn; http headers that leak referer/cookie/requestURL; external applications; mobile social networks that leak presence, location and device ID; etc. From leakage, next development may be that aggregators can join across data sources, and beyond this, fingerprint browsers. What can one do? Bala pointed users to the FTC 2010 report on privacy for more awareness. He also pointed toAcquisti's work on separating offline and online identities as well as Economics of privacy. Among questions: research community knows these leakages, why dont public follow? A: May be the tap in UK is a turning point; Privacy expectations are culture specific. A: Study has to correct for countries, china, korea, US.

Ed Felten spoke next, communicated his personal goal to "write a few lines of code everyday" (in my case, when I was a graduate student, the mantra was, "learn one new lemma a day") but talked about his policy work at FTC for monitoring businesses. He communicated how FTC can enforce: deceptive use (misleading claims or use by companies) is easy to regulate, unfair use is harder to define, and in general, before an issue can come up for FTC enforcement, researchers have to go beyond research and develop support from general population for their case.

One of the anticipated talks was by Omar Tawakol of Bluekai. He spoke about how context and sites are no longer the key in Internet advertising, and user data was the new fuel. He stated the premise of his company that data is too much in shadow, consumers are smart and can handle the complexity of data, and how they support opt-out cookies, open source and so on. How much will users pay for ads free: little. He phrased a technical argument that the plumbing you need for (a) user conversion tracking where one measures whether user actually bought/converted some time after seeing an ad, (b) retargeting, the most effective form of advertising after search, where a user seen at once place is targeted elsewhere, and (c ) frequency capping, where an advertiser limits how many times a user sees an ad, are all the same. (a) and (c) are very legitimate uses for advertisers. Does that justify (b) too? Without 3rd party cookies behind (a-c), in particular (b), he claimed that 70--80% of 7B spend on display ads will be at risk. Tradeoff of free content vs ads is not fair because users don't know what they are trading for the free content; if you aren't paying for it, you aren't the customer, you are the product; why don't we turn off targeting?; why not turn off ads altogether? He proposed that these were all good questions. He tried out a technical argument that if 50% turn off ads, other end up paying for their free loaders content and that is not fair. Not clear this argument flies. He said Bluekai has a dashboard so users know what is known about them. He further pointed out that k-anonymity of a dataset does not help quantify the damage when two or more datasets are combined; he argued for some "smart noise" that will obfuscate the data and still keep it useful for advertising. Questions: common pipe may be avoided by doing (a) and (c) at the client browser, without doing (b); q: what is the marginal value of tracking users; etc.

Russell Glass of Bizo spoke about targeting business professionals. He pointed out also that you have to see lot of ads to make small amount of $'s (margins are small in data/display ads). He argued that what the industry needed was certainly regulation, but that will not provide "trust" which is sorely needed.

Dean Hachamovitch spoke about Internet Explorer and argued it was good at blocking malware and pointed to IETestDrive.com for consumer protection. He spoke about the list data structure behind how users can specify track/dont track sites. Knowing he was talking to research audience, he posed some directions: How to describing and visualize information flow between sites; how to generating, validate and value tracking lists for curators; etc. Questions: couldnt multiple tracking list conflict each other in white/blacklisting same site? Q: Do you see visualizing information across sites as a browser problem? He wanted a more general solution across vagrancies of the browser.

Narayanan spoke about Adnostic where behavioral profiling and targeting takes place in the user's browser. The ad network remains agnostic to the user's interests. Jonathan Mayer spoke zealously about DONT Track feature (8 byte request in http header?). Paul Francis spoke about privad, a privacy-preserving way to see and be shown ads. Nina Taft did a great job of describing research goals of the new Technicolor Labs in Palo Alto (great location, people and interns!). She had math on her slides, describing differentially private SVM algorithms. She also posed problems: how to model users in a home entertainment scenario; how to do social recommendation at home where users share resources; etc.

Altogether, a good set of talks, a very large audience (200+?), and an important set of topics, I enjoyed the workshop.

Pot X

2011-07-17T07:07:00.000-07:00

Yesterday at dinner someone said, in Australia, we have "pot plants", and someone else said, in UK, we have "pot pie", and I wanted to add, in India, we have "pot Poori" (no typos), but good taste in conversation made me bite my tongue and swallow the words.

In a NY/NJ train, the youth in baggy clothes sprawled on the seat in front of me, turns to me and asks urgently (which I understood after asking him to repeat it a couple of times), "how do you spell, shield, man, shield, you know, shield?". I spell it, and he types it into his SMS. Shield? Um....

The blonde woman dressed for the club sits next to me at Starbucks and yells into the phone (profanity withheld), "I am a lousy driver, I dont drive, why dont you just tell me where to go, am parked like right here". Long conversation like this, help from me, checking GPS etc, and then she tells me, "Oh, I am so close to my friend's place, it is only 3 miles". In NY city, in 3 miles, you can go from Upper West to Upper East, Village to Midtown, Apollo theater to City center, all along wondering why you would want to do it!

On a NY/NJ train, at a certain station that locals can guess, a man gets on, sits behind me, looks around to take in the scene, watches me read the newspaper, leans over in the little while and asks, "that the wall street journal?", I nod yes, and he says, "they shrunk the size?", I say, "yes, a while ago", and he says, "yeah, been inside for long" and chuckles.

In San Francisco, I get a drink, and this old gentleman engages me in a conversation. We talk about many things and at one point, speaking of why his PhDed son didnt choose to work in research, he says, "you have to really want to write papers you know, and publish them." Simply said, and true. Later, I ask this 70+ year old man what he wants to do, and he says, "Go to NY city, don't know, stay there for long, for two weeks or something, and soak it in."

Demos, Bs and word humor

2011-07-14T19:15:00.000-07:00

What does "demo" mean? First time I asked this question, I remodeled my apartment and the contractor said they will demo. I thought, with graphics? Since then, I have learned that "demo" can mean: demonstration (garden CS kind), demolition (mo contractor kind), demote (an ad), demographic (again, ads), ...

Today over lunch I faced beer pressure. (no typos there)

I get confused between the B "triangle of beaches: Belize, Bermuda, Bahamas and Barbados.

SIGMOD/PODS at Athens

2011-07-05T06:18:00.000-07:00

PODS 2011 (a database theory conference called Principles Of Database Systems) has 1 plenary talk and 2 invited tutorials. I gave a tutorial on data streams research. My talk slides are here. It is difficult to present a tutorial on an area in 1 hour, and in particular, on a topic like data streams that has seen a lot of research, and in many different communities. My tutorial presented one technique (count-min sketch) and its applications, and emphasized the role of database community on this area (slide 32). The question of one pass computing, the motivation for dealing with large data streams, and most important for me, systems that actually use streaming in practice and validate the research effort of nearly two decades, all came from this community. I argued that their questions and drive eventually led to not only good theory of CS but also impact outside CS such as in signal processing community, where to at least some extent, compressed sensing results could be obtained by applying the count-min sketch. I would like to believe that this is a new vantage for the database community to value their technical impact (not the use of their technology) beyond CS. Some notes:

Tova Milo gave a nice plenary talk on business process data management (imagine queries to travel agency like, can I get a price quote without giving first my credit card details?), nearly all aspects from data models to query language to logic, optimization, provenance and structural/module privacy. More info here.
I spent some time with Raghu and Divy. Raghu has done everything, and it is great to pick his brain about the potential evolution curves of MapReduce, BigTable/Cassandra/ and others. Divy is super open to discussion on any topic, and we continued our past discussions on auction and pricing, this time more focused on selling data. I also spent time with Divesh, charming, incredibly knowledgeable with footprint all over SIGMOD as usual, and the ever-clever Alon Halevy (I cant break his story yet!).
In PODS business meeting, it was suggested that number of emails be used as a measure of complexity of organizing a meeting.
Finally, PODS overlapped with the day of protests and general strike in Athens. Normally the Athenians (and Greeks in general) have an alluring air of anarchy about them, and this day exaggerated the effect. I mistakenly walked into the intersection with tear gas, and not only teared and had a serious headache afterwards, but also spent the flight back to NY with no feelings on my left leg. Notwithstanding that, I was happy to be in Athens where the modern world began.

The database community likes to dress up, dance and party, and the banquet was indulgent, transforming bag-carrying, laptop-checking researchers into socialites. A 100 year old nonprofit group performed traditional greek dances --- simple to complex leg movement, with simple stringed instruments. Over the banquet, I managed to catch up with Peter Buneman and Johannes Gehrke, and talked about the EU research program on human brain. The question was, what is a big database research issue in human brain research.

ps: Missed going to this bookstore to look for Arkas in English.

FCRC (Google Meeting)

2011-07-04T20:33:00.000-07:00

At FCRC 2011, Kate Berrios, Lisa McCracken and others of Google organized an event for academic researchers --- students and faculty --- to meet with Googlers. There was an unusual format with 10 or so short 3 slide presentation of projects and their major challenges by googlers and then each of the presenters was available at a table for an hour+ of discussion and questions. Some notes:

Infrastructure: A web service request gets translated into 100's of parallel machine requests. Rare events (1 in million) happen! Fiuring out timing of processes across machines is a challenge. Performance problems in reality is hard to reproduce in labs because of the scale and complexity of real life.
Cluster management: external view of the cluster is simple, internal view not as much. Each service depends on scores of others. Anything new introduced makes some people's life better, everyone's life simple bit worse. How do you move an application from one data center to another, when each depends on scores of other services? Failures are a reality, make them first class objects in thinking about systems. Load variations are enormous, 100B to 6 TB per request in some cases.
Profiling systems at scale. Goal: 0% overhead for profiling across systems, platforms, languages, versions, and it has to be stable and everywhere? Very few benchmarks because world constantly changes and cant be reproduced. Use lot of open source tools and publish them.
Social: social interactions are more than 2 people, or edges. Social behavior does not happen on graphs. Directionality, symmetry, organizational structure, etc. Are users comfortable with sharing: any measure of this and associated utility?
Android security: Malware problem due to being popular and also open (due to large numbers). A problem: find andorid malware (client side? power-aware?). Malware perform redundant operations to be deceptive. Prob: Strong authentication methods for cellphone as a personal authenticated device?

I spoke about challenges of ad exchanges, and afterwards, at the table of market algorithms researchers --- Costas Daskalakis, Mukund Sundarajan, Gagan Goel, Vahab Mirrokni, Darja Krushevskaja, and others --- tried to shepherd the conversation to focus on large technical challenges, with the somewhat controversial hypothesis: "Research labs have given researchers good research problems, but not great ones. To engage the best of the research brains, you have to able to pose truly great problems." (In response, Costas said, "Archimedes was interested in squaring the circle." :)) Some of the discussions that ensued:

Bayesian vs worst case values. Of course! We discussed Leonard Savage's work on Bayesian assumption. Do advertisers know values? Who knows priors, bidders or mechanism. Can we design mechanisms which will work in adversarial as well as Bayesian priors nicely?
Multidimensional revenue optimal mechanisms, problem to solve. Correlated bidders.
Auctions that optimize not expected revenue but risk aversion (see eg. Mukund + Qiqi's work), say concave utilities and say other stochastic measures besides expectation? Challenge is also conceptual, what is a suitable benchmark?
Automated mechanism design?
Repeated games. 2 bidders with budgets, repeated second price auctions, what happens? Bidders learn, CSists might have a better handle on this theory than say Economists.
How to integrate auctions and machine learning? Of course! Variations in input vs predictions needs to be modelled. Online solutions vs where ML applies.
Big problems, eg., can we provide guidance on how science budget should be allocated among various disciplines, or NSF CS budget among different areas? Given a subset of researchers, say we can estimate their impact on the society when funded. Given this oracle, can we allocate funds to people to maximize social welfare? Can we model people switching teams in second round or open bid systems for reallocating funds? Q: Why doesn't NSF give $'s to 2 teams for the same project and get them to compete? For some recent work, see the work of Shay Kutten, Ron Lavi and Amitabh Trehan.
Level k thinking and dynamics. We discussed 2/3rd of the average game (did you know, there was a museum of money?). If you have a wrong model of competition (say you think you play against MIT students, but we are not), then you can do wrong things even if you are rational. Vahab mentioned several results on level k dynamics and ad auctions.
Assumption about others. Can one design a mechanism that is independent of assumption about others, robust to beliefs, solution concepts, and despite sophistication of bidders. For ex, some black box where myopic learning leads to good equilibrium?
Abstract a model, deisgn incentive-compatible mechanism, go to real world, property doesnt hold. We need a notion of how incentive-compatible are bidders. Need a useful analog of approx for incentive compatibility.

Humor: Index a la Harper's

2011-06-28T06:35:00.000-07:00

Harper's Index is a quirky slice of statistics and often a piece of art. Alas, the archives of Harper's Index seems to be behind subscription, but here is an example and here is a great article on it ("The Index provides a list of about 40 facts centered in a vertical column on one of Harper's front pages. Adjoining facts complement one another as the list meanders through a variety of subjects, at times creating a narrative. The facts are linked through puns, jokes and contrasts; common topics include government expenditures, welfare costs and political poll results."). Anyway, here is what it inspired:

On a 35 min call from an iPhone on AT&T's network, how many times does the call drop? Ans: 15
On a 35 min call from an iPhone on AT&T's network, what is the longest continuous call? Ans: 13 min.
On a 35 min call from an iPhone on AT&T's network, how many calls last less than a min? Ans: 11
On a 35 min call from an iPhone on AT&T's network, how many show up as successfully completed calls? Ans: 10
On a 35 min call from an iPhone on AT&T's network, how many minutes does AT&T charge using their standard "rounding" technique upto minutes? Ans: 44 min

Finally, why the heck do I use this junk service? Because the iPhone is a white sleek piece of art, and AT&T supports CS research and pays salaries of many of my research colleagues.

Open, streams or apps

2011-06-28T06:23:00.000-07:00

I like the culture of open problems and challenges to draw out the talented (shy and recluse, or just normal) researchers.

Piotr Indyk, Andrew McGregor, Ilan Newman and Krzysztof Onak have a nice list of open problems in data streams research. The list has concrete, technical open problems and avoids wordy discussion of novel research directions.
The FCC challenges researchers and software developers to engage in research and create apps that help consumers foster, measure, and protect Internet openness. A few interesting apps among the submissions, even though they sound researchy.

ACM Awards at FCRC

2011-06-10T22:02:00.000-07:00

Michael and Lance have already blogged about the ACM awards, here are some delayed bits.

Awards. Leslie Valiant, the Turing award winner, got a standing ovation. He spoke about the early, risky days of STOC when researchers had to "climb the wall of fear that not much science there to be discovered" in CS, and how, as a result, the STOC community was truly open and encouraged new ideas. Will 20 years from now a Turing award winner say that about today's STOC? Craig Gentry thanked Leslie in a meta way, for showing that sometimes one needed messy intermediate computations to prove the eventual, clean theorems. The awards of 2011 had support from companies like Google, Microsoft and IBM. Alfred Spector, ever precise and thoughtful, allowed himself a poetic moment when he said (paraphrased), "CS is in the heart of Google, we hope to remain in the heart of CS". On a personal note, I spent the evening admiring the constellation of great fellows from Dan Spielman to Michael Jordan, Christos Faloutsos, Fernando Pereira, Jennifer Chayes, Subhash Suri, Phil Klein, Amr Abadi and others, congratulations to them!
ACM: The programming contest had about 20k students from 2k schools across 80+ countries. Wow. ACM has 100k+ members.
Attire. It was good to see researchers like Lance carry a Tux superbly. I had to get something pronto from the local mall. In the final moments, I realized I needed a belt, and in what proved to be a great detour, bought a skateboarder belt with hand-drawn art from the fantastic Circle-A shop, and got some tips for skater music cafe. San Jose has its edge(s)!
All else. Conversation at my table involved words like Mimesis, books like "In the realm of hungry ghost", ageism in awards if any, etc.

After W8F

2011-06-10T21:41:00.000-07:00

After W8F, I had to detox some. Went for a walk in the neighborhood and saw this window display of office chair bottoms in Soho. Turns out display is to celebrate the book, A Taxonomy of Office Chairs, by Jonathan Olivares at the Phaidon. "Olivares begins his survey at the beginning of the 1840s, a period agreed upon to have seen the origins of modern business management, and ends it in the present. Over this period he has selected 184 of the most innovative office chairs from the thousands that have been designed and manufactured. This rigorous selection process has been underpinned by one rule; only chairs that have introduced at least one innovation have been included." With historical notes, technical drawings and photographs, the author presents his impressive research.

ps: I took a picture with my iphone which alas died since beyond factory restore, and I was happy to discover an identical picture here.

Workhop on Sparsity, Coding, and Complexity

2011-06-10T19:29:00.000-07:00

Workshop on Coding, Complexity and Sparsity will be at Ann Arbor, Aug 1--4, 2011. It is organized by Anna Gilbert, S Muthukrishnan, Hung Ngo, Ely Porat, Atri Rudra, Martin Strauss. The basic premise is that there has been a lot of nice interaction between coding and complexity theories, and a fledgling interaction between sparse representation and coding theories; academic research will be far richer exploring more of the connections between sparse representation and coding theories, as well as, between sparse representation and complexity theories. Could there be a general structural complexity theory of sparse representation problems and could techniques from algorithmic coding theory help sparse representation problems?

Let us get researchers from different areas together in a dagstuhl-like setting and explore the question. There will be tutorials, talks and time to research. Anna and Martin lead local arrangements, Atri is quarterbacking the effort, and I am playing the data stream researcher, highlighting the role of both upper and lower bounds from data streams that apply to sparse approximation and coding problems.

NSF W8F: Last heave

2011-05-15T04:30:00.000-07:00

Thanks to efforts of many, and mainly thanks to those who accepted our invitation to come out and brainstorm (without giving a talk, and with minimal information on what the workshop will be. my sincere thanks to them and this is an IOU, collect when you need it), we are near the beginning of the NSF Workshop on Algorithms In The Field (W8F). The webpage has been updated with the list of attendees, schedule, abstracts, breakout meeting rooms, etc.

We have a limited number of talks. These will frame individual issues, large themes, and set us for our discussions. Check out the abstracts, some truly exciting talks on the menu, from FOCS to Education, right things to cheap wins!

We have a fantastic set of attendees. Now all that remains is to bring an open mind, discuss and find exciting ideas, directions, collaborations. Weather is rainy and promises to be that way M-W. We will be away from grading, teaching and admin (in case of academics) and bosses, quarters, or deliverables (in other cases), so let us have fun, solve some problems, or at least pose them.

Local Talks

2011-05-07T05:40:00.000-07:00

Upcoming talks in NY area:

Mark Hansen at the NY Academy of Sciences on The Intersection of Data and Design ("Data are as ubiquitous as the air we breathe."). D.E. Shaw speaks on June 17 in Imaging, Visualization and Simulation: New Tools for Technology and Healthcare meeting.
NY Area Security and Privacy day is on May 20 at CUNY.

NSF Workshop on Algorithms In The Field (8F) Contd

2011-05-04T15:20:00.000-07:00

The workshop 8F is in the final lap of preparations. The schedule is up, breakout groups have been announced, etc. Time for some humor.

Urban dictionary tells me: 8F is hexadecimal term for 143 which is known as the numeric term for "I Love You". I postulate that every word is within four degrees of separation from love, or sex. Let us say this is the 8F postulate.

Rutgers Hires

2011-05-02T07:33:00.000-07:00

David Cash, Swastik Kopparty and Shubhangi Saraf and have accepted to be on the faculty at Rutgers Univ. Awesome! The Theory CS at Rutgers wall of fame is here.

The Manhattan Squeeze

2011-05-01T11:36:00.000-07:00

50 cent's In Da Club is tight, a composition with pace, and no moment to spare. Manhattan is like that. Real estate is measured in $'s per square foot (1000+), life in $'s per min for children's swimming pool (2, no tips), and leisure in $ per min of massage (3, including tips). NY has a certain tightness of geometry. The traditional buildings stand shoulder to shoulder, elbows tucked in, holding their breath and not heaving; once they clear the shoulder line, they squeeze further to form tiered rooftop gardens. There are a few exceptions --- the bulbous Gehry building or the infamously spiral Guggenheim --- trying to elbow out their neighbors, build moat spaces around them and break the squeeze. Me, I like the squeeze.

Short Comedy Films at the Y

2011-05-01T09:41:00.000-07:00

There is a scene in Godfather 2 when Robert De Niro tenderly looks down upon his son in the crib in defused light, and there is my favorite Keith Haring's painting on the left of a father holding his child high. In reality, life is not as serene or playful, but for an evening, I can enjoy movies, holding the only 14 month old at the The Iron Mule Short Comedy Films shown at the Tribeca Y. I got to see some amazing shorts in the April edition. In Houseguest, Julian Assange (of WikiLeaks fame) is an awful houseguest. In the adorable Oktapodi, two octopuses try to escape. In The Man in the Blue Gordini, a radical clothing revolution targets the monochromic orange totalitarianism, thanks to the Pied Pier in blue Gordini. In the Sounds of Summer Camp, a NFL training session becomes a rap song. The hilarious Bacon is a 12 part documentary journey through the myth, legend of bacon. In "Television is a Drug", the TV tries to get your attention. And finally, in Regrets: Kid, a mother faces her forgetfulness.

Rutgers Day 2011

2011-05-01T09:03:00.000-07:00

Rutgers Day took place on Saturday Apr 30. A day to showcase programs, campus and the people. Lot of great booths, demos, performances all through the day, and the weather was perfect too. Five of Rutgers CS students --- Aparna, Hongzhong, Maurya, Shyamsundar, and Vasisht --- built an Android tool called "Rutgers Day Review" that lets one review the events and the various booths during the day (take a picture, write review, share by uploading it to facebook via our servers, if you are funny, you might win an awesome LiveScribe Smartpen as the prize). It is live on Android market now, but the server has been shut down after the day. Some of the uploads are on the facebook page here.

ps: Winner Vukosi's caption for the upload on the left, "Been waiting for the weekend science bus for ages". Also, the Aero Engg dept that had big model airplanes in the booth ran a raffle for an iPad to draw the crowd! The Jet Age is over and we live in the Apple Universe.

NSF W8F: Questionnaire

2011-04-26T20:42:00.000-07:00

NSF Workshop on Algorithms In The Field (8F) is about having (theory/algorithms) and (other CS areas) researchers collaborate on key challenges. For the purpose here, (theory/algorithms) researchers publish in stoc/focs/soda/socg/spaa/....; (other CS areas) researchers publish in sigmod/sigcomm/icml/kdd/sdm,www,....

This blog post is a call, you probably have well formed opinions on this topic, help us by filling this questionnaire and mailing it to nsfw8f@gmail.com. Your help is much appreciated, and will be acknowledged in the workshop report.

--------------------------- CUT HERE --------------------------------------------------

Your areas of research/expertise
Any pointers to any excellent examples of online surveys, tutorials, talk slides, monographs that demonstrate some of the outstanding challenges in your areas of interest.
List any papers/DBLP entries that you would like to highlight as an example of (theory/algorithms) + (other areas of CS) researchers working together to get a nice result.
What area/topic in algorithms/theory you or your students or researchers in your area wish they knew? (I have had various researchers say they wish their students knew linear algebraic algorithms better, or randomized algorithms, or optimization or whatever).
How should we train (theory/algorithms) + (other areas of CS) students, researchers to work with each other.
In your experience, did you face any obstacles/bottlenecks in such collaborations?

-------------------------------------------------------------------------------------

New Univ in New York?

2011-04-26T08:31:00.000-07:00

Mayor Bloomberg has put his energy in the past on big projects, some more successfully than others, and this time, the City has been seeking responses to its proposal to start a new Univ for Applied Sciences (yes, CS counts). More info in NYT article.

NAS Kavli Frontiers Meeting

2011-04-24T19:58:00.000-07:00

NAS/NAE Frontiers meetings are truly exciting, drawing very creative people from various sciences, and putting together a few select talks that never fail to generate unbridled questions or suggestions from the audience. I was at the NAE Frontier's meeting in 2002 (held over from fateful Sept 2001, my flight from Dulles to LA on Sept 12 cancelled). I was glad to be back at the NAS Kavli Frontiers meeting at Irvine a few days ago.

One session was on The Creative Brain on how brain controls behavior, in particular, creativity. Beversdorf introduced the session and discussed relationship between creativity and neurological conditions as well as possible brain mechanisms. Dr. Ganesan (real Dr kind) discussed relationship between creativity and pathological conditions including psychosis, schizophrenia and insanity, and presented evidence of a link via chemistry, biology and evolution. (I remember a gem about schizophrenia being defined on basis of language, need to follow up). Beeman gave an engaging talk (using puzzles!) about processes and neural activity leading to insights, and their modulation by mood and attention. See connection between Aha moments, problem solving skills and cognitive activity. Audience had questions about parallels with other animals. I liked this session because there is a lot of pop theories about creativity and drugs, or tortured artists, or genius, but here were serious scientists doing the hard job of trying to really understand the underlying connections. Brain and its dynamics is one complicated system! But we humans really need to understand it. I wondered what will be a challenge in the spirit of the Human Genome project or the Manhattan project in this area: map the 100B neuron graph or pick one Brain area and understand its function? There were many other sessions of similarly high quality of discourse: freshwater supplies of the world, causes of extinction in very large and short scales, biomimetic materials, organic drug synthesis, genetics, quantum, and so on. Fantastic collection.

There were more attendees than speakers, so there was a poster session to bring out latent exciting research. My favorite poster was by a population biologist that presented research on migration patterns in ants. Apparently this takes place with a leader who repeatedly schleps between the old and new location, recruiting one ant after another for the tandem walk.

My talk was in a session on Algorithms and Big Data sets --- one of the two CS sessions --- with Asu Ozdaglar (spoke about social networks and strategies, gave an interesting example of herding behavior) and Ramesh Hariharan (spoke about genomics with minimalist slides, presented an interesting probabilistic string problem and variations on Burrows-Wheeler indexing, and made a nice case for faster algorithms using smaller memory since both these resources actually cost dollars in the cloud computing era). I spoke about CM sketch and streaming and enjoyed myself. Scientists are interesting. After my talk, one of them told me, "We should do a psychoanalysis of you", and another said, " We should sequence your genome". :)

One of the great things about Frontier meetings is the discussions over meals. I found out about this project to mark the spots where we bury nuclear waste using some universal language so we leave clues that will be understood say 1000's of years from now so archeaologists don't end up digging these sites when their institutional knowledge vanishes (we know how this expt worked out for Pyramids). And there was a discussion about tectonic plates moving in CA region and I wondered if we will develop the technology to get down there and grease the plates so they slide smoothly and more harmlessly. Scientists at that table liked at me like what is this Engineer doing here.

Finally, organizational issues. There was a powerful presentation from Indo-US Science and Technology Forum (IUSSTF) on bilateral collaborations between India and US. NAS and Kavli Foundation seem to be doing an excellent job of Frontiers meetings. A couple of suggestions:

Have a blogger at each of these meetings to disseminate informal description of these talks to the larger audience.
Kavli Foundation seems to be supporting research in Sciences with awards. Start an award for CS. Start an award for CS. Start an award for CS.

Finally, Raissa D' Souza and Edward Patte co-chaired the meeting and did the hard job of organizing it . As I discovered, Raissa -- a broad thinker and researcher --- and I are less than 2 hops away via multiple paths related to work!

On the left, chemical formula I havent seen in a while. Below, the tandem ants.

ps: It was fun to meet physicist Jocelyn Monroe who was looking for a billion hours of computing for free. Here it is.

Simons Science Series Talk: Jon Kleinberg

2011-04-24T18:33:00.000-07:00

Before taxes were due, Jon Kleinberg spoke at the Simons Science Series on Social Networks. Quite simply, Jon is the Carl Sagan of the Computer Science Universe. He switched between

science (Quoted Pauli that one could not even think of a wrong model; Martian's question, Is there life on Earth?),
technologies (karate clubs, wiki, epinions, flickr, emails, and of course facebook and gmail),
theories (structural social theories of balance, peer factors in social evaluations: people have negative opinion of peoplewhose level of achievement is similar to theirs),
theoretical CS (random graph modeling of dynamics, convergence analysis of local phenomena, rank 1 matrix encoded in data, random walk that returns to origin),
some truly fun experiments with data ( use flicker photo locations and abstract out a world map of population centers -- you can find the line outside a sushi restaurant if you used facebook data!; what is the prob that you answer a mail within X min?), and
great oneliners (on social networks, everyone gets a line; incredible richness of graphs; in 2000 at IBM we wondered if only we had a website where people will register and tell us where they live, and how long will it take for that to happen; we prefer facebook to enemybook; software knows you better than you do; we live in networks)

to enthrall the entire audience, and inspire them to step out of the talk, and start asking questions about the native social world online and around them, and use whatever tools --- percolation, statistics, graphs --- they have handy and start digging.

Some morsels from the feast: gmail could tell you when you are tired and not being productive; same place and same time flicker upload is sufficient correlation to associate the different uploaders tightly -- like they are a family or belong to the same conference; is there a balance theory like enemy-of-a-friend-is an-enemy for asymmetric networks?; how long will controversial topics exposed via say twitter hashtags survive?; etc.

Also, he made wiki -- at least the wiki administration that "grants tenure" to those with > = 10k edits after a vote on their portfolio -- sound cool. Finally, it is also cool to see Jon interact with many communities smoothly, go from talking about ergodicity to "like spin systems but spins here are on edges; gauge theory in physics, problem of removing frustrations".

NSF Workshop on Algorithms In The Field: Request Ideas

2011-04-09T15:04:00.000-07:00

NSF Workshop on Algorithms In The Field (W8F) will assemble CSists from networking, databases, social networks, data mining, machine learning, graphics/vision/geometry/robotics and those from algorithms and theoretical computer science. It is a wider collection than you'd find in most meetings yet small enough to discuss or even debate.

Many of you are native experts in 8F. Many of you have first hand experience of being algorithms researchers and working with others on a common challenge or vice versa. Also, many of you have thought about frustrations and triumphs, in collaborations that involve algorithms/theory researchers.

This is a call for help. Please email any issues you think we should explore; any questions you would like any particular community to address or any pair of communities to debate, or for a panel to ponder; any ideas for how to organize this workshop, etc. Here are some potential examples (disclaimer: this list is limited by my background and lack of imagination):

[Technical] Is recommendation only a machine learning problem? What problem would be most interesting to database/networking/machine learning/ folks if we could do a smoothed analysis? Is there a networking analysis for which streaming algorithm is the bottleneck? What problems in database engine is a bottleneck for which databases will be willing to live with approximation? Is there a uber version of nearest neighbors of interest to vision/machine learning/data mining? Is there a structural theory of social behavior that can be captured by graph theory? Can we prove via reductions that problems in these areas are related to each other (at a deeper level than by formulating common data structure/graph/scheduling problems)? Is there an applied area where scheduling is the bottleneck? Are there key problems in massive data analysis that needs efficient MapReduce algorithms? If algorithmic complexity was not the bottleneck, what will be main problems in vision, data mining, machine learning systems?
[Organization] If there is an annual conf on 8F, what advice will you provide? Besides developing metrics, what questions about 8F can we that will be helpful to the Kanellakis awards committee. Propose new grand challenges in 8F that requires algorithms folks and others to work together to accomplish.
[Education] How should we train students in 8F? What algorithms area do researchers in databases, networking, machine learning, vision, graphics etc. wish they (or their students) knew better? What format will be a summer school take that aims at teaching algorithms/theory students about the various fields? What will be a "field trip" in CS (akin to say in Biology)?

Google Technical Events Blog

2011-04-09T12:33:00.000-07:00

Google has presence in many technical events, from academic conferences to hackathons, developer conferences and others, and their presence is of interest to the global technical and academic community. For example, this should be of interest to graduate students looking for travel support, meeting Engineers and Researchers from Google, or pursuing jobs, etc. There is a nice blog that shows both upcoming events as well as commentary on events with Google presence. Enjoy!! (I learned about the mobility data contest from this blog).

More CS Humor

2011-04-09T11:07:00.000-07:00

One of my students in the algorithms class recently used "overbound" and "underbound" for O and \Omega. Apt, isnt it?

In the past, people's last names used to be their profession, Baker, Fisher, Kempe, etc. Soon we will have John Programmer?

Natl Acad of Sc Talk on Streams: Suggestions?

2011-04-09T10:42:00.000-07:00

I will be giving a talk on challenges in data stream processing at the NAS Kavli Frontiers of Science meeting in a couple of weeks in Irvine, CA. These meetings tend to bring in very bright researchers from many different areas in Science and Engg. They say,

"The success of this symposium largely rests on your ability to speak effectively to an interdisciplinary audience. Your task is to introduce top young scientists from many fields to the excitement of your field in general and your own research in particular. Your presentation should not be a review of your field; rather you should (1) clearly delineate the problem that you are trying to solve, (2) place that problem and your research in the larger context of your field and other fields, and (3) explain its significance. In general, your talk should be geared to ignite the interest of scientists outside your field, to communicate why the topic of the session is an exciting “frontier” and to provide the specifics necessary to set the stage for the general discussion after your talk or at the end of your session."

There is a long discussion following these talks. If you think of an interesting way to present data streams research (or passionately believe in some outstanding challenge, or think we should explore connections to some areas in Science, or have a new/old result that you think should be of special interest in this discussion) please send me ideas/suggestions, I can use a new angle.

Headline Humor

2011-04-03T19:44:00.000-07:00

Just saw a headline: The ACM Awards emphasize music (this is CS humor.)

Some general newspaper headline/classifieds humor here.

NSF Workshop on Algorithms In The Field (May 16--18)

2011-04-03T16:37:00.000-07:00

Algorithms research can take many forms from fundamental algorithms theory, to applied algorithms or even algorithms engineering. There is yet another (perhaps distinct) type of algorithms research, one in which researchers from different communities --- including algorithms and systems --- work together “in the field”, developing the system and theory jointly --- constantly informing each other and inventing in their respective areas --- without needing to make independent research threads meet ex post.

Thanks to NSF folks' initiative, there will be a workshop to explore this theme. Researchers from networking, databases, data mining, statistics, machine learning, social networks, parallel systems, graphics, robotics, massive data and others will participate in the workshop together with algorithms/theory researchers. This will be held at DIMACS, May 16--18. More details here.

Chances are many of you have ideas how Algorithms In The Field (8F, acronymize that!) is done, what topics should be covered, how this workshop should be structured, etc. Please email any suggestions. Your input will be much appreciated, if this workshop succeeds, our communities will benefit. Also, if students/postdocs/visitors in the neighborhood want to be at the workshop, please email.

Theory of Computation as a Lens on the Sciences: Berkeley Conference

2011-04-01T18:21:00.000-07:00

Theory of Computation as a Lens on the Sciences
University of California, Berkeley, May 7-8, 2011

The conference will explore the theme that many processes in the physical, biological, engineering and social sciences involve information processing at a fundamental level and can be studied through computational models. A conference held in Berkeley in May, 2002 helped crystallize this theme as a promising direction of research, and this second conference will highlight the impact of the computational lens on areas such as quantum information science, statistical physics, social networks, economics and game theory, genetics, molecular biology, evolutionary biology, cognitive science, mathematics, statistics and machine learning. Featured Speakers:

Professor Leslie Valiant, Harvard University, Evolution as a Form of Learning
Professor Ehud Kalai, Northwestern University, Robustness and Complexity in Games
Professor Christos Papadimitriou, UC Berkeley, Algorithms, Games, and the Internet
Professor Michael Kearns, Univ of Pennsylvania, Social Networks, Strategic Behavior and Computation
Professor Mark Newman, University of Michigan, Structure and Dynamics of Networks in the Real World
Professor Michael Jordan, UC Berkeley, On Joint Inference of Phylogeny and Alignment
Professor David Haussler, UC Santa Cruz, Cancer Genomics
Professor Andrea Montanari, Stanford, Statistical Mechanics through the Lens of Computation
Professor Daniel Fisher, Stanford, Modeling Evolutionary Dynamics: Problems and Prospects
Dr. Jonathan Oppenheim, University of Cambridge, Computer Science as a Lens on Quantum Theory
Professor Umesh Vazirani, UC Berkeley, How does Quantum Mechanics Scale?
Professor Lior Pachter, UC Berkeley, A Computational Approach to Discovery in Biology
Professor Tandy Warnow, UT, Austin, Ultra-Large Phylogenetic Estimation
Professor Sebastien Roch, UCLA, Large Phylogenies from Short Sequences: Recent Theoretical Insights

Please register for this conference here. There is no charge for registration. If you have questions, please contact Heather Levien, tel: 15106423497.

STOC 2011 Posters

2011-03-27T17:41:00.000-07:00

STOC 2011 Call for Posters. Details at: http://www2.research.att.com/~dsj/stoc11/CallForPosters.html

This year, STOC 2011 (part of FCRC) is experimenting with a new Poster Session. The poster session will be held from 8:30pm to 10:30pm on Monday June 6, and should be thought of as an extended hallway-discussion with a visual aid. The poster session will be accompanied by refreshments. We welcome posters from registered FCRC attendees on research in any aspect of theoretical computer sciences, and believe presenting posters should be especially appealing for:

- Researchers with new results since the STOC submission deadline.
- Researchers with papers in other FCRC conferences that would be of interest to the STOC community.
- Researchers with TCS papers not appearing at FCRC that would be of interest to the STOC community.
- Students who want to let senior researchers know of their work.
- STOC authors who want to have a visual aid for extended discussions of their work.

Deadline: May 2. Poster Committee: Avrim Blum (CMU), Lisa Fleischer (Dartmouth), Ravi Sundaram (Northeastern), Salil Vadhan (Harvard). Please send any questions to stoc11posters@seas.harvard.edu.

A String Problem: Relative Suffix Tree

2011-03-20T12:02:00.000-07:00

Given a string S of length n, its absolute suffix tree is a compressed trie of all the n suffixes of S. This is the classical data structure that is popular.

Given a string S of length n and a reference string R of length m, the relative suffix tree of S is its absolute suffix tree but with edges labelled by substrings NOT in R being pruned away (together with the subtree under those edges). Say m < n.

Is relative suffix tree meaningful, nontrivial? Any research problems, a la, best running time?

DIMACS Parallelism 2020: John Gustafson

2011-03-20T01:10:00.000-07:00

Nitish Korula is a thinker, able to assimilate and relate vast amount of information; I have been looking for a sufficiently broad topic to get him to weigh in, and this proves ideal:

----

Thanks to Muthu for the opportunity to write a guest post, and thanks to the organizers for putting together this workshop. There were several great talks on Monday, but one that really stood out was a "keynote" by John Gustafson, director of research at Intel Labs. It exemplified many of the qualities of a great keynote address; it was provocative and comprehensive, with the speaker demonstrating a mastery of every aspect of his subject.

Gustafson's vision for 2020 was billion-core computing. Not a billion cores on a single chip, but a billion cores in a data-center sized single computing unit. Getting there, though, will be more difficult than simply continuing on our current path; our performance trend curves are flattening out on many dimensions. Will Moore's law continue to hold for another 10 years? Intel imagines that we will be at 5 nm gates by then, but 5 nm is only about 50 atoms wide; at this scale electrons travel 'slowly' and "the speed of light isn't what it used to be". Even if we can get performance improvements, this is likely to require significant power increases, so the "performance per watt" will go in the wrong direction.

The talk was far from pessimistic, though; the message was that building these billion-core machines will require radically new ideas in many areas of computer science, and it's an exciting time to be doing research on them. Some of the themes woven through the talk were a need for a better understanding and use of memory, better algorithms for scientific computing simulations, and better performance metrics. I can't possibly do justice to them all, but here are a few highlights:

Shekhar Borkar, the director of Intel's Microprocessor Technology Lab, says "Caches are for morons"! More seriously, reading data from memory takes a long time, and so we have been trying techniques like speculative fetching of large blocks of memory into a cache. According to Intel's best estimates, roughly 79% of data in a cache is never accessed. Gustafson suggests that we "cherish every bit" of memory we access, which leads to a second suggestion:
Throw out old Numerical Analysis textbooks! Algorithm designers have historically "measured" algorithm run times by counting the number of floating point operations / additions / multiplications. This made sense decades ago, when floating point arithmetic took 100 times as long as reading a word from memory. Now, one multiplication takes about 1.3 nanoseconds (to go through the entire pipeline; this underestimates throughput), compared to 50-100 nanoseconds for the memory access. Why do our algorithms measure the wrong thing? We should be counting memory accesses; it isn't reasonable to ignore the constant factor of 50.
Processor utilization is a terrible way to measure performance of a supercomputer! As one of many such analogies, he compared processors to snow plows at O'Hare airport; there are dozens of plows at the airport, almost all of which are idle most of the year. But when you need them, you need all of them; it wouldn't make sense to cut back on the number of snowplows because the average utilization is low. We should design programs that use as many processors as needed; see the next point.
We need new arithmetics! (What?) Today, we typically use 64-bit floating point arithmetic for everything, because "64 bits is enough". Sometimes it isn't, and at other times, it's far more than the application needs. When it isn't, you run into rounding errors that propagate; the heuristics to deal with this don't always work, and so you could have 64 bits of precision with errors from the third bit onwards. And when you don't need 64 bits, why are you wasting memory? You should be "cherishing every bit". One way of dealing with this problem is interval arithmetic, which explicitly maintains an interval guaranteed to contain the "true" answer. Unfortunately, interval arithmetic has its own issues; it's very easy to get the interval [-\infinity,+\infinity] if one isn't careful. Still, there are applications (such as $n$-body problems) where interval arithmetic gives good results. (And when you have a billion cores, you can split up the interval and have different cores working on different sub-intervals.) For these approaches to catch on, we need new algorithms for interval arithmetics and/or new arithmetics.
We need new programming languages and development environments to allow programmers to understand / interact with the hardware they're programming for. Should compilers receive a "memory description" in addition to source code? Should programmers use a 3-D environment in which they can specify the spatial relationship of their billion cores and memory?

There was much more in this vein; I didn't touch on system software and reliability, networks and communication (Gustafson thinks we should increase communication budgets by a factor of ~8), etc. As you can probably imagine, the controversial points generated a lot of
questions and heated debate. Like many great talks, it energized the audience and suggested new lines of work on areas including architecture, compiler design, human-computer interaction, networks, scientific computing, programming languages, and (of course) algorithms.

HackRU

2011-03-16T07:22:00.000-07:00

HackRU is the largest event of the year hosted by the Undergraduate Student Alliance of Computer Scientists (USACS). It is a 27-hour programming competition beginning at 11AM on March 26th at the Hill Center on Busch campus, Rutgers Univ, in NJ. The webpage says, "The goal of HackRU is to get programmers from all over to get together and make awesome applications. We will have companies presenting their APIs—until 2PM on the 26th—which will be available to contestants to use in their applications. Contestants do not necessarily have to be students at Rutgers University. Participants may enter with a group of people as a team or may choose to work solo. Food and drinks will be served throughout the contest, and free parking will be available for contest participants. Linux machines will be available for contestants, although we highly recommend bringing your own laptops. The event will end at 2PM on March 27th and the contestants with the best applications will win prizes!"

Seems like a great opportunity to go, hang out with smart people, build something.

Workshop: Parallelism 2020

2011-03-16T01:46:00.000-07:00

I was at the DIMACS Workshop on parallelism: 2020 vision. I looked forward to the workshop and as expected, problems and challenges that were discussed were reminiscent of early 1990's,; the keywords however were not interconnection machines, grids or hypercubes but mapreduce and multicores. The people --- Vijaya Ramachandran, Uzi Vishkin, Leslie Valiant, Mike Goodrich, Guy Blelloch and many others --- were stalwarts who brought a lot of experience from PRAM world of 90's to the discussions of the day.

Mike started off the meeting with a talk on many algorithmic results he is able to obtain on a model of mapreduce. The talk was a tour through data structures (invisible B trees), geometry, linear programming and simulations (some version of BSP by a version of mapreduce), and at the least is a large swath of benchmark of algorithms research in this area that now one can understand and try to improve.
I went next. In the first part, I gave examples of simple things I wish I could do easily in mapreduce (recurse on problems like prefix sums and be able to fill answers back in, enumerate pairs for triangle counting, or do sketches for eigenvalue computations, etc). In the second part, I spoke about a special case of mapreduce, namely, sawzall, and our model for it showing it to be equivalent to streaming. I ran out of energy half way through and thought I did not communicate well the importance of sawzall, the relevance of relating it to streaming, or the niftiness of the proof that simultaneous communication complexity model can simulate sequential communication complexity model (via Savitch's theorem on streams). Apologies to the audience, as Howard Karloff pointed out, my talk had 2 jokes and 0 proofs (not true, I proved a theorem about counting triangles in terms of eigenvalues. :)), while I should have managed to work in one more proof. My talk pdf here.
Sid Suri went next and spoke in detail about the problem of counting triangles. The straightforward enumeration algorithm for counting triangles takes very long because some nodels have high degrees. Then he exploited schank's observation that responsibility for counting triangles can be shifted to low degree nodes, together with graph partition techniques to get an improved algorithm and showed actual mapreduce run times. An interesting part of his talk was the finale, where he abstracted lessons for mapreduce algorithms from this particular example: quadratic shuffling is hard, rounds matter unless some reducers are streaming which saves some, and both the model and the machines can not differentiate between constants.

Leslie started the afternoon session with a clear goal: enabling a world where parallel programs can be written once and used on whatever parallel machine. He then extended the BSP model to a hierarchical version, and amidst many parameters, still managed to design optimal algorithms for many problems. Vijaya went next and spoke about a parallel machine machine with local cache and work stealing across machines, and proposed algorithms for a number of problems in a joint work with Richard Cole. Finally, Uzi did a powerful defense of his agenda for past few years that PRAM is a useful model for thinking parallel programs and discussed 1000 or so machine PRAMs within reach.

When I headed back after a toothsome dinner at due mari, I realized that this workshop was definitely about what algorithms community should be doing --- applying our expertise on parallelism to see its impact in the new world of multi-core, multi-machines world, where systems researchers and builders have built parallel machines successfully. So, to some extent, this is a bridge from the other side (the side we knew was going from beautiful theory to getting them built). We also need a healthy perspective that systems change year to year, mapreduce of yesterday may be different from one of tomorrow. So, more tighter loop of interaction between theory and practice will be desirable.

Some Counts Dont Count

2011-03-12T15:24:00.000-08:00

Now that Turing Awards are in the air (Congratulations Leslie!), here is some data. Recall that the h-index is the largest h such that h papers are cited \geq h times each.

Here are the h-indices of Turing award winners.
82 Robert Tarjan, 57 Alan Newell , 54 Amir Pnueli , 54 Herbert A. Simon, 53 Adi Shamir, 51 Richard Karp, 49 John McCarthy, 47 C.A.R. (Tony) Hoare, 46 John Hopcroft, 45 Jim Gray, 43 Barbara Liskov, 43 Robin Milner, 43 Ronald L. Rivest, 42 Donald E. Knuth, 41 Manuel Blum, 41 Marvin Minsky,, 41 Joseph Sifakis, 40 Edmund M. Clarke, 40 Michael O. Rabin, 40 James H. Wilkinson, 40 Niklaus Wirth,

Plenty of h-indices above this cluster, and below. All data filtered from this list.

in situ Theater

2011-03-12T09:12:00.000-08:00

I don't have concept of a weekend --- work flows from one week into the weekend and on to the next --- but I have a distinct feel for the Friday evening, when work has ``ended'' for the week, I am fatigued, having gone moment to moment, and I pause some. In that mood, I went for a walk and found myself at the World Financial Center (WFC), accidently and directly walking onto the performance of The Rover by the NY classical theater.

It is what I call in situ theater. The entire 3.5 acre WFC site with its multilevel stairs becomes the stage. The action and audience are moved from spot to spot, actors move in and out of the cast and paper masks, costume and knifes flash intermittently. See NYT review. The actors did a superb job, changing their diction, body language and strides from small square spaces to long elongated ones along walking bridges, grand staircases with working escalators carrying wall street folks, and finally, to the cavernous space filled with green benches and tall trees. Surprises like this keep me going.

NVTI 11

2011-03-05T15:32:00.000-08:00

The Netherlands Theory Day took place on Friday. After a brief puzzling moment (the projector showed mirror image of the slides and I had to tweak knobs, one of which turned out to be the joystick for the menu).

Jos Baeten motivated his talk with a few observations: in reactive systems, input is not a string with an endmarker; world is nondeterministic, such as google results from one moment to another; Turing m/c's can't fly an airplane but computers can; etc. Then he embarked on describing a theory for interactivity. He emphasized the lack of distributivity in presence of interaction (a.b + a.c \not= a. (b+c); a is open door and after that have b or c revealed is different from opening the door and having the choice of b vs c), and develop an algebra. The talk went from processes similar to finite automata to pushdown processes with new concepts along the way (new Kleene closure, unbounded branching of automata, nonstandard cfg, use of contra simulation, etc) and eventually to reactive Turing machines with executability playing the role of computability. The audience had questions about quantum versions, analogs of halting problems or Universality, and so on, and technical discussions about nonlinear recursion. Jos ended the talk saying this material was good for teaching 1st year theory course because this can lead to later courses on both computability and to process algebra.

I spoke second on data stream algorithms. I had a new puzzle for this talk and was energized. Mark de Berg asked about classes of problems solvable not only in polylog space like typical streaming, but also in say \sqrt{n} space, etc. Yvette Tuin talked about Dutch govt funding for theory but despite best efforts, the picture is dismal for core theory. Observations: Grants were called "subsidies". There were interesting programs like Games for Healthcare, and things like vici, vidi, veni on slides that I am trying to still figure out. Over lunch, I got tutored on how to say Vermeer and Van Gogh.

Hans Bodlaender spoke after lunch about kernelization: preprocessing the input in polytime with what looks like simple rules to reduce the problem to its polysize kernel in some parameter k. The first example was Vertex Cover, for which O(K^2) kernel exists (one can remove any vertex of degree >= k+1 and include it). The second example was about transforming a string into one in which all symbols occur only in runs, and this too had quadratic sized kernel. Hans then related this to FPT (fixed parameter tractability): a prob is FPT iff there exists a kernel. Questions were about complete/hard problems (ex: W(1) hard), role of choice of parameters (in SAT, you can set k variables or satisfy k clauses), and other problems (set cover is hard, linear algebraic problems?). Hans talk altogether was very interesting and I think "kernelization" is a nice combinatorial way to bring one into the FPT world.

The final talk was by Tobias Nipkow. In introducing him, Femke van Raamsdonk talked about success of his group in checking complex proofs (like proof of Kepler's Conjecture or compiled Java programs). Tobias stated that students find it challenging to prove things formally. (Scott Aaronson who has a gift for phrasing, made a cameo: he was quoted comparing some proofs to LSD trips). So, Tobias started breezily, with setting out the goal of teaching students to do proofs with a proof assistant using the Isabelle system, and the image he invoked was thought of bloody video game (qed or die). Rest of his talk was about his experiment of teaching a class on semantics with HWs using a proof assistant with 15 or so MS students. Fascinating, the kind of observations one can make with such experiments. Questions: are there proof "styles"? does Isabelle find counterexamples? can this be extended to algorithms (challenges: probability, approx, running times?) can one detect plagiarism? etc. Some of the technical discussions were around whether this only applied to constructionist logic or if this was too old fashioned by omitting pointers, etc.

After the talks, the NVTI organization (Jaco van de Pol led) discussed their business --- newsletter, thesis awards --- and I was a fly on the wall. They discussed more technical activities, and Femke brought up the idea of connecting with activities for the Turing year (didn't know about that!) in 2012.

ps: The day ended with the dinner at the traditional place (for 15+ years). It was great to see Han La Poutre whose early work on data structures and dynamic graph problems I know and liked, who now seems to have ambled onto bidding/bargaining/auctions/strategies. Han is a fellow city dweller, and Amsterdam is one of the great art cities of the world.

Ad Exchanges Revisited

2011-02-27T23:37:00.000-08:00

My research on Ad Exchanges has continued, but I have been quiet on blogging about the business. Here are some updates.

It has been more than a year since the launch of the DoubleClick Ad Exchange. It seems to be doing well. See the presentation here for stats. Of relevance to research: "in January of last year the real time buys on DoubleClick’s AdExchange represented just 8 percent of the total. By January of this year, that figure was 64 percent." So, many research problems with real time bidding are now important, from optimizing call out, to understanding the game theory, arbitrage and others.

Individual publishers are building private ad exchanges around their own inventory. CBS Interactive, Forbes.com, NBC Universal (universal audience platform), Weather.com (channel 5) and Turner Broadcasting Systems. "For publishers, setting up exchanges has several advantages: they cut out the middlemen and they allow the publishers greater control over consumer data." Check out NY Times article. This means there is a lot of research to be done on inventory optimization, understanding the dynamics of advertisers automatically choosing across publishers and so on.

Hooray for AdX research!

Shout Out to Anja Feldmann

2011-02-27T23:16:00.000-08:00

My friend, collaborator and a cohort from old AT&T days, Anja Feldmann, a networking researcher for long, has been awarded the Gottfried Wilhelm Leibniz Prize 2011. Awesome, congratulations!

About the prize:

The Gottfried Wilhelm Leibniz Prize is the highest honour awarded in German research. The Leibniz Programme, established in 1985, aims to improve the working conditions of outstanding scientists and academics, expand their research opportunities, relieve them of administrative tasks, and help them employ particularly qualified young researchers. A maximum of € 2.5 million is provided per award. Prizewinners are first chosen from a slate of nominations put forward by third parties; the final selection is made by the Joint Committee on the basis of a recommendation from the Leibniz Nominations Committee.

Ode to Men -- of Certain Age ---Shopping

2011-02-25T15:50:00.000-08:00

I can give (for my friends who seek it) advice on shopping in NY for anything from clothes to chocolates, but I dont enjoy shopping or chocolates. It is just information I have because I like all sorts of information.

I went shopping for shoes and clothes today. I am more bling-bling than Eddie Bauer, so the "usual" places I go to have the property that without much thinking I can find unusual things. And sadly, I noticed today that inches are not what they used to be, they seem to be getting shorter, and I dont fit into the sizes I used to. :)

Theory Day in The Netherlands

2011-02-23T01:17:00.000-08:00

The Dutch Association for Theoretical Computer Science (NVTI) supports the study of theoretical computer science and its applications. One of the activities of NVTI is the organization of the yearly Theory Day with a combination of speakers from The Netherlands and outside. Here is the link to the 2011 version, to be held on March 4, and a link to the past list of speakers. I will speak on Data Stream Theory and hope to include some new results, slowly getting back to this area after a hiatus. The last time I was in Amsterdam, I was an unformed youth with rollerblades on my back and a restless mind. This time, the rollerblades will not travel with me.

Renewal, NY Style

2011-02-19T04:48:00.000-08:00

I have been down some, mojo in a freeze. A couple of recent incidents are helping with the thawing.

I rode my bicycle through the streets, holding two dozen black and white balloons on my left hand. The day was windy and I made a bulbous figure crouched on my bicycle, swerving to avoid parked cars, darting pedestrians and trying to not interrupt the flow of taxis that slowed as they approached me, and sped off with relief when they got past. Children waved and wanted to reach out to the floating ying yang, but my moment was made when two tourists stopped me to take pictures, with the cobble-stoned, graffiti-filled Tribeca for the background.
Yesterday it was warm, but the Parks dept is yet to catch up. The Imagination Playground was closed. I saw a few children and parents inside, including what looked like a 7 month pregnant woman. When asked, they said, "just hop over the fence". That is how one has a pleasant PM in Burling Slip, NYC. NYers dont wait out the winter, as much as spring ahead.

Edible Geometry

2011-02-19T04:35:00.000-08:00

My review of the book, Geometry of Pasta. With beautiful black and white prints. Let me list the pasta types I talk about in the review (so you dont have to rely on my spoken Italian): Penne, Rigatoni, Orecchiette, Reginetti, Strozzaprati, Stellini, .... Who knew that geometry could be edible.

Simons Science Series: Sanjeev Arora

2011-02-18T07:10:00.000-08:00

Sanjeev Arora needs no introduction for us CSists. To the larger audience of scientists and mathematicians at the Simons Science Series, David Eisenbud introduced him by pointing out his great trajectory in academia.

Sanjeev started the talk with an informal view of P vs NP and phrased it as "Can Brilliance --- someone gives us the solution, we check it and exclaim why didn't I think of it --- be automated?". The mathematicians briefly struggled with ease of checking decision vs optimization versions of a problem. Some in the audience needed to know what was n (input size in bits), whether P/NP was machine-dependent (under strong Church-Turing hypothsis, NO), or did randomization help (Not believed to help P vs NP). Given NP Completeness, how do we approach the world? Sanjeev pointed out the heuristic code-it-up approach vs average case vs approximation theory. Then he used the max-cut approximation as an example of approximation theory: GW approximation, inapproximability without or with UGC (no time to explain UGC in the talk). The local audience close to where I was sitting expressed some wonder at these numbers and the tightness. Sanjeev used this moment to make a meta point: the failure of SDP on some instance can be turned into inapproximability result. Then he discussed the PCP theorem, motivating NP = PCP(log n , O(1)), discussed gap amplification with an "impressionistic proof" and described Dinur's checking algorithm for maxcut. Rest of the talk meandered through KKL, Euclidean TSP, etc.

The audience had many question: does PCP theorem apply to natural language math proofs (ie can we replace referees in journals); in practice what does it mean if P=NP? (Crypto will collapse, SAT in o(n^2) might change worlds); do people work on P vs NP (Sanjeev didnt fall for the temptation to give examples of attempts and said when you work on a problem, you constantly keep both algorithm and complexity in mind, and eg wonder if I solve this piece, will it have a bad implication),;any connection to machine learning and data mining (some of the key problems there are hard to approximate); etc.

Well, Sanjeev is a prince of a researcher and he did a great job of presenting central thoughts related to P vs NP question. I was very pleasantly surprised by how audience related to the PCP theorem: many in the audience, seeing it for the first time, really saw the power of the theorem and its enormous implications. For the evening, maybe without intending, Sanjeev represented the SIGACT Committee for Advancement of Theoretical CS ("Increase awareness of theoretical computer science's activity and successes in general CS, and the public at large.")

A Report (Financial Crisis) and an Observation (Apple)

2011-02-17T05:36:00.000-08:00

Here is a report: the Financial Crisis Enquiry Commission has its report out on the Great Recession from 08. It is a fascinating account, one would imagine there is a lot here about network effects to model and study as (armchair) Economists.

Here is an observation: Apple is a company that nurtures and thrives on its image as an innovative company. Yet, it is surprisingly absent from the world of academia, and does not seem to support research either directly by employing a research group or vicariously via grants, or indirectly by having their employess --- Applers, is that what they are called --- attending conferences. This observation seems to say something about either Apple or Academia.

NY loses Yasuda

2011-02-05T19:11:00.000-08:00

It is 2+ months old news, but I could not bear to talk about it earlier. My sushi chef Yasuda leaves NY. NY Times does a piece, aptly, elegy-style. If someone has the address for his new (8 seat) sushi bar in Tokyo, please let me know. A flight to Tokyo is small price to pay for the master. Some pictures of his incomparable sushi here. And his parting gift: Sushi Nori Yasuda.

Unique iValentine's, iPhone Style

2011-01-29T05:17:00.000-08:00

Valentine's could be traumatic: you need to be creative, fun, meaningful, and still be you. People expect all that. One way is to build something of your own. As in many things in life in this post-6/29/07 era, iPhone/iPad is the answer.

iAdverti's BeCreative is an app builder. Think of it like scratch or appinventor, but very light and highly usable. You pick a canvas background or use your own photos, add various objects (whimsical, from food to office items), do touchscreen magic like rotate, resize etc. and add music. You got yourself a card! (Like a true object of creation, you have to iterate of course).

Also, here is a contest: Valentine's des Artistes, run by iCanstandit. Use BeCreative app builder to produce a Valentine's Day card for iPhone/iPad, share, vote, and win prizes! One of the prizes is a very cool tablet stand (which assembles and dissembles in seconds!) that I find very useful.

ps: iAdverti has a few ebooks that kids and adult-kids seem to love. My fave on the left.

Teaching Algorithms: Personal

2011-01-28T05:40:00.000-08:00

Semester has started. In my first lecture in the graduate algorithms class (overflowing by factor 1.6, and factor 2 if you consider the waiting list), I saw a student I recognized from the same course 2 years ago, arrive and sit in the rear of the class. As I proceeded with the 3 hour monster of a lecture, I tried to put the mystery of this student away in my mind. During the break, the student came up to me and said they liked my lectures and just wanted to experience my first lecture. The student's life had of course moved on in the interim with triumphs in other classes and internships, and was on the threshold of a career. I was deeply moved and thankful. I credit the material of course, it is difficult to be NOT interesting while teaching Algorithms.

Market Algorithms Talks

2011-01-28T04:18:00.000-08:00

On Wednesday, I heard a few talks on "market algorithms".

Christos Papadimitriou (think Che Guevara T-shirt, motorcycle leather jacket) described many results. First, departing from Nash equilibria of games, Christos focused on Arrow-Debreu market pricing and noted that it assumed convex production (hence, no economies of scale). Instead, the proposal is to consider "complexity equilibria". The main result was, "any poly bounded agents will be stuck in a dense market". This work is likely to have tentacles, even reaching into different measures for quantifying the density of markets. Second, Christos revisited Nash equilibria and focused on equilibria selection: Finding Nash equilibria by any of the standard known methods (eg., Lemke-Howson, Homotopy method) is PSPACE complete (also true for approximate equilibria to some extent). Then, continuing with Nash's theorem, Christos pointed out that it deals with maximizing expectations (E) and does not model risk, insurance, etc. He gave a general formulation of studying games with risk and defined a new concept of V-Nash equilibrium. When does Nash Theorem hold with this concept? Yes --- exists and as easy to compute as standard Nash equilibrium --- for E+Var, E+ Prob(X>c) and so on, and No --- may not exist, NP hard to tell if it does --- for E-Var, and others. Finally, he turned to auctions, and considered combining welfare and revenue. Contrary to conventional methods of considering linear combinations, the mentioned the result that the Pareto curve (deterministic auctions, independent, random values) is not convex and in general is intractable. This was, as usual, an inspiring talk from a maestro.

Sudipto Guha (who later regaled with stories of dusty travels in Peru and Nepal) gave a lecture, equally masterly, on ad allocation problems. It is tempting to see the ad allocation problems in a vast grid of offline vs online, weighted by CTR/Conversions, budgeted or not, or optimization vs explore-exploit a la multiarm bandit, and so on, and indeed it may be natural to navigate this vast space in that cell by cell manner. But Sudipto chose a many-layered presentation, first pointing out that a key is to consider the timing and via a series of examples, pointed out world was not "Here’s the input and the function, go …" but rather, "Unsure of the input, discover the input and the function as you proceed ..." Thereafter, Sudipto focused on a concrete example, Multiarm Bandit (MAB) type problems where playing an arm secured only a delayed response. There are nuances in setting up the benchmark to compare ones' algorithms, the techniques even more detailed as Sudipto described a series of transformations to make the problem LP-amenable. He finished with a host of MAB problems, even more complex, and yet to be tackled. MAB is a crowded space in CS beyond algorithms research, and algorithms researchers are bringing genuine insights. Mental note to follow this literature more.

There were other talks (Jason Hartline, Suchi Chawla, Mukund Sundarajan, Vahab Mirrokni, Aranyak Mehta, Andrea Montanari) as well, that alas I am not able to summarize here now.

ps: For those who dont know Che, he is the one who wears Bart Simpson T-shirt.

pps: Sudipto's awesome quote that needs some time to parse. "Diagonalize this!
* There is a prior (consistent) * There is no prior (is it self consistent?)".

Some Questions

2011-01-17T15:51:00.000-08:00

On my mind:

Should ACM/SIGACT/EATCS do a Gödel Prize for Applied Algorithms (theoretical algorithms research that has demonstrable impact on practice), notwithstanding the difficulties in defining and quantifying that?
Who are some of the finalists for the Simons Institute for Theory of Computing?
Is there an emergence of network coding in practice?

Any answers will be appreciated.

AMS Awards

2011-01-09T03:32:00.000-08:00

American Mathematical Society (AMS) awarded major prizes at the Joint Mathematics Meetings in New Orleans. Among them:

The Bôcher Memorial Prize (with its incredible legacy from 20's) to Assaf Naor "for introducing new invariants of metric spaces and for applying his new understanding of the distortion between various metric structures to theoretical computer science".
The AMS Steele Prize for a Seminal Contribution to Research to Ingrid Daubechies "for her paper, "Orthonormal bases of compactly supported wavelets" constructed the very first examples of families of wavelets that have since become extremely popular in practical signal processing."

Awesome. Congratulations!

Banking in India

2011-01-03T20:16:00.000-08:00

Banks worldwide adopted Internet early on, but seem to be stuck with late 90's technology and perspective. Banking in India is an interesting exercise. I am told that they ask for a lot of information when you apply for an account. It takes several days and you get called by many employees of the bank meanwhile who seem to be verifying things, but every one seems to have access to your entire file. Then, you try to set up the Internet account, or try to access it. They have zeal for security: they have an on-screen keyboard that is rearranged arbitrarily each time, so it takes time to figure out what to tap; in addition, they time out very rapidly (think in the order of a few TCP roundtrip delay times!); so you scurry like a mouse that gets trained instantly and is sent down the maze that morphs each time. Then there is the ATM experience. There is a security guard near the ATM, one takes off their shoes before entering, and the ATM times off rapidly and I had to on average enter my password twice. Finally, here is a Koan with a wink from Soumen: Why do ATMs only disburse crisp new currency notes? (somebody must print a lot of currency!).

ps: Here is a discussion on innovation in banking in India from micro pensions to biometric ATMs and banking for the unbanked.

Difficult Business of Flimmakers in NY

2011-01-02T07:14:00.000-08:00

Film making is difficult business and two filmmaker friends in NY make strides in 2010:

Shailja Gupta released her first film Walkaway in October, about the "meanders of Indian matrimony" among people "with one feet in NY and one in India".
Manolo Celi whose short film Neuva York about US Hispanics in "the canvas of NY" I enjoyed at the Tribeca Film Festival last year, made major progress with Tony Tango.