ACM Fellows, 2011

Many theoreticians on this year's list of ACM Fellows:

• Serge Abiteboul
• Guy Blelloch
• David Eppstein
• Howard Karloff
• Joe Mitchell
• Janos Pach
• Diane Souvaine

Congratulations to them, and to all the Fellows this year (especially my collaborator Divesh Srivastava)

Awards from the joint math meetings, and other notes..

It's the new year !! apparently, being on twitter makes blogging frequency drop, because the throwaway information one might blog about just gets tweeted. This is not a bad thing in general.

I've been away in India for much of the winter break, after dealing with the NSF proposal deadlines. On a side note, for anyone complaining about the SODA deadline close to the July 4 weekend, the NSF Dec 17 deadline is MUCH worse. I've submitted proposals now from a cruise ship in Hawaii and at 2:30 in the morning from my parent's place in Bangalore. argghhh

The Joint Math meetings are wrapping up in New Orleans, and award news is beginning to trickle out. Muthu mentions the prizes for Assaf Naor and Ingrid Daubechies. Much to my surprise and great pleasure, the wonderful and entertaining overhang papers by Paterson, Peres, Thorup, Winkler, and Zwick were given the David Robbins Prize for

 a paper with the following characteristics: it shall report on novel research in algebra, combinatorics or discrete mathematics and shall have a signifi cant experimental component; and it shall be on a topic which is broadly accessible and shall provide a simple statement of the problem and clear exposition of the work

The citation for their work is:

The Mathematical Association of America proudly awards the 2011 David P. Robbins Prize to Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, and Uri Zwick for their innovative work on two papers: “Overhang,” American Mathematical Monthly 116, January 2009;
“Maximum Overhang,” American Mathematical Monthly 116, December 2009.

The two papers together solve, to within a constant factor, the classic problem of stacking blocks on a table to achieve the maximum possible overhang, i.e., reaching out the furthest horizontal distance from the edge of the table. The January paper was written by Paterson and Zwick, and the December paper was written by all five people named above. The January paper proves the surprising result that n blocks can be (cunningly) stacked using suitable counterbalancing to achieve an overhang proportional to $n^{1/3}$. (Many people have assumed that the overhang of about log n, given by the standard calculus exercise, is optimal.)
The December paper gave a complementary argument showing that an overhang proportional to n(1/3) is, in fact, the largest possible for any balanced stack.

The papers describe an impressive result in discrete mathematics; the problem is easily understood and the arguments, despite their depth, are easily accessible to any motivated undergraduate.

In other news, cstheory is humming along after the winter break. We're closing on in 3000 users. I'm always hoping for more on-target questions, especially in areas like approximations, geometry and AGT: complexity theory seems over-represented (which isn't a problem, but diversity is great!). We're hoping to develop some formal links with SIGACT fairly soon: stay tuned.

ACM Fellows

The ACM just announced the 2010 Fellows, and there are many theoreticians, and many people that I know - congratulations to all !!

Theoreticians on the list:

• Jennifer Chayes
• Anne Condon
• Michael Jordan
• Phil Klein
• Muthu Muthukrishnan
• Pavel Pevzner
• Dan Spielman
• Subhash Suri

Also congratulations to Kathleen Fisher, Fernando Pereira, and Lydia Kavraki, ex-colleagues and collaborators.

Quick note

(am posting this from 37000 ft. isn't technology cool ?)

The clustering series will be on hiatus for a few days while I wrap up some more pressing deadlines. It will restart two weeks from now.

Congratulations to Adam Smith and Sean Hallgren on getting a PECASE award. See what creating a new blog can do !

Godel Prize

The ACM site isn't updated yet (here's the press release), but Michael M informs us that Vadhan, Reingold and Wigderson just won the Godel prize, most likely for their paper on the zig-zag graph product, which had a major role in and for Reingold's proof that SL = L. These were inspiration for Dinur's combinatorial PCP theorem.

Congratulations !

Barbara Liskov wins the Turing Award

Via MM comes this news:

ACM, the Association for Computing Machinery, has named Barbara Liskov of the Massachusetts Institute of Technology (MIT) the winner of the 2008 ACM A.M. Turing Award. The award cites Liskov for her foundational innovations to designing and building the pervasive computer system designs that power daily life. Her achievements in programming language design have made software more reliable and easier to maintain. They are now the basis of every important programming language since 1975, including Ada, C++, Java, and C#. The Turing Award, widely considered the "Nobel Prize in Computing," is named for the British mathematician Alan M. Turing. The award carries a $250,000 prize, with financial support provided by Intel Corporation and Google Inc.

The first U.S. woman to be awarded a Ph.D. from a computer science department (in 1968 from Stanford University), Liskov revolutionized the programming field with groundbreaking research that underpins virtually every modern computer application for both consumers and businesses. Her contributions have led to fundamental changes in building the computer software programs that form the infrastructure of our information-based society. Her legacy has made software systems more accessible, reliable, and secure 24/7.

ACM Fellows, 2008 edition

ACM has announced its Fellows for 2008. Familar names on the list include:

• Sanjeev Arora
• Ken Clarkson.
• Steve Cook
• Michel Goemans
• Ian Munro
• Madhu Sudan

In the related area of game theory, Xiaotie Deng and Tuomas Sandholm were honored as well. Congratulations to all the winners !

(HT: Michael Trick)

The Katayanagi Prize

Via the Baconmeister (er.. the Quantum Pontiff), we hear that Christos Papadimitriou and Erik Demaine have received the Katayanagi Prize. Christos gets it for "research excellence":

The Katyanagi Prize for Research Excellence will be awarded annually to an established researcher with a record of outstanding, and sustained achievement.

and Erik gets it for "emerging research leadership":

The Katyanagi Emerging Leadership Prize will be awarded annually to an individual recognized as an emerging research leader.

Congratulations to both of them, (and do read the Dr. Dobbs interview with Christos, where he shows that he knows what "Guitar Hero" is :))

