The 40th International Colloquium on Automata, Languages and Programming (ICALP), the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS), took place from 8 to 12 July 2013 in Riga, Latvia.

The main conference has been preceded by series of workshops, taking place on Sunday, 7 July 2013 (i.e., one day before ICALP).


ICALP proceedings will be published in the Springer-Verlag ARCoSS (Advanced Research in Computing and Software Science) subseries of LNCS (Lecture Notes in Computer Science).


EATCS lecture

There will be an EATCS lecture on the occasion of the 40th ICALP given by Jon Kleinberg (Cornell University) on "Algorithms, Networks, and Social Phenomena".

Jon Kleinberg is an American computer scientist and the University Professor of Computer Science at Cornell University known for his work in algorithms and networks.

Kleinberg research focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other online media.

Kleinberg is best known for his work on networks and particularly for his HITS algorithm, also for his work on algorithmic aspects of the small world experiment.

Abstract of invited talk:

We consider the development of computational models for systems involving social networks and large human audiences. In particular, we focus on the spread of information and behavior through such systems, and the ways in which these processes are affected by the underlying network structure.

EATCS General Assembly on 10 July 2013 (18:30)


The General Assembly of the EATCS will start after the excursion. At the end of the excursion, everybody will be delivered to the main building and offered a snack for participating in the General Assembly.


  1. Reports on ICALP 2013
  2. Award of the best student papers
  3. Report on the organization of ICALP 2014 (Philip Bille)
  4. Proposal for ICALP 2015 for approval by the General Assembly (Kazuo Iwama)
  5. Orna Kupferman. The Challenge Facing Women in Academia
  6. Reports from the president, the treasurer and the secretary
  7. Any Other Business

Honorary Degrees

University of Latvia will award Honorary Doctoral degree to two distinct computer scientists:

  • prof. Juris Hartmanis (born in Riga). He is a prominent computer scientist and computational theorist who received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory". At the Cornell University in 1965 he was one of the founders and the first chairman of computer science department (which was one of the first computer science departments in the world).
  • prof. Jozef Gruska (Czech Republic). For development of Computer Science field in Eastern Europe. He is an expert in Theoretical Informatics (Book Foundations in Computing, Thomson Learning, 730 pages, 1997) and Quantum Information Processing (Book Quantum Computing, McGraw Hill Book, 430 pages, 1999). He has over 150 publications.

Both professors will give a short talk during the Award Ceremony.

EATCS Awards

EACTS will award two scientific awards.

2013 EATCS Presburger Award: Erik Demaine (MIT, USA)

Erik Demaine, born in 1981, has made outstanding contributions in several fields of algorithms, namely computational geometry, data structures, graph algorithms and recreational algorithms. In computational geometry and data structures he has solved or made significant progress on classic problems, such as the carpenter’s rule problem, the hinged-dissection problem, the prefix-sum problem, and the dynamic optimality conjecture. In graph algorithms he used the powerful theory of graph minors to develop a suite of algorithms for approximately solving a general family of intractable problems. He also started the new field of computational origami, where his book is the leading authority in the field. His work has shown promising applications to computer graphics, sensor networks, molecular biology, programmable matter, and manufacturing and engineering.

2013 EATCS Award: Martin Dyer (University of Leeds, UK)

Martin Dyer’s scientific contributions span a wide range of topics within Theoretical Computer Science, including the following.

  • Pioneering the development of linear-time algorithms for linear programming in a fixed number of dimensions.
  • Developing probabilistic analysis of algorithms.
  • Discovering the first polynomial-time algorithm for estimating the volume of a high-dimensional convex body.
  • Introducing the elegant and useful path-coupling technique for bounding the mixing time of Markov chains.
  • Discovering fast algorithms for approximate counting.
  • Classifying the complexity of counting problems.
  • Susanne Albers, Humboldt University
  • Jon Kleinberg, Cornell University – EATCS Lecture
  • Orna Kupferman, Hebrew University
  • Daniel Marx, Hungarian Academy of Sciences
  • Paul Spirakis, University of Patras
  • Peter Widmayer, ETH Zürich

The main conference will be preceded by series of workshops, taking place on Sunday 7 July 2013 (i.e., one day before ICALP2013).

List of workshops:

  • Workshop on Automata, Logic, Formal languages, and Algebra (ALFA'13)
  • International Workshop on Approximation, Parameterized and EXact algorithms (APEX 2013)
  • Quantitative Models: Expressiveness and Analysis. Canceled due to technical reasons!
  • Foundations of Network Science (FONES)
  • Learning Theory and Complexity
  • 7th Workshop on Membrane Computing and Biologically Inspired Process Calculi (MeCBIC 2013). Canceled due to technical reasons!
  • Workshop on Quantum and Classical Complexity

Bus excursion (Wednesday, 10 July)

13:30 – departure from the University of Latvia

1. Riga sightseeing by bus: showing the most important historical landmarks of the city centre, including The monument of Freedom, Town hall square and Art-Nouveau buildings.

Bus tour with guide + small walks to major sites

Riga has been named a UNESCO World Heritage Site thanks to the collection of Art-Nouveau buildings that is one of the largest in the world, as well as a city in whose architecture the entire history from 1201 to the present day is reflected.

2. The main exhibition of Riga Motor Museum: dedicated to the historical development of cars, motorbikes and bicycles over the first century of its mass production from the last decade of 19th to the end of 20th century.

Guided tour + time for exploring on your own

3. Museum of the River Daugava: represents an unique history of culture on it’s banks, starting from 8000 BC till nowadays. The building of the Museum is a former dwelling house of the Dole estate, and it was constructed in 1898.

Guided tour of manor and park + time to explore park + quick snack

EATCS General Assembly

The General Assembly of the EATCS will start after the excursion.

At the end of the excursion, everybody will be delivered to the main building and offered a snack for participating in the General Assembly.