IRIF members and visitors are asked to comply with the COVID-19 Directives of CNRS and Université de Paris. image/svg+xml Welcome IRIF, the Research Institute on the Foundations of Computer Science, is a research laboratory of CNRS and Université de Paris, also hosting two Inria project-teams. The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences. IRIF hosts about 200 people. Six of its members have been distinguished by the European Research Council (ERC), five are members of the Institut Universitaire de France IUF), two are members of the Academia Europæa, and one is member of Académie des sciences. More People Contact Follow @IRIF_Paris Notion of the day News 22.5.2020 Jean Krivine (IRIF) discusses how to model an epidemy with Samuel Alizon (MIVEGEC) in a video for Sciences Pop’ Saint-Denis, an association for popular education. 20.5.2020 Amos Korman (IRIF) has been awarded the 2020 Prize for Innovation in Distributed Computing. The prize will be given during the SIROCCO 2020 conference in July. 11.5.2020 IRIF PhD student Simon Mauras had a paper accepted at the EC 2020 conference, “Two-Sided Random Matching Markets: Ex-Ante Equivalence of the Deferred Acceptance Procedures” 11.5.2020 Thomas Colcombet and Hugo Férée (IRIF) together with Antoine Amarilli and Thomas Schwentick administrate the website for the TCS4F Manifesto, an initiative to reduce the carbon footprint related to Theoretical Computer Science research activities. 7.4.2020 The OCaml MOOC developed by Ralf Treinen, Roberto Di Cosmo and Yann Régis-Gianas from IRIF is reopened during COVID19 sheltering. Use this time at home to learn functional programming! 11.5.2020 An online ANR-HOSIGRA 2020 meeting will be held on Tuesday May 12, 14:00-17:00 with a possibility of further discussions on the following days. If interested in joining the meeting, please contact Reza Naserasr. edit all the past news (These news are displayed using a randomized-priority ranking.) Events All events are currently organized remotely. Algorithms and complexity Tuesday June 2, 2020, 11AM, Online Weiqiang Wen (IRISA) Learning With Errors and Extrapolated Dihedral Cosets The hardness of the learning with errors (LWE) problem is one of the most fruitful resources of modern cryptography. In particular, it is one of the most prominent candidates for secure post-quantum cryptography. Understanding its quantum complexity is therefore an important goal. We show that under quantum polynomial time reductions, LWE is equivalent to a relaxed version of the dihedral coset problem (DCP), which we call extrapolated DCP (eDCP). The extent of extrapolation varies with the LWE noise rate. By considering different extents of extrapolation, our result generalizes Regev's famous proof that if DCP is in BQP (quantum poly-time) then so is LWE (FOCS'02). We also discuss a connection between eDCP and Childs and Van Dam's algorithm for generalized hidden shift problems (SODA'07). Our result implies that a BQP solution for LWE might not require the full power of solving DCP, but rather only a solution for its relaxed version, eDCP, which could be easier. Graphs Tuesday June 2, 2020, 3:30PM, Online Julien Baste (Universität Ulm) Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which –automatically– converts a tree decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter. Verification Wednesday June 3, 2020, 2PM, (online, using BigBlueButton) Caterina Urban (INRIA- ENS) Perfectly Parallel Fairness Certification of Neural Networks Recently, there is growing concern that machine-learning models, which currently assist or even automate decision making, reproduce, and in the worst case reinforce, bias of the training data. The development of tools and techniques for certifying fairness of these models or describing their biased behavior is, therefore, critical. In this paper, we propose a perfectly parallel static analysis for certifying causal fairness of feed-forward neural networks used for classification of tabular data. When certification succeeds, our approach provides definite guarantees, otherwise, it describes and quantifies the biased behavior. We design the analysis to be sound, in practice also exact, and configurable in terms of scalability and precision, thereby enabling pay-as-you-go certification. We implement our approach in an open-source tool and demonstrate its effectiveness on models trained with popular datasets. Enumerative and analytic combinatorics Thursday June 4, 2020, 2PM, Salle 1007 Éric Fusy (LIX) To be announced Automata Friday June 5, 2020, 2:30PM, Online K. S. Thejaswini (University of Warwick) The Strahler Number of a Parity Game The Strahler number is a measure of branching complexity of rooted trees. We define the Strahler number of a parity game to be the the smallest Strahler number of the tree of any of its attractor decompositions. In this talk, we will argue that the Strahler number of a parity game is a robust, and hence arguably natural, parameter: it coincides with its alternative version based on trees of progress measures and— remarkably—with the register number defined by Lehtinen (2018). We will also look at how parity games can be solved in quasi-linear space and in time that is polynomial in the number of vertices n and linear in (d/2k)^k , where d is the number of priorities and k is the Strahler number. This complexity is quasi-polynomial because the Strahler number is at most logarithmic in the number of vertices. This significantly improves the running times and space achieved for parity games of bounded register number by Lehtinen (2018) and by Parys (2020).