2007 ACM Turing Award, and a perspective on model checking.

The 2007 Turing Award was awarded to Edmund Clarke, E. Allen Emerson and Joseph Sifakis for their work on model checking. In our "theory A" cocoon, we tend not to pay attention to much "theory B" work, and model checking is one of the shining stars in theory B, with a rich theory and immense practical value.

I am not competent to discuss model checking at any level, and so I asked someone who is ! Ganesh Gopalakrishnan is a colleague of mine at the U. and heads our Formal Verification group. I asked him if he could write a perspective on model checking, and he kindly agreed. What follows is his piece (with URLs added by me). As usual, all credit to him, and any mistakes in transcribing are my fault alone.

A Perspective On Model Checking
Ganesh Gopalakrishnan

One of the earliest attempts at proving the correctness of a program was by Alan Turing in 1949. The activity was raised to a much more prominent level of interest and importance through the works of Dijkstra, Hoare, and others. Yet, the enterprise of "Program Verification" was met with more noticeable failures than successes in the 1970's, due to its inability to make a dent on practice. The introduction of Temporal Logic for modeling concurrent systems (for which Amir Pnueli won the 1996 Turing Award) was the first attempt at shifting the attention away from the impossibly difficult task of 'whole program verification' to a much more tractable focus on verifying the reactive aspects of concurrency.

