16/10/2015 - Constantin Enea awarded ERC Starting Grant 2015 The project FOVEDIS aims at developing automated formal methods for building reliable geo-distributed software systems dealing with large numbers of users which are distributed across wide geographical areas, and who generate and exchange huge amounts of data. The project focuses on distributed data structures (DDS), which are critical components of such systems and which are responsible for fast access, transformation, and exchange of data across large-scale networks. The main objectives are to develop (1) coherent formal specifications that provide precise requirements at design time and explicit guarantees during their usage, (2) programming principles, compatible with these specifications, for building applications on top of DDS, and (3) efficient automated reasoning techniques for debugging or validating DDS implementations against their specifications.

15/10/2015 - Zvi Lotker (Ben Gurion University) has obtained a junior chair from FSMP Zvi Lotker, which is professor of Department of Communication Systems Engineering at the Ben Gurion University, has won a junior chair from Fondation Sciences Mathématiques de Paris and will spend the year 2015-2016 in the Algorithms and Complexity, and Distributed Algorithms and Graphs teams of LIAFA. http://www.sciencesmaths-paris.fr/en/junior-chair-245.htm.

12/10/2015 - The diameter or the worldwide road network computed by the Distributed algorithms and graphs team The diameter of a graph is the distance between two points that are furthest apart one from another. The interesting distance notion in a road network is often travel time. Finding the worldwide road network diameter thus amounts to find two points such that the travel time from one to another is maximal. Once such a pair of points is identified, we can compute the shortest path between them to obtain somehow the longest road trip in the world. Computing the diameter of a general graph usually requires to compute all pairwise distances, which is impractical for such a big graph. However, the team has developed heuristics that appear to work fast on many practical graphs including road networks. Thanks to OpenStreetMap data, the team has thus been able to compute the world road diameter (and the diameter of various restricted parts of the network). You can visualize this on http://gang.inria.fr/road.

01/09/2015 - Mai Gehrke awarded ERC Advanced Grant 2015 The project DuaLL is about duality in Formal Languages and Logic, adopting a unifying approach to complexity and semantics. Dualities between algebraic and topological structure are pervasive in mathematics, and toggling back and forth between them has often been associated with important breakthroughs. The main objective of this project is to bring such topo-algebraic dualities to bear on a number of subjects in theoretical computer science thereby advancing, systematizing, and unifying them. (Translated from the CNRS website)

01/07/2015 - Amos Korman awarded ERC Consolidated Grant 2015 The interdisciplinary project Distributed Biological Algorithms (DBA) aims at demonstrating the usefulness of a distributed algorithmic perspective in understanding complex biological systems. The focus is on the biology domain of collective animal behaviour. The project suggests new methodologies for combining theoretical algorithmic results with experimental measurements of biological parameters. (Translated from the CNRS website)

17/04/2015 - The first results of the investigation Algopol quoted by Le Monde An investigation on the uses of Facebook realized in the ANR project Algopol whose Liafa is a partner, bringing together sociologists and computer scientists. The first results show three user profiles. Links : Le Monde newspaper article, first results.

12/01/2015 - A trimester dedicated to combinatorics at IHP! IHP just announced the acceptance of a trimester dedicated to combinatorics for the year 2017 (from January to March). This thimester will have the following title: Combinatorics and interactions: at the interface between physics and mathematics, theory of representations and probabilities. It will be organized by Marie Albenque (CNRS LIX), Gaetan Borot (Bonn), Guillaume Chapuy (CNRS LIAFA), Valentin Feray (Zurich) and the scientific committe will be composed of Alexei Borodin (MIT), Jérémie Bouttier (CEA et ENS), Sylvie Corteel (CNRS, LIAFA), Bertrand Eynard (CEA), Ian Goulden (University of Waterloo) and Jean-François Le Gall (Orsay). This trimester will be partially founded by the Emergences project "Combinatoire à Paris" which is sponsored by the Fondation Sciences Mathématiques de Paris http://combinatoire-a-paris.math.cnrs.fr/

