Thematic team Pole Algorithms and discrete structures Algorithms and complexity Head Sophie Laplante Research themes The theory of efficient algorithms is the common base of our research topics, both in classical and in quantum computation. We seek to tackle emerging algorithmic challenges and to understand the limitations of novel computational models. We identify central algorithmic problems, suggest efficient solutions, analyze them, and at the same time try to show their optimality by finding lower bounds on the complexity of the given problems. In classical computation we focus on computational models that take into account various restrictions on the access to the input, including streaming algorithms, online algorithms, distributed algorithms or property testing. In all these areas the development and study of probabilistic tools for approximation are often necessary in order to design algorithms that remain efficient. We also study algorithmic aspects of distributed systems, ranging from network computing to new approaches in the context of animal collective behavior. In the latter framework, we collaborate in parallel with experimental biologists to validate our methodology and our predictions. In quantum computation we try to better understand the contribution of quantum information to computation, cryptography and communication. We are also involved in several experimental projects and industrial partnerships, which complement our theoretical expertise and our international positioning. To learn more: Quantum computing at IRIF. The mutual exchange of ideas and techniques between all these models of computation is an important characteristic of the research carried out within our group. We use complexity theory tools in order to better understand and quantify the limitations of various models for computation, communication, and privacy, as well as to study quantum physics and biological systems from a new standpoint. These tools include communication complexity, query complexity, information theory and algorithmic game theory. Seminar Algorithms and complexity seminar National and international networks Paris Centre for Quantum Computing (PCQC) : In 2014, we co-founded PCQC in Paris. PCQC brings together computer scientists, theoretical & experimental physicists and mathematicians that work in and around Paris. GDR Informatique Mathématique through GT ALGA, GT CoA and GT IQ GDR Information Quantique, Fondements & Applications IRIF-IQC Cooperation on Quantum Information Processing (PICS QIP) French-Israeli Laboratory on Foundations of Computer Science (UMI FILOFOCS) Singapore-French Laboratory for Quantum Physics and Information (UMI MajuLAB) Japanese-French Laboratory for Informatics (UMI JFLI) Openings We are seeking excellent candidates for permanent and postdoctoral positions in classical and quantum computing. We are also happy to welcome motivated and strong students to pursue a PhD or a Master thesis in our group. Topics of interest include (but are not limited to): algorithms, online algorithms, streaming algorithms, approximation algorithms, communication complexity, cryptography, computational game theory, quantum computing, computational applications of logic, randomness in computing, privacy. Further information may be obtained from any of the permanent members of the group. Permanent positions Every year, the CNRS (French National Center for Scientifc Research) has job openings, including some openings for researchers in Computer Science. The application deadline is usually in early February. Details are available on the CNRS website. Faculty positions at the Université Paris Diderot may also be available. The application deadline is usually in March. Details are available on the University website. For those interested in applying to such positions in order to join our group, we recommend to contact one of the permanent members at least three months before the deadline in order to discuss the possibilities and the application process, and to send a CV, a research statement and references to algocomp-apply@irif.fr at least two months before the deadline. Postdoctoral positions Starting dates are usually in September-October but may be negotiable. To apply please send a CV including list of publications, a summary of research, and names and emails of at least three references to algocomp-apply@irif.fr. Before applying please see further instructions, as well as the deadline for applications, at the IRIF postdoc call for applications. The position(s) will be financed either by group resources, or via joint applications of the candidate and the group to external funding sources. PhD and Master Theses For PhD applicants, please contact one of the permanent members no later than spring, since scholarships are allocated just before summer. For Master internships, please contact permanent members individually with your CV, transcripts and a description of your research interests, at least three months before the start of the internship. Teaching We actively participate in teaching algorithms, complexity and quantum computing at the undergraduate and masters level. In the Paris Computer Science Master's Programme (MPRI) we are currently involved in the following courses: Randomness in Complexity, Quantum information and applications, and Quantum Cryptography. Permanent members Name@PhoneOfficePositionPoleTeam Apers Simon @ 01 57 27 94 01 4026 Research Scientist - CNRS ASD algocomp Boura Christina @ 3008 Professor ASD algocomp Couteau Geoffroy @ 01 57 27 92 45 3041 Research Scientist - CNRS ASD algocomp De Rougemont Michel @ 01 57 27 94 48 4041 Professor Emeritus - Université Paris 2 ASD algocomp Fraigniaud Pierre @ 01 57 27 92 60 4019 Senior Research Scientist - CNRS ASD algocomp , distribue Kerenidis Iordanis @ 01 57 27 92 63 4025 Senior Research Scientist - CNRS ASD algocomp Korman Amos @ 01 57 27 94 06 4028 Senior Research Scientist - CNRS - Currently on sabbatical at FILOFOCS ASD algocomp , distribue Laplante Sophie @ 01 57 27 94 47 4040a Professor ASD algocomp Magniez Frédéric @ 01 57 27 94 02 4024 Senior Research Scientist - CNRS ASD algocomp Mathieu Claire @ 01 57 27 94 39 4009 Senior Research Scientist - CNRS ASD algocomp Orru Michele @ 4027 Research Scientist - CNRS ASD algocomp Rosén Adi @ 01 57 27 94 40 4013 Senior Research Scientist - CNRS ASD algocomp Santha Miklos @ 4041 Senior Research Scientist Emeritus - CNRS ASD algocomp Saulpic David @ 4029a Research Scientist - CNRS ASD algocomp Vladu Adrian @ 01 57 27 92 45 3041 Research Scientist - CNRS ASD algocomp Non-permanent members Name@PhoneOfficePositionPoleTeam Bermot Elie @ 4059 PhD Student ASD algocomp Bhushan Kaartik @ Visitor ASD algocomp Bui Thi-Thuy-Dung @ 3014 PhD Student ASD algocomp Carozza Eliana @ 3014 PhD Student ASD algocomp Das Avinandan @ 4055 PhD Student ASD algocomp , distribue Ducros Clement @ 3028 PhD Student ASD algocomp Edenhofer Roman @ 4060 PhD Student ASD algocomp Egger Christoph @ 3036 Post-Doc ASD algocomp Experton Samuel @ 06 95 12 94 76 Study ingenior ASD algocomp Koch Alexander @ 4058 Post-Doc ASD algocomp Lechine Ulysse @ 3028 PhD Student ASD algocomp Luce Mael @ 3014 PhD Student ASD algocomp , distribue Mathieu-Bloise Benjamin @ PhD Student ASD algocomp Migliaro Francesco @ 4017 Visitor ASD algocomp Natansh Mathur @ 4056 PhD Student ASD algocomp Nematollahi Shamisa @ 4031 PhD Student ASD algocomp Nguyen Mathieu @ Study ingenior ASD algocomp Objois Etienne @ 3033 PhD Student ASD algocomp , graphes Pu Sihang @ 3057 Post-Doc ASD algocomp Riahinia Mahshid @ Visitor ASD algocomp Sellier Francois @ PhD Student ASD algocomp Siproudhis Adrien @ Study ingenior ASD algocomp Szabo Daniel @ 4059 PhD Student ASD algocomp Zhao Junyao @ Post-Doc ASD algocomp van Wijland Ernest @ PhD Student ASD algocomp