Looking back, this enterprise did not meet with the expected degree of success, as Temporal Logic reasoning was still based on `deduction' (proof from first principles). From an engineer's perspective, what was needed was a simple way to specify the classes of "legal and illegal waveforms" a system can produce on its signals / variables, and an efficient way of checking that all those waveforms are contained in the set of "legal waveforms" as can be specified through temporal properties. In other words, it was sufficient to show that finite state machines (or finite state control skeletons of programs) served as *models* for a catalog of desired temporal properties.

This was essentially the approach of model checking. It immediately took off as a practically viable method for debugging concurrent systems; the approach guaranteed exhaustive verification for small instances of a problem. In practice it meant that all relevant corner cases were considered in the confines of afforable resource budgets. This was the gist of Allen Emerson's contribution in his PhD dissertation which he wrote under Ed Clarke's guidance. A parallel effort underway at France in Joseph Sifakis's group also arrived at the same pragmatic approach to verification. Model checking was given crucial impetus by Ken McMillan who, using the technology of Binary Decision Diagrams formulated and popularized by Randy Bryant, developed the highly efficient Symbolic Model Checking approach. The technology has since then skyrocketed in its adoption rate.

Today, model checking and its derivatives are part of every verification tool used to debug digital hardware. While "full verification" is not the goal (and is largely a meaningless term), the ability of model checkers to find *high quality bugs* is uncanny. It is those bugs that escape simulation, and may not even manifest in hardware that operates at the rate of GHz. Some of the error traces produced by model checkers are only about two dozen steps long; yet, if one imagines the number of reachable nodes in a tree with arity (branching factor) 2000 in two dozen steps, one understands why conventional approaches to testing miss bugs: they have to make the same lucky "1 in 2000" choices two dozen times in a row. A model checker can often get away by not really modeling these choices explicitly. Reduction techniques allow model checkers to detect and avoid exploring many "equivalent" behaviors. In that sense, model checking is one of the most powerful "test acceleration technologies" that mankind has invented.

Today, microprocessor companies employ several kinds of model checkers. In software, Bell Labs (mainly before its collapse), JPL, NASA, and Microsoft (to name a few) have had tremendous success using model checking for verifying device drivers, switch software, and flight control software. Speaking more generally, anything with a finite state structure (e.g., decision processes, reliability models, planning in AI) can be approached through model checking.

Aftermatter:

• Daniel Jackson (MIT), "With its dramatic successes in automatically detecting design errors (mainly in hardware and protocols), model checking has recently rescued the reputation of formal methods." (source)
• "Proofs of programs are too boring for the social process of mathematics to work." DeMillo et al in CACM 1979).
  

Levi Conant Prize for Hoory, Linial and Wigderson

The joint meetings of the AMS and MAA are going on right now, and among the prizes being awarded is the Levi L. Conant Prize for the best expository article in the Notices or the Bulletin of the AMS in the last 5 years. One of the two awardees is the group consisting of Shlomo Hoory, Nati Linial and Avi Wigderson, for their article 'Expander graphs and their applications' in the Bulletin of the AMS (here's the related course).

Congratulations ! On a side note, I'm truly impressed by the number of prizes awarded for articles that are expository or targeted at the general public. I don't think that the mere creation of prizes encourages people to write such articles; rather, the existence of such prizes is a post facto demonstration of the intrinsic value attributed to exposition in the mathematics community.

Leibniz Prize

Via an anonymous commenter comes the news that Susanne Albers is one of the 2008 Leibniz Prize winners. This is the most prestigious science award in Germany (and that's all of science, not just computer science). Going back over the list of past winners, it seems (and everything's in German, so I could be wrong here) that the last theory prize winner was Gunter Ziegler, back in 2001. Susanne Albers, for those who don't know, works in online algorithms, approximations, and algorithmic game theory.

From the Leibniz Prize page:

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. Up to ten prizes are awarded annually with a maximum of €2.5 million per award. The prize is awarded from a slate of nominations put forward by third parties. The prizewinner is selected by the Joint Committee on the basis of a recommendation from the Nominations Committee for the Leibniz Programme.

The Leibniz Prize is administered by the DFG, which according to Wikipedia translates to the German Research Foundation, which would make it the equivalent of the NSF, and the Leibniz Prize roughly comparable to the NSF's Waterman Prize.

Update: here's the announcement (in German)

2007 ACM Fellows

A huge crop of algorithms/complexity folks have been named ACM Fellows in this year's batch of awards: among them

• Rajeev Alur
• Avrim Blum
• Andrei Broder
• Danny Dolev
• Rodney Downey
• Tao Jiang (thanks, Anon)
  
• Lance Fortnow
• Rajeev Motwani

Congratulations to all !

(12/6): A special congratulations also to Rajeev Motwani (my research "father") and Lance (my blog "father") :)

This year's Godel Prize

The 2007 Godel Prize goes to Alexander Razborov and Steven Rudich for their paper, "Natural Proofs" (JCSS Vol 55. No. 1, 1997).

I'd like to think that Godel himself would have approved of this particular award, given the mind-bending nature of the Razborov-Rudich result. To use Scott Aaronson's loose formulation, their result can be summarized as

The reason P != NP is so difficult to prove is that P != NP

Computational Complexity (is it the Lance-blog, or the Bill-blog, or a Lance-post in the Bill-blog, or a Lance-post in the Bill-blog-that-used-to-be-Lance's-blog?), and In Theory have detailed explanations of the RR result, and do a far better job than I can do here.

To put it in perspective, the Razborov-Rudich result is a "meta-result": it says that no proofs of a certain kind (the so-called natural proofs) can be used to prove P != NP, unless other hardness assumptions break to begin with. Another example of a meta-result is the (older) result by Baker, Gill and Solovay that the P=NP question does not relativize (i.e cannot be proved using methods that hold under the application of oracles).

Razborov-Rudich really put a shaft in methods for separating P and NP (see this pessimistic post by Lance). If only all the P vs NP cranks actually tried examining proofs like this before wasting all those valuable bits on comp.theory ;)

(HT: [LB, UB] and Process Algebra Diary).

Silvio Micali elected to the NAS

The National Academy of Sciences just announced 72 new members, among them Silvio Micali from MIT. For those who may not know, he's famous for his work in pseudorandomness, cryptography, and interactive proof systems. Among his many awards are the Godel Prize in 1993 and being named a Fellow of the AAAS in 2003.

Knuth Prize

Nancy Lynch from MIT has been awarded this (one and half) year's Knuth Prize for her work in reliability of distributed computing. I remember first hearing about her work when I studied distributed computing and Byzantine agreement problems back in IITK.

This has been a good (and well deserved) year for women in computing: first Frances Allen, and now Nancy Lynch.

Fran Allen, Turing Award, 2006

Fran Allen, Fellow Emerita at IBM, has been named this year's Turing Award winner. She is also the first woman to win this award.

Streaming Algorithms

This year's Gödel Prize went to Noga Alon, Yossi Matias and Maro Szegedy for their 1996 paper titled 'The space complexity of approximating the frequency moments". Why ? What was so great about this paper (which we shall call the 'AMS' paper) ?

If you study databases for a living, or work with large data sets, you will know that the amounts of data that computers are being asked to process is growing astronomically. Google crawls over 8 billion pages on a regular basis, and if you start monitoring data on networks, you are looking at gigabytes of fresh data streaming in every day. If you're Walmart for example, you might have sales data showing up every minute, and if you're an astronomer observing on a telescope, again you get humungous (ed: 'humungous' is a technical term that translates as 'really a lot of stuff, and I am too lazy to figure out exactly how much') amounts of data a constant basis.

Most of this data cannot be stored; it is just infeasible, even with storage as cheap as it is, to store everything you get. More often than not, you want to compute a small summary of the data and throw the rest away. Even if you are willing to archive large portions of your data, it is too large to do careful processing over. Most often you will scan the data ONCE, and retain whatever you can maintain usefully. As database folks know well, accessing a disk is a lot cheaper if you do it in sequential order.

Remember though, that memory in your computer is nowhere near as large as your disk. A state of the art PC might have 4GB of RAM, and over 500 GB of disk, and servers have even more disk space, with not necessarily much more RAM. So here's the problem:

If I can't even read my data into memory to process, or I am drinking at this hose that's blasting data at me, how can I compute summaries efficiently with only a small amount of main memory ?

This is the prime motivating question for the area of streaming algorithms, an area of frenetic research in algorithms and databases over the past 10 years. For a survey, read this tech report by S. Muthukrishnan.

The AMS paper looked at the following simple problems on a stream of numbers:

• Can I count the number of unique items ?
  
• Can I estimate the variance of the items ?
  

In general, if I associate the number f_i with the frequency of the number i, can I compute functions of the form F_k = ∑ f_i^k, where F₀ thus denotes the number of unique items, F₁ the sum, F₂ the sum of squares (which can be used to compute variance) and so on.

You might think it's easy to count F₀ and F₁. You'd be partly right. I can count F₁ by adding up all the items as they come in. I need only space to store the sum. But if I want to count the number of unique items, I have to maintain one memory location for each new item that comes in, and that could mean needing n memory locations for n items, which violates the rules of this game (memory used has to be MUCH LESS than the size of the data).

In general, for frequency counts other than F₁, I am in a bind. I can't maintain all the frequencies f_i, because that would need me to maintain as much space as there were distinct items (and in a worst case analysis this is proportional to the size of the data). So what can I do ?

This is the space of problems attacked by AMS: their main contributions were:

• Good news: F₂ can be approximately computed in logarithmic space; in other words, proportional to the space required to store a single element of the stream
• Bad news: if you are not willing to toss coins (use a randomized algorithm) and be content with an approximate solution, you will need space linear in the input stream.
  
• Tight results for different k.

Their paper was the first to use communication complexity to prove lower bounds on stream algorithms. This is too long a topic to get into now, but it is one of the most powerful methods for proving limits on streaming, and most current lower bounds use this idea.

This paper, along with later work by Henzinger, Rajagopalan and Raghavan and Feigenbaum, Kannan, Strauss and Vishwanathan, laid the foundations for the entire field of streaming algorithms. The time was right in the middle 90s for streaming to emerge as a real field with real applications. Interestingly, some of the nascent ideas date back much further (to a paper by Flajolet and Martin in 1983 for computing F₀, and a paper by Morris on computing F₁ in log log n space (!) in 1978, in the CACM-as-a-good-technical-publication era).

The field has expanded greatly since AMS, but the problems they studied are still of great interest. In fact at this very STOC, a paper by Indyk and Woodruff closes the final open problems left behind by the AMS paper.

Tags: streaming, frequency, moments