Report from ICALP

While EC is taking place in Palo-Alto, I’m just returning from ICALP in Rhodes.  ICALP is the main Thoeretical CS European confernce and is a

friendly and relaxed event with somewhat over 200 participants, many of them being old friends for me.

Many came with families and many spent some of their time on the beach or in other tourist

attractions rather than in the talks.  The program consists of 3 tracks: the largest on Algorithms and Complexity, the

"European CS" track on Logic, Automata, and Languages,

and the new Internet-related track, with the 3 tracks fitting into two parallel sessions.

The main special event during this ICALP was a workshop celebrating Christos Papadimitriou’s 60th birthday.  Dick Karp talked about several

algorithmic problems arising from computational biology.  Laci Lovasz talked about a surprising elegant notion of a limit of a sequence

of graphs.  The idea is that we can say that a sequence of graphs , where is a graph on vertices, is convergent

if for every finite -vertex graph, the fraction of induced -vertex subgraphs of that equals it, has a limit.  For

such convergent sequences, an infinite limit object can naturally be defined, where this object is a measurable function , and

it maintains various properties of the graphs in the sequence. The next two talks were related to Christos’s current field, Algorithmic Game Theory.  I talked

about budgets in multi-unit auctions, and Tim Roughgarden gave an amazingly crisp talk about the robustness of the price of anarchy in congestion games.  He pointed out

a cannonical method used for proving most price-of-anarchy results, and showed that it also bounded the loss incurred in a much wider variety of

equilibrium-like solutions, not just pure-Nash equilibria.  He also showed that this cannonical method is "complete" for congestion games.  The last talk

of the workshop was given by Christos’s long-time collaborator, Mihalis Yannakakis, who gave an interesting narrative that went over

many of the complexity classes that Christos defined

throughout his career (such as approximation classes and PPAD). The whole event was really warm and lovely.

Among the regular talks I attended, the one that caught my imagination most was by John Reif who has been working on "self-assembly"

for the last 10 years and is rarely seen in CS conferences anymore.  The idea is to study

and mimic natural processes where simple building blocks arrange themselves into complex structures (e.g. into DNA).  Theoretical models

for this usually involve 2-dimesional tiles that can fit togther according ot some rules, and this talk gave a probabilistic variant where 1-dimensional tiles

also exhibit some capabilities of this form.

Besides the talk I gave during the workshop, I gave another invited talk describing Google’s auction for TV-ads.

While EC is taking place in Palo-Alto, I just returned from ICALP in Rhodes.  ICALP is the main Theoretical CS European conference and is a friendly, relaxed, and fun event with somewhat over 200 participants.   Many came with families and many spent some of their time on the beach or in other tourist attractions rather than in the talks.  The program consists of 3 tracks: the largest on “Algorithms, automata, complexity and games”, the  “European CS” track on “Logic, semantics and theory of programming”, and the new track on “Foundations of networked computation”, with the 3 tracks fitting into two parallel sessions.

The main special event during this ICALP was a workshop celebrating Christos Papadimitriou’s 60th birthday.  Dick Karp talked about several algorithmic problems arising from computational biology.  Laci Lovasz talked about an elegant notion of a limit of a sequence of graphs.  The idea is that we can say that a sequence of graphs , where is a graph on vertices, is convergent if for every finite -vertex graph, the fraction of induced -vertex subgraphs of that equals it, has a limit.  For such convergent sequences, an infinite limit object can naturally be defined, where this object turnsa out to be  a measurable function , and it maintains various properties of the graphs in the sequence. The next two talks were related to Christos’s current field, Algorithmic Game Theory.  I talked about budgets in multi-unit auctions (paper, presentation), and Tim Roughgarden gave an amazingly crisp talk about the robustness of the price of anarchy in congestion games.  He pointed out a canonical method used for proving most price-of-anarchy results, and showed that it also bounded the loss incurred in a much wider variety of equilibrium-like solutions, not just pure-Nash equilibria.  He also showed that this canonical method is “complete” for congestion games.  The last talk of the workshop was given by Christos’s long-time collaborator, Mihalis Yannakakis, who gave an interesting narrative that went over many of the complexity classes that Christos defined throughout his career (such as approximation classes and PPAD). Ending with a few words from Christos, the whole event was really warm and lovely.

Among the regular talks I attended, the one that caught my imagination was by John Reif who has been working on “self-assembly” for the last 10 years and is rarely seen in CS conferences anymore.  The idea is to study and mimic natural processes where simple building blocks arrange themselves into complex structures (e.g. into DNA).  Theoretical models for this usually involve 2-dimensional tiles that can fit together according to some rules, and this talk gave a probabilistic variant where 1-dimensional tiles also exhibit some capabilities of this form.

Besides the talk I gave during the workshop, I gave another invited talk describing Google’s auction for TV-ads (presentation, paper).

Advertisement