The Valiant brothers report from ICS

Gregory and Paul report from the ICS conference in this guest post:

The inaugural Innovations in Computer Science conference was held in Beijing last week, and if the amazingly high spirits of the participants are anything to go by, the conference was a success.  Our hosts at Tsinghua University’s Institute for Theoretical Computer Science (ITCS) stepped in to an unusual degree to ensure that, despite Beijing’s worst snowstorm in 50 years, we were warm, happy, and on schedule.

One of the talks we enjoyed the most was the paper of Barasz and Vempala, “A New Approach to Strongly Polynomial Linear Programming”, presented on short notice by Avrim Blum. (Avrim has now earned the top spot on our list of substitute presenters.)  The paper introduces a class of algorithms that combines the best aspects of the simplex method and interior point methods in the hopes of lighting the way to a strongly polynomial algorithm for linear programming.  Simplex algorithms, since they are inherently combinatorial in nature, have the unique advantage of having a running time independent of the bit-complexity of their inputs, but analyses of this running time soon get lost in the maze described by the surface of high-dimensional polytopes.  Interior point methods, on the other hand, bypass the intricacies of the surface by taking a “short cut” through the center of the polytope.  What this paper describes is essentially a variant of the simplex method whose vertex-to-vertex transition rule allows for such “short cuts”.   Their main technical results–that the proposed algorithms run efficiently on a class of instances containing all known hard instances for simplex methods–provide ample motivation for follow-up work.   This paper seems to epitomize the objectives of the conference: without the onus of intricate technicalities, it puts forward a new idea that could open up a promising new direction of research.

Perhaps stemming from the idealistic call for papers, and the fact that this was the first meeting of a forward-looking conference, there was a feeling of optimistic camaraderie in the air which could be said to culminate in the final discussion session. The discussion covered reflections on the ICS papers, some plugs for undernourished research areas (most notably Vijay Vazarani’s call to arms to tackle the problems of convex programming with the tools of combinatorial optimization), and a section chaired by next year’s ICS chair, Bernard Chazelle, on what one audience member dubbed “innovations in conference organization”.

The first and last papers of the conference were highlighted by Shafi Goldwasser as providing much-needed input from the theory community to the growing reality of multi-core computing.  The last paper, by Avinatan Hassidim “Cache Replacement Policies for Multicore Processors” generalized the standard caching analyses to the now very pertinent case where multiple cores have access to a single shared cache, and showed that for standard caching algorithms to be efficient, the cache size would need to be prohibitively large.  This has the counterintuitive implication that making caches private would actually help performance.  The opening paper of the conference, by Applebaum, Ishai, and Kushilevitz, “Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?” while not mentioning multicore computation at all, has clear implications for it: cellular automata are in some sense a caricature of the multicore world, where functions requiring only local inputs can be computed in a single step, but communication is slow and tricky.  In this model, they demonstrate encryption, pseudorandom generators, and commitment schemes (under a standard coding theory assumption) that all take just a single step of the cellular automaton, while showing the corresponding impossibility of decryption or signature schemes.

The conference concluded with a lively discussion of suggestions for next year’s ICS.  A popular suggestion was that the format of the sessions should have more variety to explicitly welcome innovation in a wide variety of forms: from traditional papers with theorems and proofs, to surveys/tutorials of promising new directions or techniques (perhaps chosen from a set of submissions), to a formal (refereed) ongoing projects session which may include summaries of false starts, attempts, or background material as an introduction to a problem or set of problems.  (Someone noted that typical open problem sessions are often filled with people’s throw-away problems: a mix of the impossible and the not-worth-my-time; injecting some formality and prestige might change this.)  And, of course, as innovation does not happen in lock-step, a bit more unstructured time for chatting might help.

Along the lines of encouraging more responses to the papers presented, the committee mentioned they had initially planned to have a very brief (five minute?) panel discussion after each session, where volunteers or committee members who, having previously read each of the papers just presented, would provide some contrasting perspective.  This is perhaps motivated by the fact that no amount of perfectly honed rhetoric from an author can match the impact of an “I liked *this* about it” from an impartial third party.

One final point that was touched on was that an increasing fraction of conferences are being videotaped, but these videos never seem to appear online in an accessible way that aims to recreate the experience of going to a talk — perhaps all it would take is something as simple as a webpage with video on one side of the page, and navigable powerpoint slides on the other side of the page.

We look forward to seeing some of these proposals–both mathematical and logistic–carried out in next year’s ICS.   It is certainly a conference to keep an eye on.



Advertisement