18/12/2014 - Winter school "Big Data" Winter school "Big Data" organized from 19 to 23 January 2015 at École Normale Supérieure de Lyon by Nicolas Schabanel. Website: http://www.liafa.univ-paris-diderot.fr/~nschaban/MSC/2014-2015/ER/index.html Registration: http://www.ens-lyon.fr/DI/?p=3312

07/10/2014 - Pierre Fraigniaud is awarded the Prize for Innovation in Distributed Computing (SIROCCO award) 2014 During the conference SIROCCO 2014 (International Colloquium on Structural Information and Communication Complexity), Pierre Fraigniaud, Senior Researcher at CNRS, was awarded the Prize for Innovation in Distributed Computing (aka SIROCCO award) for his contribution to the understanding of routing in social networks. http://en.wikipedia.org/wiki/Prize_for_Innovation_in_Distributed_Computing https://sites.google.com/site/sirocco2014japan/sirocco-award

29/09/2014 - Sylvie Corteel is Editor in Chief of the Journal of Combinatorial Theory Series A Sylvie Corteel, Senior Researcher at CNRS, becomes Editor in Chief of the Journal of Combinatorial Theory Series A. http://www.journals.elsevier.com/journal-of-combinatorial-theory-series-a/

01/09/2014 - Nomination of Jean Mairesse as Scientific Assistant Director at INS2I Jean Mairesse, Senior Researcher at CNRS, was nominated the 1st september 2014 Scientific Assistant Director at INS2I, where he is in charge of the "computer science" domain. http://www.cnrs.fr/ins2i/spip.php?article865

15/06/2014 - The application Algopol receives the first prize for collaborative research at Futur en Seine The 15th of June 2014, the application Algopol, implemented by Stéphane Raux, PhD student at LIAFA/Linkfluence, and conceived by Irène Bastard, PhD student in solciology at Orange Labs within the ANR project Algopol (Cams, LIAFA, Orange Labs, Linkfluence), to study Facebook usages, has received the prize "Or" for collaborative research at the festival Futur en Seine organized by Cap Digital. Link towards the website of the application : http://app.algopol.fr/ Prizes and awards of Futur En Seine : http://www.futur-en-seine.fr/fens2014/prix-recompenses/

06/03/2014 - Lauren Williams (University of California, Berkeley) has obtained a junior chair from FSMP Lauren Williams, which is Associate Professor of Mathematics at the University of California-Berkeley, has won a junior chair from Fondation Sciences Mathématiques de Paris and will spend the year 2014-2015 in the Combinatorics team of LIAFA. http://www.sciencesmaths-paris.fr/en/chaire-junior-245.htm

06/03/2014 - Jean-Éric Pin becomes an EATCS fellow Jean-Éric Pin which is Director of Research in the Automata and Application team of LIAFA is among the first recipient of an EATCS fellowship for his outstanding contributions to the algebraic theory of automata and languages in connection with logic, topology, and combinatorics and service to the European TCS community. http://www.liafa.univ-paris-diderot.fr/~jep/indexAnglais.html http://eatcs.org/index.php/component/content/article/1-news/1863-atcs-fellows-class-of-2014-named

01/01/2014 - Creation of the Federation Paris Centre for Quantum Computing PCQC The Paris Centre for Quantum Computing (PCQC) brings together computer scientists, theoretical & experimental physicists and mathematicians that work in Paris. PCQC aspires to break the ground for the establishment of new and realistic applications in quantum information processing by uniquely combining concepts from quantum computation, communication and cryptography and eventually lead the way from a Personal Computer (PC) to a Quantum Computer (QC). The administrative supervisors of the federation are the University Paris Diderot, the Telecom ParisTech and the CNRS. At the same time, the following institutions - Université Pierre et Marie Curie (UPMC), INRIA Paris, Commissariat à l'Energie Atomique et Aux Energies Alternatives (CEA), Institut d'Optique, Université Paris-Sud - also participate in PCQC through their researchers-members of the centre. More details at http://www.pcqc.fr.

