Unique iValentine's, iPhone Style

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

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

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

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

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

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

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.
  

Happy New Year!

As many would observe, this is the year to celebrate 1/1/11, 1/11/11, 11/1/11 and the fabulous 11/11/11. Happy new year!

Films to End 2010

I spent the 16+ hrs flight from Mumbai to NY -- one of the earliest flights able to get through after the snow --- stretched out detoxing, and watched or rewatched:

• The Vulture: Japanese. A fund manager comes out of retirement to rescue a Japanese car company from a Chinese fund manager in a high stakes thriller. Ancient Japan and its traditions from behind the Wall Street heroics.
  
• Raise the Castle: Japanese. Villagers are convinced to build a castle, out of cardboard, in a Don Quixotesque setting with bureaucracy, visit from Samurais of the distant past, and a woman architect/engineer. Awesome collage of concepts, and despite the rawness of execution, a fun movie.
• Up: Animation. A friend not used to repeating words, recommended this movie twice. It is a charming movie about wilderness, adventure, spirit of old people, and 1000's of balloons, but I am a dogs person and for me, it is a fabulous movie about dogs.
• Broken Embraces: Spanish. Almodóvar's ode of a movie. Every frame is exquisitely composed, and Penelope Cruz is superlative. NY Times raves. A line: "It's a normal kiss, the kind couples give each other out of habit." Not when you watch it the first time.
  
• Gran Torino: Clint Eastwood scowls, growls, spits, or instantly glows, as the outside world teases him out of his hole and he emerges a protector in this sly movie. Phenomenal review.

All worth watching. And from a flight a while ago, must watch: King of Jail Breakers. A quirky, japanese film about a man who repeatedly and ingeniously breaks out of prisons only to be caught on train tracks. It is a beautiful mystery.