Friday, July 31, 2009
On Being a Theorist
Wednesday, July 22, 2009
Rejecta Mathematica: Vol 1, Number 1.
Mark Davenport: We are delighted to say that the content of this first issue runs the gamut of genres included in our mission: minor or traditionally unpublishable results, non-traditional ideas and proof techniques, misunderstood genius, results based on questionable assumptions, and controversial papers and open letters. We are also pleased that the papers span several areas of the mathematical sciences, including pure mathematics, applied mathematics, theoretical physics, and engineering."
Sunday, July 19, 2009
Saturday, July 18, 2009
- What is the worst permutation p, that is, no matter how it is rotated, it has the least number of entrees directly in front of the person who ordered them?
- Find a fast algorithm to determine the rotation that will maximize the number of people who will find their entrees directly in front of them.
2 Round Monty Hall
ps: Of course people will argue it is not really free, or that ultimately, the measure to optimize is readers' attention, so we need confs to select and rank papers, and authors to write papers in a prefix-complete sense (readers read from the beginning and stop when they want to, and the results should make sense no matter where they stop), etc.
Friday, July 17, 2009
SUNY Buffalo, the local host institution, is associated with quality theory in my mind. I got to talk to Atri Rudra and heard about some of his nice new results on codes in the streaming model. I also had a great talk with Hung Ngo on analyzing probabilistic data, wish I had more time to talk about some networking problems.
Finally, I completed nearly 20 years of my life as an immigrant in NY by visiting the Falls for the first time. I am a freak for large bodies of water, and the simulated waterboarding as you stand under one of the falls and gasp as your lung expands, was cool. Also, I got reminded that we all have reasons why we are theory researchers. Me, I left my undergraduate school vowing never to read another IEEE journal again. With the exception of some amazing thing by information theorists, for most past, I have succeeded.
NY Friday AM
Sunday, July 12, 2009
Things I Think About
- [Worth of Information] If you had access to the location of people for every second, accurate to (lat, long) coordinates, for several years and continuing, for millions of people, how much -- $'s -- is it worth?
- [MJ, MJ, BO] NYT says, "Mr. Jackson was to music what Michael Jordan was to sports and Barack Obama to politics ...". Everyone I know thinks one of the 3 --- a different one for each --- does not belong to the list with the other 2, based on some hypotheses they have in mind for the analogy. The question of course is what did NYT have in mind?
EC 09 Travel
- EC started on Monday with the Workshop on Ad Auctions, a feast for specialists, papers flying off on themes of externalities, expressive bidding languages, pricing and equilibria; all papers are online.
- Next (for me) was the Tuesday of tutorials. Jon and I did a tutorial on sponsored search and took a risky route, not talking about auction design. Jon splendidly laid out the world of many knobs that advertisers face (as one researcher exclaimed later, "And we work on what auctions to run?"). I spoke about how to optimize ad campaigns with a given budget. Researchers angst about whether advertisers care about clicks, profit, ROI, conversions, or whatever; do they consider interaction between keywords, broad match or stochastics, etc. My main point was these goals --- notwithstanding our passion to apply LPs or discover hardness of problems --- can all be compiled down to the knapsack problem with suitable weights and values, to some approximation. Then, simple bidding methods work. I ran out of energy some, and did not wrap up this argument like I wanted. I hoped to give an effective way for advertisers to think about their ad campaigns.
- EC Conf started on Wed, banquet-ed on Thurs and sputtered on Fri. I liked the two papers (1, 2) that tried to understand the price of truthfulness in learning click-thru-rates for revenue/efficiency in ad auctions. At the banquet, we learned Nicolas Lambert continued his run and won the best paper award at EC. On Friday, Michael Moritz, a journalist, venture capitalist, and surely other things too, gave a keynote talk.
- Nikolay Archak (data analysis), Tanmoy Chakraborty (cs theory) and Mallesh Pai (econ) are all interns in NY who were at EC as well, and I got to see the conf from many different perspectives through them. Nitish Korula, who was at ICALP, was missed.
Thursday, July 02, 2009
FOCS and Streams
- Exact And Approximate Pattern Matching In The Streaming Model. Ely Porat and Benny Porat.
- The Data Stream Space Complexity of Cascaded Norms. T.S. Jayram and David Woodruff.
- Efficient sketches for Earth-Mover Distance, with applications. Alexandr Andoni, Khanh Do Ba, Piotr Indyk and David Woodruff.
Talks, Tutorials, Truthfulness
|EC 2009 Tutorial|
Feldman, Muthukrishnan: Information
Exchange in Sponsored Search.
There are at least two forthcoming talks of great interest, but you have to choose one: Susan Athey will speak at EC09 on Wed, July 8, at Palo Alto, CA. On Thurs, July 9th, Noam Nisan will speak at ICALP09 at Rhodes, Greece.
Finally, truthfulness. Can we design a truthful mechanism for budget-constrained bidders in a series of ad auctions? If you wanted to maximize the number of clicks, in some cases one can design such a mechanism [FMNP SAGT08]. If you want to maximize profit, such mechanisms can not produce Pareto-optimality [DLN FOCS08], but in a forthcoming paper at Ad Auctions Workshop, Ravi, Hafalir and Sayedi show a very nice, simple semi-truthful mechanism that is also Pareto optimal.