01/01/2014 - Creation of the Federation in Theoretical Computer Science of Paris Diderot The TCS federation of Paris Diderot gathers together the two CNRS labs in Computer Science at the university : LIAFA and PPS. Its main objective is to promote scientific interactions between the two labs, and, more generally, to bringing the two labs closer for preparing their merging on January 1st, 2016. The federation includes more than a hundred university faculties and of CNRS or INRIA researchers, for a total of roughly 170 members. The administrative supervisors of the federation are the University Paris Diderot and the CNRS (through its two institutes INS2I and INSMI). The federation also includes two INRIA project-teams : Pi-R2 and GANG. Website: http://www.fifp.univ-paris-diderot.fr

17/12/2013 - Launching of the application Algopol, investigation on online sociability In the context of the french ANR Project Algorpol (involving Cams, LIAFA, Orange Labs, Linkfluence), a large investigation on online sociability has been launched under the form of a Facebook application which has been developed by Stéphane Raux, PhD student at LIAFA/Linkfluence, and designed together with Irène Bastard, PhD Student in Sociology at Orange Labs. This investigation is particularly original because of the two following aspects: first it relies both on the analysis of networks of big data and on traditional ethonographcial methods (as face to face interviews); second it is adressed to a representative panel of internet surfers, panel provided by the CSA institute. Link towards the website of the application : http://app.algopol.fr/ The methodology applied for this work is decribed on this webpage : http://www.internetactu.net/2013/12/13/travail-et-travailleurs-de-la-donnee/ This application has also been mentioned on the blog Science of the french newspaper LeMonde.fr : http://www.lemonde.fr/sciences/article/2013/12/12/quand-la-recherche-like-facebook_4332566_1650684.html

30/10/2013 - Invited talk by Frédéric Magniez at the CNRS forum "Les Fondamentales" From November 14 - 16 2013, the CNRS is organizing a forum at the Sorbonne entitled "Les Fondamentales" whose objective is to share the meaning and reach of its research. The central theme of this meeting involving researchers from various areas is the question of "What remains to be discovered?" During this forum, Frédéric Magniez, member of the LIAFA, will give a talk along with the physicist Philippe Grangier about "The challenges of quantum computers". The talk will take place on November 15 2013 from 3:40PM to 4:40PM in the Amphithéâtre Liard at the Sorbonne. The website for the forum "Les Fondamentales" is : http://lesfondamentales.cnrs.fr/ The web page for the talk "The challenges of quantum computers" is : http://lesfondamentales.cnrs.fr/programme/debat/les-defis-de-lordinateur-quantique

04/07/2013 - Ahmed Bouajjani nominated senior member of the prestigious Institut Universitaire de France (IUF) Ahmed Bouajjani, professor of computer science at the University Paris Diderot and LIAFA member, has been nominated senior member at the prestigious Institut Universitaire de France (IUF). This nomination is a gratitude of his scientific contributions to the theory of the verification of sequential or concurrent programs.

20/06/2013 - Anna Pappa received a 2013 Google Anita Borg Memorial Scholarship Anna Pappa, doctoral student jointly supervised by Iordanis Kerenidis (LIAFA) and Eleni Diamanti (Télécom), received a 2013 Google Anita Borg Memorial Scholarship. The Google Anita Borg Memorial Scholarship honours the memory of Dr. Anita Borg who devoted her life to encouraging the presence of women in computing. All of the students receiving the scholarships are pursuing degrees in computer science or related fields at universities across Europe, the Middle East and Africa. For more information please visit the following link. http://googleblog.blogspot.fr/2013/06/google-scholarships-recognize-84.html

31/03/2013 - Valérie Berthé awarded Legion of Honor Valérie Berthé was inducted into the Legion of Honor during the Easter 2013 campaign. This title rightly honors the enormous work that Valérie has done for the French mathematics and computer science communities. (Below is a short description of these activities.) Valérie Berthé leads a brilliant career at the CNRS. An alumna of the Ecole Normale Supérieure, she obtained her agrégation in mathematics in 1992 and defended a thesis in pure mathematics in Bordeaux in 1994. She then immediately obtained a position as junior scientist (Chargé de Recherche) at the CNRS in Section 1 (Mathematics), working at the Institute of Mathematics of Luminy (IML). She defended her habilitation in 1999. Her works at the intersection of mathematics and computer science led her to join the LIRMM (Laboratory in computer science, robotics, and microelectronics of Montpellier) in the early 2000s, where she took charge of the Arithmetic Computer Science project of the laboratory's computer science department. She was promoted to senior scientist (Directrice de Recherche) at the CNRS in 2006 in Section 7 (Computer Science), and in 2010 she joined the LIAFA (Laboratory in computer science and algorithms) at the University of Paris Diderot. Since March 2010, she has been adjoint director of the laboratory. The brilliant scientific career of Valérie Berthé briefly summarized above demonstrates her remarkable scientific qualities at the highest international level at the interface of mathematics and computer science (tilings and numbering systems, with applications in discrete geometry and combinatorics). But it is particularly notable that besides her scientific work, Valérie Berthé has also labored intensively for the community during her entire career. For example, from 2007 to 2010, she was charged with managing mathematics-computer science relations for the INS2I (Institute for computer science and its interactions) and INSMI (Institute for mathematical sciences and their interactions) at the CNRS. In 2011, she became adjoint director of the FSMP (Foundation for mathematical sciences of Paris). This foundation for scientific cooperation, founded in 2006, is the only RTRA (Thematic network in advanced research) in France in the mathematical sciences. This network associates 11 laboratories in mathematical sciences and computer science, and brings together over 1200 researchers. The FSMP was also awarded a LabEx (Laboratory of excellence), the LabEx SMP. In addition, Valérie Berthé is a member of many scientific councils, including the City of Paris' council, the CIRM's (Center for international meetings in mathematics), and the RAGAAD's (African network for geometry and algebra applied to development). She is also a member of the CNU (National university committee) in section 25 (mathematics), and is or was a committee member for many national and international scientific programs. Due to the quality of her research and the dedication she has shown to the scientific community in her work, Valérie Berthé has performed a remarkable service for the national and international community. She is without doubt one of the foremost scientific personalities whose research and organizing activities have allowed the French community in theoretical computer science to establish its position at the highest international level.

13/03/2013 - Journées d'Informatique Fondamentale de Paris Diderot To inaugurate the new premises, the computer science departments of the Université Paris Diderot - Paris 7, LIAFA and PPS, organise a series of talks from April 22 to 26, 2013. A ceremony for the awarding of Palmes Académiques to Maurice Nivat will take place on Wednesday, April 24, at 18:00, preceded by a special session dedicated to the CNRS silver medal of Pierre Fraigniaud. http://www.liafa.univ-paris-diderot.fr/jifp/

07/09/2012 - FPSAC'13 to be held at Universty of Paris Diderot - Paris 7, organized by the LIAFA The Combinatorics team of the LIAFA is organizing the FPSAC'13 conference from June 24 to 28, 2013 to be held at the University of Paris Diderot - Paris 7. This will be the 25th meeting of this conference, which is the most important international conference in combinatorics and brings together 180 combinatorialists from all over the world each year. http://www.liafa.univ-paris-diderot.fr/fpsac13 The conference's permanent website: http://www.fpsac.org/

30/08/2012 - Iordanis Kerenidis awarded ERC Starting Grant 2012 Iordanis Kerenidis was awarded an ERC Starting Grant 2012 for his project "Quantum communication and cryptography". Iordanis Kerenidis received his doctorate from the University of California Berkeley in 2004. After a postdoc at MIT, he joined the CNRS as a researcher and is currently based at the LIAFA at University of Paris 7. His ERC project "Quantum communication and cryptography" was awarded an ERC Starting Grant 2012, and will study the future of communication technologies where the network will be composed of both classical and quantum agents who wish to be able to communication efficiently and securely. The goals of his project include: design new cryptographic primitives secure even against quantum adversaries and to implement them using state-of-the-art photonic systems, studying efficient quantum communication and multi-player games, and understanding quantum mechanisms and complexity theory using quantum information and quantum cryptography. (Translated from the CNRS website.)

25/06/2012 - Founding of the LEA FILOFOCS with Tel Aviv University The LEA "FILOFOCS" was founded on January 1st, 2012 between the LIAFA and the Blavatnik School of Computer Science of Tel Aviv University. This is the third LEA created in partnership with Israel, and will be active for four years. The LEA is open to the participation of other laboratories both French and Israeli. The two leaders of the project are Adi Rosen (DR CNRS at LIAFA) and Benny Chor (Professor at the Blavatnik School of Computer Science). The goal of the LEA FILOFOCS is to create high quality scientific research in theoretical computer science, to encourage the development of new collaborations in this area, and to develop a framework that will allow for long-term exchange between the French and Israeli scientific communities about their methods and areas of expertise, in particular for young researchers. To accomplish this, the LEA FILOFOCS will organize various events: an annual bilateral workshop alternating between France and Israel, Spring or Summer Schools in the two countries, exchange of PhD students and postdocs, and visits between both junior and senior researchers. The LEA FILOFOCS is the first large-scale cooperation between the CNRS and Tel Aviv University, which has the most joint publications with the CNRS out of all Israeli universities. (Translated from the CNRS website.)

07/06/2012 - Translated video from the CNRS website "Turing Model (The)" Alan Turing was a mathematician, cryptographer, a pioneer in computer science, artificial intelligence, and morphogenetic processes. For the centenary celebration of his birthday, this film introduces us to an exceptional man by tracing his life, work, and legacy. By speaking to researchers working in the many different disciplines influenced by Turing, we discover who he was, what he discovered and the impact of his work on to the present day. The video shows us the circumstances under which a new science emerged: computer science. While the father of computer science and artificial intelligence might seem rather unfamiliar to the majority of French people, he nevertheless is a popular and celebrated figure among scientists, and the passion that drove Turing is still alive and well and drives researchers to this day. This video was produced with help from Jean Mairesse and Laurent Bienvenu, CNRS researchers at the LIAFA. (Translated from the CNRS website.)

16/04/2012 - Pierre Fraigniaud awarded Silver Medal of the CNRS Pierre Fraigniaud was awarded the 2012 Silver Medal of the CNRS for the Institute of Information Sciences and their Interactions (INS2I). Each year, this medal recognizes a researcher for the originality, quality, and importance of their work, both on a national and international scale. After his studies at the ENSIMAG and at the Université Joseph Fourier de Grenoble, Pierre Fraigniaud defended his thesis at ENS Lyon in 1990. He joined the CNRS in 1991, and was a member at the LIP in Lyon, at the LRI in Orsay and finally at LIAFA at Paris 7. He is currently the director of the LIAFA. His area of research has evolved from the study of parallel programs for numerical problems, to optimization problems for communication tasks on supercomputers, and finally to the study of distributed algorithms. His recent research in distributed algorithms studies the tradeoffs between the performance of a distributed computation versus the amount of initial information the processors have about their environment. His research has a wide range of applications, from the design of communication networks in various settings (including "peer-to-peer" settings) to the study of social networks (including "small world" phenomena).

28/03/2012 - Fu Song and Tayssir Touili awarded EASST best paper award at ETAPS 2012 Fu Song and Tayssir Touili. "Pushdown Model-Checking for Malware Detection". In Proceedings 18th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2012). Volume 7214 of Lecture Notes in Computer Science. Springer. 2012. This work describes a new approach to detecting computer viruses that is more efficient and accurate than existing anti-virus techniques. Indeed, no existing method can always reliably detect whether or not an application in some application market is legitimate. Existing virus detection techniques are based on looking for suspicious signatures in the code via a kind of pattern matching. However, it is extremely easy for a virus designer to bypass these detectors by changing the signature of their virus, even very slightly, while keeping the same viral behavior. To overcome this problem, analyzing the behavior of viruses is a more promising technique than analyzing their code syntactically, as is currently the case. Model checking techniques are particularly appropriate for the analysis of systems' behavior, and in this article we propose innovative techniques derived from model-checking that allow us to detect viruses. These techniques have been implemented in a tool that is able to detect over 400 viruses. Several of these viruses were not detectable by well-known anti-virus software such as Kaspersky, Avira, or Avast.

26/03/2012 - Spring School in Theoretical Computer Science, 2012 The Spring School in Theoretical Computer Science (EPIT) is a veritable institution in Theoretical Computer Science in France. The school was founded by Maurice Nivat in 1973, and in its 39 years of existence has covered a large spectrum of major topics in theoretical computer science, and it is now an essential meeting place for new generations of researchers in the area. 2012 edition: This year, the focus is on probabilistic algorithms, with an emphasis on their mechanics and lower bounds. While algorithms form the common foundation of the computer science community, many young researchers remain somewhat unfamiliar with probabilistic algorithms. This is despite the fact that probabilistic algorithms have fundamentally changed our view of computer science, from applications in the real world that they allow to notions of complexity that they have forced us to reconsider. This school will give an introduction to some aspects that have had the most impect. Speakers: - Iordanis Kerenidis (LIAFA, Paris 7) - Claire Mathieu (Brown University) - Frédéric Magniez (LIAFA, Paris 7) - Andrew McGregor (University of Massachussets) - Nicolas Schabanel (LIAFA, Paris 7) - Ronald de Wolf (CWI, Amsterdam) Scientific committee : Iordanis Kerenidis, Claire Mathieu, Frédéric Magniez Organization (LIAFA, Paris 7) : Nathanaël François, Iordanis Kerenidis, Christian Konrad, Frédéric Magniez

09/12/2011 - André Chailloux awarded the Gilles Kahn prize for his thesis The SiF prize was created in 1998 to recognize the best thesis in computer science of the year. Gilles Kahn, believing firmly in the importance of promoting promising young researchers in our discipline, presided over the first three prize committees. In his honor, in 2007 the prize was renamed the Gilles Kahn prize and has gained the sponsorship of the Academy of Sciences, thus commemorating one of its most preemiment members. The 2011 prize was awarded to André Chailloux for his thesis "Quantum Coin Flipping and Bit Commitment: Optimal Bounds, Practical Constructions, and Computational Security", written at the Laboratoire de Recherche en Informatique (CNRS/Université Paris-Sud 11), advised by Iordanis Kerenidis, CNRS researcher at the LIAFA.

08/12/2011 - Inaugural conference for the LEA Struco with Charles University of Prague, Czech Republic STRUCO is an LEA of the CNRS in cooperation joint between IÚUK, Prague and the LIAFA. The primary theme of the laboratory is graph theory, and more specifically: - sparsity of graphs (nowhere dense classes of graphs, bounded expansion classes of graphs) - extremal graph theory - graph coloring - Ramsey theory, universality and morphism duality - graph and matroids algorithms - model checking The LEA focuses on high-level study of fundamental combinatorial objects, with a particular emphasis on comprehending and disseminating the state-of-the-art theories and techniques developed. The obtained insight shall be applied to obtain new results on existing problems as well as to identify directions and questions for future work. The chosen themes of the project cover timely and difficult questions, for which a stable and significant cooperation structure is needed. By gathering an important number of excellent researchers and students, the LEA will create the required environment for making advances, which shall be achieved not only by short-term exchanges of researchers, but also by a strong involvement of Ph. D students in the learning of state-of-the-art techniques and in the international collaborations, thereby ensuring the continued existence of a productive and world-level network in fields belonging to graph theory, combinatorics and theoretical computer science. The LEA is run by two Co-directors. The management of the LEA is jointly provided by : Dr Jean-Sébastien Sereni for CNRS, France, Prof. Jaroslav Nešetřil for Charles University, Czech Republic.

22/12/2010 - Thomas Colcombet awarded the Bronze Medal of the CNRS Thomas Colcombet was awarded the 2010 Bronze Medal of the CNRS for the Institute of Information Sciences and their Interactions (INS2I) in recognition of the brilliant work Thomas has done on automata and their link to logic. The award is given each year in recognition of a young researcher whose work is exceptional in their area.

22/10/2010 - Thomas Colcombet awarded ERC Starting Grant 2010 For its third call for projects, the European Research Council awarded Starting Grants to three researchers at the INS2I and to 35 researchers in total at the CNRS. The program rewards talented young researchers likely to lead innovative projects in various areas of research at a European level (http://erc.europa.eu). After an extremely selective process, Thomas Colcombet, researcher at LIAFA (http://www.liafa.jussieu.fr/~colcombe), was selected for his work on automata theory and its links to logic. (Translated from the CNRS website.) More about this project.