Author: "Institute of Science and Technology [Austria] (IST Austria)" / Topic: computer science - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Institute of Science and Technology [Austria] (IST Austria)"' showing total 36 results

Start Over Author "Institute of Science and Technology [Austria] (IST Austria)" Topic computer science

36 results on '"Institute of Science and Technology [Austria] (IST Austria)"'

1. Shellability is NP-Complete

Author: Zuzana Patáková, Pavel Paták, Uli Wagner, Xavier Goaoc, Martin Tancer, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Department of Mathematics and Statistics [Brno], Faculty of Science [Brno] (SCI / MUNI), Masaryk University [Brno] (MUNI)-Masaryk University [Brno] (MUNI), Institute of Science and Technology [Austria] (IST Austria), Department of Applied Mathematics [Prague] (KAM), Charles University [Prague] (CU), Bettina Speckmann and Csaba D. Tóth, Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Austria] - IST Austria (IST Austria), Geometric Algorithms and Models Beyond the Linear and Euclidean realm (GAMBLE ), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, Reduction (recursion theory), 0102 computer and information sciences, Collapsibility, 02 engineering and technology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Contractible space, 01 natural sciences, Combinatorics, Simplicial complex, Mathematics - Geometric Topology, Corollary, Artificial Intelligence, Simple (abstract algebra), FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, [INFO]Computer Science [cs], [MATH]Mathematics [math], 0101 mathematics, Mathematics, 000 Computer science, knowledge, general works, Simplicial complexes, 010102 general mathematics, Geometric Topology (math.GT), 020207 software engineering, NP-completeness, 010201 computation theory & mathematics, Hardware and Architecture, Control and Systems Engineering, Computer Science, Computer Science - Computational Geometry, 020201 artificial intelligence & image processing, Combinatorics (math.CO), NP-complete, Partially ordered set, Software, Information Systems, Shellability
Abstract: We prove that for every $d\geq 2$, deciding if a pure, $d$-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every $d \ge 2$ and $k \ge 0$, deciding if a pure, $d$-dimensional, simplicial complex is $k$-decomposable is NP-hard. For $d \ge 3$, both problems remain NP-hard when restricted to contractible pure $d$-dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable., Version 2: 17 pages, 11 figures. Improved readability at various places. Proof in Section 6 simplified
Published: 2018
Full Text: View/download PDF

2. Bounding Helly Numbers via Betti Numbers

Author: Xavier Goaoc, Uli Wagner, Pavel Paták, Zuzana Patáková, Martin Tancer, Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Einstein Institute of Mathematics, The Hebrew University of Jerusalem (HUJ), Department of Applied Mathematics [Prague] (KAM), Charles University [Prague] (CU), Institute of Science and Technology [Austria] - IST Austria (IST Austria), Martin Loebl, Jaroslav Nešetřil, Robin Thomas, Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Institute of Science and Technology [Austria] (IST Austria), Department of Algebra (MFF-UK), and Lars Arge and János Pach
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Betti number, 0102 computer and information sciences, Computer Science::Computational Geometry, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Primary 52A35, secondary 05E45, 55S91, 05D10, 57Q35, Combinatorics, 510 Mathematics, Integer, Bounding overwatch, Embedding of simplicial complexes, FOS: Mathematics, Algebraic Topology (math.AT), Mathematics - Combinatorics, Beta (velocity), Betti numbers, Family of sets, Mathematics - Algebraic Topology, 0101 mathematics, Physics, 000 Computer science, knowledge, general works, Ramsey’s theorem, 010102 general mathematics, Homological almost-embedding, 010201 computation theory & mathematics, Computer Science, Computer Science - Computational Geometry, Combinatorics (math.CO), Helly-type theorem, Singular homology, Computer Science - Discrete Mathematics
Abstract: We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers $b$ and $d$ there exists an integer $h(b,d)$ such that the following holds. If $\mathcal F$ is a finite family of subsets of $\mathbb R^d$ such that $\tilde\beta_i\left(\bigcap\mathcal G\right) \le b$ for any $\mathcal G \subsetneq \mathcal F$ and every $0 \le i \le \lceil d/2 \rceil-1$ then $\mathcal F$ has Helly number at most $h(b,d)$. Here $\tilde\beta_i$ denotes the reduced $\mathbb Z_2$-Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these $\lceil d/2 \rceil$ first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex $K$, some well-behaved chain map $C_*(K) \to C_*(\mathbb R^d)$., Comment: 29 pages, 8 figures
Published: 2017

3. On Generalized Heawood inequalities for manifolds: a Van Kampen–Flores-type nonembeddability result

Author: Goaoc, Xavier, Mabillard, Isaac, Paták, Pavel, Patáková, Zuzana, Tancer, Martin, Wagner, Uli, Arge, Lars, Pach, János, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Institute of Science and Technology [Austria] (IST Austria), Einstein Institute of Mathematics, The Hebrew University of Jerusalem (HUJ), Department of Applied Mathematics [Prague] (KAM), Charles University [Prague] (CU), Charles University Grant SVV-2014-260103, CE-ITI (GACR P202/12/G061) of the Czech Science Foundation, Swiss National Science Foundation (grants SNSF-200020-138230 and SNSF-PP00P2-138948), European Project: 267165,EC:FP7:ERC,ERC-2010-AdG_20100224,DISCONV(2011), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Department of Algebra (MFF-UK), Lars Arge, János Pach, and Institute of Science and Technology [Austria] - IST Austria (IST Austria)
Subjects: General Mathematics, 0102 computer and information sciences, Type (model theory), [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Combinatorics, Van Kampen–Flores, 510 Mathematics, 05E45 (Primary), 57N35 (Secondary), FOS: Mathematics, Mathematics - Combinatorics, 0101 mathematics, Manifolds, Prime power, Klein bottle, Mathematics, Heawood graph, Conjecture, Simplex, 000 Computer science, knowledge, general works, 010102 general mathematics, Complete graph, Surface (topology), Embeddings, 010201 computation theory & mathematics, Computer Science, Heawood Inequality, Combinatorics (math.CO)
Abstract: The fact that the complete graph $K_5$ does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph $K_n$ embeds in a closed surface $M$ (other than the Klein bottle) if and only if $(n-3)(n-4)\leq 6b_1(M)$, where $b_1(M)$ is the first $\mathbb Z_2$-Betti number of $M$. On the other hand, van Kampen and Flores proved that the $k$-skeleton of the $n$-dimensional simplex (the higher-dimensional analogue of $K_{n+1}$) embeds in $\mathbb R^{2k}$ if and only if~$n \le 2k+1$. Two decades ago, K\"uhnel conjectured that the $k$-skeleton of the $n$-simplex embeds in a compact, $(k-1)$-connected $2k$-manifold with $k$th $\mathbb Z_2$-Betti number $b_k$ only if the following generalized Heawood inequality holds: $\binom{n-k-1}{k+1} \le \binom{2k+1}{k+1}b_k$. This is a common generalization of the case of graphs on surfaces as well as the van Kampen--Flores theorem (the special cases $k=1$ and $b_k=0$, respectively), and also closely related to the theory of face numbers of triangulated manifolds. In the spirit of K\"uhnel's conjecture, we prove that if the $k$-skeleton of the $n$-simplex embeds in a $2k$-manifold with $k$th $\mathbb Z_2$-Betti number $b_k$, then $n \le 2b_k\binom{2k+2}{k} + 2k + 4$. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that $M$ is $(k-1)$-connected. Our results generalize to maps without $q$-covered points, in the spirit of Tverberg's theorem, for $q$ a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.
Published: 2015

4. Metamachines of Pluripotent Colloids

Author: Antoine Aubret, Jeremie Palacci, Quentin Martinet, Laboratoire Ondes et Matière d'Aquitaine (LOMA), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS), University of California [San Diego] (UC San Diego), University of California, and Institute of Science and Technology [Austria] (IST Austria)
Subjects: Computer science, Science, Distributed computing, FOS: Physical sciences, General Physics and Astronomy, 02 engineering and technology, Condensed Matter - Soft Condensed Matter, Article, General Biochemistry, Genetics and Molecular Biology, 03 medical and health sciences, Affordable and Clean Energy, Colloids, [PHYS.COND.CM-SM]Physics [physics]/Condensed Matter [cond-mat]/Statistical Mechanics [cond-mat.stat-mech], Microscale chemistry, ComputingMilieux_MISCELLANEOUS, 030304 developmental biology, 0303 health sciences, Focus (computing), [PHYS.PHYS.PHYS-OPTICS]Physics [physics]/Physics [physics]/Optics [physics.optics], Multidisciplinary, business.industry, Active particles, Control reconfiguration, Self-assembly, General Chemistry, Energy consumption, Modular design, Stem Cell Research, 021001 nanoscience & nanotechnology, Active matter, body regions, Applied physics, Template, [PHYS.COND.CM-GEN]Physics [physics]/Condensed Matter [cond-mat]/Other [cond-mat.other], [PHYS.COND.CM-MS]Physics [physics]/Condensed Matter [cond-mat]/Materials Science [cond-mat.mtrl-sci], Soft Condensed Matter (cond-mat.soft), Generic health relevance, 0210 nano-technology, business, [PHYS.COND.CM-SCM]Physics [physics]/Condensed Matter [cond-mat]/Soft Condensed Matter [cond-mat.soft]
Abstract: Machines enabled the Industrial Revolution and are central to modern technological progress: A machine’s parts transmit forces, motion, and energy to one another in a predetermined manner. Today’s engineering frontier, building artificial micromachines that emulate the biological machinery of living organisms, requires faithful assembly and energy consumption at the microscale. Here, we demonstrate the programmable assembly of active particles into autonomous metamachines using optical templates. Metamachines, or machines made of machines, are stable, mobile and autonomous architectures, whose dynamics stems from the geometry. We use the interplay between anisotropic force generation of the active colloids with the control of their orientation by local geometry. This allows autonomous reprogramming of active particles of the metamachines to achieve multiple functions. It permits the modular assembly of metamachines by fusion, reconfiguration of metamachines and, we anticipate, a shift in focus of self-assembly towards active matter and reprogrammable materials., Mobile micromachines have the potential to probe and manipulate matter at small scales emulating the biological machinery of living organisms. Here, the authors take advantage of the anisotropy of self-propelled colloidal heterodimers to control anisotropic and reprogrammable interactions between particles.
Published: 2021

5. Roadmap on multiscale coupling of biochemical and mechanical signals during development

Author: Ed Munro, Kasumi Kishi, Sham Tlili, Jean-Léon Maître, Stefano Di Talia, Yonit Maroudas-Sacks, Aryeh Warmflash, Paolo Caldarelli, Anna Kicheva, Zev J. Gartner, Timothy E. Saunders, Idse Heemskerk, Antoine Fruleux, Alan R. Rodrigues, Benjamin Stormo Stormo, Bassma Khamaisi, Amy Gladfelter Gladfelter, Edouard Hannezo, Jerome Gros, Pierre-François Lenne, David Sprinzak, Arezki Boudaoud, Laura Bocanegra-Moreno, Yuchen Long, Arthur Michaut, Amy E. Shyer, Kinneret Keren, Nicolas Minc, Institut de Biologie du Développement de Marseille (IBDM), Aix Marseille Université (AMU)-Collège de France (CdF (institution))-Centre National de la Recherche Scientifique (CNRS), University of Chicago, University of Michigan Medical School [Ann Arbor], University of Michigan [Ann Arbor], University of Michigan System-University of Michigan System, Rice University [Houston], Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Reproduction et développement des plantes (RDP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Laboratoire d'hydrodynamique (LadHyX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), National University of Singapore (NUS), Cellule Pasteur UPMC, Institut Pasteur [Paris] (IP)-Sorbonne Université (SU), Régulation Dynamique de la Morphogénèse - Dynamic Regulation of Morphogenesis, Institut Pasteur [Paris] (IP)-Centre National de la Recherche Scientifique (CNRS), Technion - Israel Institute of Technology [Haifa], University of California [San Francisco] (UC San Francisco), University of California (UC), University of North Carolina [Chapel Hill] (UNC), University of North Carolina System (UNC), Rockefeller University [New York], Institut Jacques Monod (IJM (UMR_7592)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Génétique et Biologie du Développement, Institut Curie [Paris]-Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Duke University Medical Center, Tel Aviv University (TAU), The AK group is supported by IST Austria and by the ERC under European Union Horizon 2020 research and innovation programme Grant 680037. Apologies to those whose work could not be mentioned due to limited space. We thank all my lab members, both past and present, for stimulating discussion. This work was funded by a Singapore Ministry of Education Tier 3 Grant, MOE2016-T3-1-005. We thank Francis Corson for continuous discussion and collaboration contributing to these views and for figure 4(A). PC is sponsored by the Institut Pasteur and the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Grant Agreement No. 665807. Research in JG's laboratory is funded by the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC Grant Agreement No. 337635, Institut Pasteur, CNRS, Cercle FSER, Fondation pour la Recherche Medicale, the Vallee Foundation and the ANR-19-CE-13-0024 Grant. We thank Erez Braun and Alex Mogilner for comments on the manuscript and Niv Ierushalmi for help with figure 5. This project has received funding from the European Union's Horizon 2020 research and innovation programme under Grant Agreement No. ERC-2018-COG Grant 819174-HydraMechanics awarded to KK. EH thanks all lab members, as well as Pierre Recho, Tsuyoshi Hirashima, Diana Pinheiro and Carl-Philip Heisenberg, for fruitful discussions on these topics—and apologize for not being able to cite many very relevant publications due to the strict 10-reference limit. EH acknowledges the support of Austrian Science Fund (FWF) (P 31639) and the European Research Council under the European Union's Horizon 2020 Research and Innovation Programme Grant Agreements (851288). The authors acknowledge the inspiring scientists whose work could not be cited in this perspective due to space constraints, the members of the Gartner Lab for helpful discussions, the Barbara and Gerson Bakar Foundation, the Chan Zuckerberg Biohub Investigators Programme, the National Institute of Health, and the Centre for Cellular Construction, an NSF Science and Technology Centre. The Minc laboratory is currently funded by the CNRS and the European Research Council (CoG Forcaster No. 647073). Research in the lab of J-LM is supported by the Institut Curie, the Centre National de la Recherche Scientifique (CNRS), the Institut National de la Santé Et de la Recherche Médicale (INSERM), and is funded by grants from the ATIP-Avenir programme, the Fondation Schlumberger pour l'Éducation et la Recherche via the Fondation pour la Recherche Médicale, the European Research Council Starting Grant ERC-2017-StG 757557, the European Molecular Biology Organization Young Investigator programme (EMBO YIP), the INSERM transversal programme Human Development Cell Atlas (HuDeCA), Paris Sciences Lettres (PSL) 'nouvelle équipe' and QLife (17-CONV-0005) grants and Labex DEEP (ANR-11-LABX-0044) which are part of the IDEX PSL (ANR-10-IDEX-0001-02). We acknowledge useful discussions with Massimo Vergassola, Sebastian Streichan and my lab members. Work in my laboratory on Drosophila embryogenesis is partly supported by NIH-R01GM122936. The authors acknowledge the support by a grant from the European Research Council (Grant No. 682161). Lenne group is funded by a grant from the 'Investissements d'Avenir' French Government programme managed by the French National Research Agency (ANR-16-CONV-0001) and by the Excellence Initiative of Aix-Marseille University—A*MIDEX, and ANR projects MechaResp (ANR-17-CE13-0032) and AdGastrulo (ANR-19-CE13-0022)., ANR-19-CE13-0024,Embryonics,Rôle de la mécanique dans l'auto-organisation et la plasticité embryonnaire(2019), ANR-11-LABX-0044,DEEP,Développement, Epigénèse, Epigénétique et potentiel de vie(2011), ANR-10-IDEX-0001,PSL,Paris Sciences et Lettres(2010), ANR-16-CONV-0001,CENTURI,CenTuri : Centre Turing des Systèmes vivants(2016), ANR-17-CE13-0032,MechaResp,Réponses cellulaires et tissulaires aux forces mécaniques au cours de la morphogenèse(2017), ANR-19-CE13-0022,AdGastrulo,Intégration de signaux biochimiques et mécaniques aux contacts adhésifs cellulaires pendant la morphogenèse mammifère : une approche quantitative utilisant un système auto-organisé minimal(2019), European Project: 680037,H2020,ERC-2015-STG,GROWTHPATTERN(2016), European Project: 665807,H2020,H2020-MSCA-COFUND-2014,PASTEURDOC(2015), European Project: 337635,EC:FP7:ERC,ERC-2013-StG,LIMBCELLDYNAMICS(2014), European Project: 647073,H2020,ERC-2014-CoG,FORCASTER(2015), European Project: 757557,ERC-2017-STG ,MECHABLASTO(2018), European Project: 851288,ERC-2019-STG,DEMOS(2020), European Project: 682161,ERC-2015-CoG ,MorphoNotch(2016), Institute of Science and Technology [Austria] (IST Austria), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Institut Pasteur [Paris]-Sorbonne Université (SU), Institut Pasteur [Paris]-Centre National de la Recherche Scientifique (CNRS), University of California [San Francisco] (UCSF), University of California, Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Tel Aviv University [Tel Aviv], and Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Cognitive science, Force generation, 0303 health sciences, Computer science, [SDV]Life Sciences [q-bio], Biophysics, morphogenesis, Cell Biology, Models, Biological, Article, Biomechanical Phenomena, Dynamic coupling, 03 medical and health sciences, Coupling (physics), 0302 clinical medicine, Development (topology), Multiscale coupling, Structural Biology, embryogenesis, signalling, Molecular Biology, Biological sciences, 030217 neurology & neurosurgery, Signal Transduction, 030304 developmental biology
Abstract: The way in which interactions between mechanics and biochemistry lead to the emergence of complex cell and tissue organization is an old question that has recently attracted renewed interest from biologists, physicists, mathematicians and computer scientists. Rapid advances in optical physics, microscopy and computational image analysis have greatly enhanced our ability to observe and quantify spatiotemporal patterns of signalling, force generation, deformation, and flow in living cells and tissues. Powerful new tools for genetic, biophysical and optogenetic manipulation are allowing us to perturb the underlying machinery that generates these patterns in increasingly sophisticated ways. Rapid advances in theory and computing have made it possible to construct predictive models that describe how cell and tissue organization and dynamics emerge from the local coupling of biochemistry and mechanics. Together, these advances have opened up a wealth of new opportunities to explore how mechanochemical patterning shapes organismal development. In this roadmap, we present a series of forward-looking case studies on mechanochemical patterning in development, written by scientists working at the interface between the physical and biological sciences, and covering a wide range of spatial and temporal scales, organisms, and modes of development. Together, these contributions highlight the many ways in which the dynamic coupling of mechanics and biochemistry shapes biological dynamics: from mechanoenzymes that sense force to tune their activity and motor output, to collectives of cells in tissues that flow and redistribute biochemical signals during development.
Published: 2021

6. Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity

Author: Mirza Ahad Baig, Alessia Milani, Corentin Travers, Danny Hendler, Institute of Science and Technology [Austria] (IST Austria), Ben-Gurion University of the Negev (BGU), Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: amortized step complexity, 020203 distributed computing, Theoretical computer science, Computer science, max array, 0102 computer and information sciences, 02 engineering and technology, Object (computer science), Snapshot algorithm, 01 natural sciences, atomic snapshot, Shared memory, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Key (cryptography), [INFO]Computer Science [cs], CCS Concepts: • Theory of computation → Concurrent algorithms Additional Key Words and Phrases: shared memory, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: We present the first deterministic wait-free long-lived snapshot algorithm, using only read and write operations, that guarantees polylogarithmic amortized step complexity in all executions. This is the first non-blocking snapshot algorithm, using reads and writes only, that has sub-linear amortized step complexity in executions of arbitrary length. The key to our construction is a novel implementation of a 2-component max array object which may be of independent interest.
Published: 2020

7. ARCH-COMP20 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics

Author: Pieter Collins, Fabian Immler, Niklas Kochdumper, Christian Schilling, Luis Benet, Alexandre Chapoutot, Julien Alexandre Dit Sandretto, David P. Sanders, Xin Chen, Daniel Freire, Matthias Althoff, Luca Geretti, Marcelo Forets, Department of Computer Science [Verona] (UNIVR | DI), University of Verona (UNIVR), Unité d'Informatique et d'Ingénierie des Systèmes (U2IS), École Nationale Supérieure de Techniques Avancées (ENSTA Paris), Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), Instituto de Matematicas (UNAM), Universidad Nacional Autónoma de México (UNAM), University of Dayton, Department of data science and Knowledge Engineering [Maastricht], Maastricht University [Maastricht], Universidad de la República (UDELAR), Computer Science Department - Carnegie Mellon University, University of Pittsburgh (PITT), Pennsylvania Commonwealth System of Higher Education (PCSHE)-Pennsylvania Commonwealth System of Higher Education (PCSHE), Department of Mathematics, Massachusetts Institute of Technology, Cambridge MA 02139, United States, and Institute of Science and Technology [Austria] (IST Austria)
Subjects: Nonlinear system, justITSELF, Hybrid systems, Continuous systems, Computer science, Hybrid system, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Nonlinear systems, Applied mathematics, Arch, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, ComputingMilieux_MISCELLANEOUS, ddc
Abstract: We present the results of a friendly competition for formal verification of continuous and hybrid systems with nonlinear continuous dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2020. This year, 6 tools Ariadne, CORA, DynIbex, Flow*, Isabelle/HOL, and JuliaReach (in alphabetic order) participated. These tools are applied to solve reachability analysis problems on six benchmark problems, two of them featuring hybrid dynamics. We do not rank the tools based on the results, but show the current status and discover the potential advantages of different tools.
Published: 2020

8. DILS: Demographic Inferences with Linked Selection by using ABC

Author: Alexis Simon, Nicolas Bierne, Nicolas Galtier, Camille Roux, Christelle Fraïsse, Stéphane Delmotte, Xavier Vekemans, Jonathan Romiguier, Etienne Loire, Iva Popovic, Laurent Duret, Clément Mazoyer, Bruno Spataro, Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Évolution, Écologie et Paléontologie (Evo-Eco-Paleo) - UMR 8198 (Evo-Eco-Paléo (EEP)), Université de Lille-Centre National de la Recherche Scientifique (CNRS), School of Biological Sciences [Brisbane], University of Queensland [Brisbane], Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Institut des Sciences de l'Evolution de Montpellier (UMR ISEM), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-École Pratique des Hautes Études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Montpellier (UM)-Institut de recherche pour le développement [IRD] : UR226-Centre National de la Recherche Scientifique (CNRS), Animal, Santé, Territoires, Risques et Ecosystèmes (UMR ASTRE), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Département Systèmes Biologiques (Cirad-BIOS), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad), We would like to acknowledge the support of the I‐Site ULNE Foundation for this work., Institute of Science and Technology [Austria] (IST Austria), Évolution, Écologie et Paléontologie (Evo-Eco-Paleo) - UMR 8198 (Evo-Eco-Paléo), Centre National de la Recherche Scientifique (CNRS)-Université de Lille, École pratique des hautes études (EPHE), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Montpellier (UM)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre National de la Recherche Scientifique (CNRS)-Institut de recherche pour le développement [IRD] : UR226
Subjects: Gene Flow, 0301 basic medicine, 0106 biological sciences, Genetic Speciation, Computer science, [SDV]Life Sciences [q-bio], media_common.quotation_subject, Population, Locus (genetics), Genomics, Computational biology, Biology, 010603 evolutionary biology, 01 natural sciences, Genome, Gene flow, 03 medical and health sciences, [SDV.BBM.GTP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Genomics [q-bio.GN], Genetic algorithm, Genetics, Selection, Genetic, education, Divergence (statistics), Ecology, Evolution, Behavior and Systematics, Selection (genetic algorithm), 030304 developmental biology, media_common, Population Density, 0303 health sciences, education.field_of_study, [SHS.STAT]Humanities and Social Sciences/Methods and statistics, Models, Genetic, Population size, Bayes Theorem, Speciation, Genetics, Population, 030104 developmental biology, Approximate Bayesian computation, Biotechnology
Abstract: We present DILS, a deployable statistical analysis platform for conducting demographic inferences with linked selection from population genomic data using an Approximate Bayesian Computation framework. DILS takes as input single-population or two-population datasets (multilocus fasta sequences) and performs three types of analyses in a hierarchical manner, identifying: 1) the best demographic model to study the importance of gene flow and population size change on the genetic patterns of polymorphism and divergence, 2) the best genomic model to determine whether the effective sizeNeand migration rateN.mare heterogeneously distributed along the genome (implying linked selection) and 3) loci in genomic regions most associated with barriers to gene flow. Also availableviaa web interface, an objective of DILS is to facilitate collaborative research in speciation genomics. Here, we show the performance and limitations of DILS by using simulations, and finally apply the method to published data on a divergence continuum composed by 28 pairs ofMytilusmussel populations/species.
Published: 2020

9. Adaptively Secure Proxy Re-encryption

Author: Georg Fuchsbauer, Krzysztof Pietrzak, Karen Klein, Chethan Kamath, Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Institute of Science and Technology [Austria] (IST Austria), The first author is supported by the French ANR EfTrEC project (ANR-16-CE39-0002). The remaining authors are supported by the European Research Council, ERC consolidator grant TOCNeT (682815)., Dongdai Lin, Kazue Sako, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), ANR-16-CE39-0002,EfTrEC,Monnaie électronique transférable efficace(2016), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris
Subjects: Proxy reencryption, 050101 languages & linguistics, business.industry, Computer science, 05 social sciences, 02 engineering and technology, Adversary, Computer security, computer.software_genre, Encryption, Proxy re-encryption, Public-key cryptography, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Ciphertext, Adaptive security, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, business, Proxy (statistics), computer
Abstract: International audience; A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key pk′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under pk′ without having to know the underlying message, while transformations from pk′to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.All existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in Open image in new window , rendering the result meaningless already for moderate Open image in new window .Jafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.Our results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).
Published: 2019
Full Text: View/download PDF

10. ARCH-COMP19 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics

Author: David P. Sanders, Xin Chen, Christian Schilling, Niklas Kochdumper, Luis Benet, Luca Geretti, Alexandre Chapoutot, Matthias Althoff, Marcelo Forets, Fabian Immler, Computer Science Department - Carnegie Mellon University, University of Pittsburgh (PITT), Pennsylvania Commonwealth System of Higher Education (PCSHE)-Pennsylvania Commonwealth System of Higher Education (PCSHE), Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), Universidad Nacional Autónoma de México (UNAM), Unité d'Informatique et d'Ingénierie des Systèmes (U2IS), École Nationale Supérieure de Techniques Avancées (ENSTA Paris), University of Dayton, University of the Republic of Uruguay, University of Verona (UNIVR), and Institute of Science and Technology [Austria] (IST Austria)
Subjects: Reachability Analysis, Temporal Logic, Hybrid Automata, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, ddc, Nonlinear system, Reachability Analysis, Temporal Logic, Control theory, Hybrid system, Temporal logic, Hybrid Automata, Arch, ComputingMilieux_MISCELLANEOUS
Abstract: We present the results of a friendly competition for formal verification of continuous and hybrid systems with nonlinear continuous dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In this year, 6 tools Ariadne, CORA, DynIbex, Flow*, Isabelle/HOL, and JuliaReach (in alphabetic order) participated. They are applied to solve reachability analysis problems on four benchmark problems, one of them with hybrid dynamics. We do not rank the tools based on the results, but show the current status and discover the potential advantages of different tools.
Published: 2018

11. Separating intrinsic interactions from extrinsic correlations in a network of sensory neurons

Author: Ulisse Ferrari, Stéphane Deny, Matthew Chalk, Gašper Tkačik, Thierry Mora, Olivier Marre, Institut de la Vision, Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Institut National de la Santé et de la Recherche Médicale (INSERM), Stanford University, Institute of Science and Technology [Austria] (IST Austria), Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS), and Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)
Subjects: Computer science, FOS: Physical sciences, Sensory system, Stimulus (physiology), ENCODE, Retinal ganglion, 01 natural sciences, Sensory neuroscience, 03 medical and health sciences, Neural activity, 0302 clinical medicine, Encoding (memory), Ising model, Neuronal networks, 0103 physical sciences, Biological neural network, medicine, 010306 general physics, 030304 developmental biology, [PHYS]Physics [physics], 0303 health sciences, Retina, Quantitative Biology::Neurons and Cognition, Artificial neural network, Disordered Systems and Neural Networks (cond-mat.dis-nn), Limiting, Condensed Matter - Disordered Systems and Neural Networks, Neural encoding, medicine.anatomical_structure, Retinal ganglion cell, FOS: Biological sciences, Quantitative Biology - Neurons and Cognition, Neurons and Cognition (q-bio.NC), Neuroscience, 030217 neurology & neurosurgery
Abstract: International audience; Correlations in sensory neural networks have both extrinsic and intrinsic origins. Extrinsic or stimulus correlations arise from shared inputs to the network and, thus, depend strongly on the stimulus ensemble. Intrinsic or noise correlations reflect biophysical mechanisms of interactions between neurons, which are expected to be robust to changes in the stimulus ensemble. Despite the importance of this distinction for understanding how sensory networks encode information collectively, no method exists to reliably separate intrinsic interactions from extrinsic correlations in neural activity data, limiting our ability to build predictive models of the network response. In this paper we introduce a general strategy to infer population models of interacting neurons that collectively encode stimulus information. The key to disentangling intrinsic from extrinsic correlations is to infer the couplings between neurons separately from the encoding model and to combine the two using corrections calculated in a mean-field approximation. We demonstrate the effectiveness of this approach in retinal recordings. The same coupling network is inferred from responses to radically different stimulus ensembles, showing that these couplings indeed reflect stimulus-independent interactions between neurons. The inferred model predicts accurately the collective response of retinal ganglion cell populations as a function of the stimulus.
Published: 2018

12. Online Timed Pattern Matching using Automata

Author: Thomas Ferrère, Alexey Bakhirkin, Oded Maler, Eugene Asarin, Dejan Nickovic, VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Institute of Science and Technology [Austria] (IST Austria), Austrian Institute of Technology [Vienna] (AIT), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)
Subjects: Theoretical computer science, Computer science, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Timed automaton, 020207 software engineering, 02 engineering and technology, Specification language, Rotation formalisms in three dimensions, Automaton, Reachability, Asynchronous communication, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Regular expression, Pattern matching, Computer Science::Formal Languages and Automata Theory
Abstract: International audience; We provide a procedure for detecting the sub-segments of an incrementally observed Boolean signal w that match a given temporal pattern phi. As a pattern specification language, we use timed regular expressions, a formalism well-suited for expressing properties of concurrent asynchronous behaviors embedded in metric time. We construct a timed automaton accepting the timed language denoted by phi and modify it slightly for the purpose of matching. We then apply zone-based reachability computation to this automaton while it reads w, and retrieve all the matching segments from the results. Since the procedure is automaton based, it can be applied to patterns specified by other formalisms such as timed temporal logics reducible to timed automata or directly encoded as timed automata. The procedure has been implemented and its performance on synthetic examples is demonstrated.
Published: 2018

13. Brief Announcement: Performance Prediction for Coarse-Grained Locking

Author: Dan Alistarh, Petr Kuznetsov, Vitaly Aksenov, ITMO University [Russia], Langages de programmation, types, compilation et preuves (GALLIUM), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Télécom ParisTech, ANR-05-PADD-0014,ACDUQ,Action collective pour une maîtrise durable de la santé animale : qualification sanitaire en élevage de ruminants(2005), European Project: 308246,EC:FP7:ERC,ERC-2012-StG_20111012,DEEPSEA(2013), and Institute of Science and Technology [Austria] (IST Austria)
Subjects: 010302 applied physics, Record locking, Computer science, Concurrent data structure, Stochastic process, Design pattern, 020206 networking & telecommunications, 02 engineering and technology, Parallel computing, 01 natural sciences, Hash table, 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, Performance prediction, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Queue, Throughput (business)
Abstract: International audience; A standard design pattern found in many concurrent data structures , such as hash tables or ordered containers, is an alternation of parallelizable sections that incur no data conflicts and critical sections that must run sequentially and are protected with locks. A lock can be viewed as a queue that arbitrates the order in which the critical sections are executed, and a natural question is whether we can use stochastic analysis to predict the resulting throughput. As a preliminary evidence to the affirmative, we describe a simple model that can be used to predict the throughput of coarse-grained lock-based algorithms. We show that our model works well for CLH lock, and we expect it to work for other popular lock designs such as TTAS, MCS, etc.
Published: 2018

14. Efficient Parametric Identification for STL

Author: Oded Maler, Thomas Ferrère, Alexey Bakhirkin, VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), and Institute of Science and Technology [Austria] (IST Austria)
Subjects: 0209 industrial biotechnology, Computer science, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Parameterized complexity, 02 engineering and technology, Parameter space, Parametric Identification, 020901 industrial engineering & automation, Signal temporal logic, Robustness (computer science), Signal Temporal Logic, Quantifier elimination, 0202 electrical engineering, electronic engineering, information engineering, Parametric temporal Logic, 020201 artificial intelligence & image processing, Temporal logic, Parametric identification, Algorithm
Abstract: International audience; We describe a new algorithm for the parametric identification problem for signal temporal logic (STL), stated as follows. Given a dense-time real-valued signal w and a parameterized temporal logic formula phi, compute the subset of the parameter space that renders the formula satisfied by the signal. Unlike previous solutions, which were based on search in the parameter space or quantifier elimination, our procedure works recursively on phi and computes the evolution over time of the set of valid parameter assignments. This procedure is similar to that of monitoring or computing the robustness of phi relative to w. Our implementation and experiments demonstrate that this approach can work well in practice.
Published: 2018

15. The divergence history of European blue mussel species reconstructed from Approximate Bayesian Computation: the effects of sequencing techniques and sampling strategies

Author: Christelle Fraïsse, John J. Welch, Jonathan Romiguier, Nicolas Bierne, Camille Roux, Pierre-Alexandre Gagnaire, Nicolas Faivre, Institut des Sciences de l'Evolution de Montpellier (UMR ISEM), École pratique des hautes études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Montpellier (UM)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre National de la Recherche Scientifique (CNRS)-Institut de recherche pour le développement [IRD] : UR226, Department of Genetics University of Cambridge, University of Cambridge [UK] (CAM), Institute of Science and Technology [Austria] (IST Austria), Évolution, Écologie et Paléontologie (Evo-Eco-Paleo) - UMR 8198 (Evo-Eco-Paléo), Université de Lille-Centre National de la Recherche Scientifique (CNRS), Department of Genetics [Cambridge], Fraïsse, Christelle [0000-0001-8441-5075], Bierne, Nicolas [0000-0003-1856-3197], Apollo - University of Cambridge Repository, Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-École Pratique des Hautes Études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Montpellier (UM)-Institut de recherche pour le développement [IRD] : UR226-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Évolution, Écologie et Paléontologie (Evo-Eco-Paleo) - UMR 8198 (Evo-Eco-Paléo (EEP)), and ANR-17-CE02-0006,CoGeDiv,Génomique Comparative de la Divergence pour relier la spéciation aux traits d'histoire de vie(2017)
Subjects: 0106 biological sciences, 0301 basic medicine, Computer science, Mytilus edulis, lcsh:Medicine, Inference, 010603 evolutionary biology, 01 natural sciences, General Biochemistry, Genetics and Molecular Biology, Coalescent theory, 03 medical and health sciences, Genetics, Divergence (statistics), [SDV.GEN.GPO]Life Sciences [q-bio]/Genetics/Populations and Evolution [q-bio.PE], General Neuroscience, Model selection, lcsh:R, Computational Biology, Sampling (statistics), Contrast (statistics), Demographic inferences, General Medicine, Evolutionary Studies, 030104 developmental biology, Biogeography, Evolutionary biology, Approximate Bayesian Computation, Next-generation sequencing, Approximate Bayesian computation, General Agricultural and Biological Sciences, Synonymous substitution, Joint site frequency spectrum
Abstract: Genome-scale diversity data are increasingly available in a variety of biological systems, and can be used to reconstruct the past evolutionary history of species divergence. However, extracting the full demographic information from these data is not trivial, and requires inferential methods that account for the diversity of coalescent histories throughout the genome. Here, we evaluate the potential and limitations of one such approach. We reexamine a well-known system of mussel sister species, using the joint site frequency spectrum (jSFS) of synonymous mutations computed either from exome capture or RNA-seq, in an Approximate Bayesian Computation (ABC) framework. We first assess the best sampling strategy (number of: individuals, loci, and bins in the jSFS), and show that model selection is robust to variation in the number of individuals and loci. In contrast, different binning choices when summarizing the joint site frequency spectrum, strongly affect the results: including classes of low and high frequency shared polymorphisms can more effectively reveal recent migration events. We then take advantage of the flexibility of ABC to compare more realistic models of speciation, including variation in migration rates through time (i.e. periodic connectivity) and across genes (i.e. genome-wide heterogeneity in migration rates). We show that these models were consistently selected as the most probable, suggesting that mussels have experienced a complex history of gene flow during divergence and that the species boundary is semi-permeable. Our work provides a comprehensive evaluation of ABC demographic inference in mussels based on the coding site frequency spectrum, and supplies guidelines for employing different sequencing techniques and sampling strategies. We emphasize, perhaps surprisingly, that inferences are less limited by the volume of data, than by the way in which they are analyzed.
Published: 2018

16. Multiplexed computations in retinal ganglion cells of a single type

Author: Ulisse Ferrari, Romain Caplette, Olivier Marre, Stéphane Deny, Pierre Yger, Emilie Mace, Gašper Tkačik, Serge Picaud, Institut de la Vision, Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Institute of Science and Technology [Austria] (IST Austria), and HAL-UPMC, Gestionnaire
Subjects: 0301 basic medicine, Male, Retinal Ganglion Cells, genetic structures, Computer science, Motion Perception, General Physics and Astronomy, Multiplexing, 0302 clinical medicine, 571 Physiology, Computer vision, lcsh:Science, 0303 health sciences, education.field_of_study, Multidisciplinary, [SDV.MHEP] Life Sciences [q-bio]/Human health and pathology, Ganglion, Visual field, medicine.anatomical_structure, Feature (computer vision), Female, Computation, Science, Population, Sensory system, Stimulus (physiology), Retinal ganglion, General Biochemistry, Genetics and Molecular Biology, Article, Retina, 03 medical and health sciences, medicine, Animals, Computer Simulation, Motion perception, education, 030304 developmental biology, business.industry, General Chemistry, Models, Theoretical, eye diseases, Rats, 030104 developmental biology, Amacrine Cells, Object code, lcsh:Q, Artificial intelligence, Visual Fields, business, Neuroscience, 030217 neurology & neurosurgery, [SDV.MHEP]Life Sciences [q-bio]/Human health and pathology, Photic Stimulation
Abstract: In the early visual system, cells of the same type perform the same computation in different places of the visual field. How these cells code together a complex visual scene is unclear. A common assumption is that cells of a single-type extract a single-stimulus feature to form a feature map, but this has rarely been observed directly. Using large-scale recordings in the rat retina, we show that a homogeneous population of fast OFF ganglion cells simultaneously encodes two radically different features of a visual scene. Cells close to a moving object code quasilinearly for its position, while distant cells remain largely invariant to the object’s position and, instead, respond nonlinearly to changes in the object’s speed. We develop a quantitative model that accounts for this effect and identify a disinhibitory circuit that mediates it. Ganglion cells of a single type thus do not code for one, but two features simultaneously. This richer, flexible neural map might also be present in other sensory systems., Retinal ganglion cell subtypes are traditionally thought to encode a single visual feature across the visual field to form a feature map. Here the authors show that fast OFF ganglion cells in fact respond to two visual features, either object position or speed, depending on the stimulus location.
Published: 2017

17. Space-time sculpting of liquid animation

Author: Ulysse Vimont, Marie-Paule Cani, Damien Rohmer, Chris Wojtan, Pierre-Luc Manteaux, Intuitive Modeling and Animation for Interactive Graphics & Narrative Environments (IMAGINE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), ERC, European Project: 291184,EC:FP7:ERC,ERC-2011-ADG_20110209,EXPRESSIVE(2012), and Institute of Science and Technology [Austria] (IST Austria)
Subjects: Sequence, Shape analysis (program analysis), business.industry, Computer science, 020207 software engineering, 02 engineering and technology, Animation, Shape analysis, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Feature (computer vision), Computer graphics (images), 0202 electrical engineering, electronic engineering, information engineering, Trajectory, 020201 artificial intelligence & image processing, Polygon mesh, Computer vision, Artificial intelligence, business, Rotation (mathematics), Computer animation, space-time editing, sculpture, fluid animation, ComputingMethodologies_COMPUTERGRAPHICS
Abstract: International audience; We propose an interactive sculpting system for seamlessly editing pre-computed animations of liquid, without the need for any re-simulation. The input is a sequence of meshes without correspondences representing the liquid surface over time. Our method enables the efficient selection of consistent space-time parts of this animation, such as moving waves or droplets, which we call space-time features. Once selected, a feature can be copied, edited, or duplicated and then pasted back anywhere in space and time in the same or in another liquid animation sequence. Our method circumvents tedious user interactions by automatically computing the spatial and temporal ranges of the selected feature. We also provide space-time shape editing tools for non-uniform scaling, rotation, trajectory changes, and temporal editing to locally speed up or slow down motion. Using our tools, the user can edit and progressively refine any input simulation result, possibly using a library of pre-computed space-time features extracted from other animations. In contrast to the trial-and-error loop usually required to edit animation results through the tuning of indirect simulation parameters, our method gives the user full control over the edited space-time behaviors.
Published: 2016

18. PSYNC: A partially synchronous language for fault-tolerant distributed algorithms

Author: Cezara Drăgoi, Thomas A. Henzinger, Damien Zufferey, Analyse Statique par Interprétation Abstraite (ANTIQUE), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Institute of Science and Technology [Austria] (IST Austria), Computer Science and Artificial Intelligence Laboratory [Cambridge] (CSAIL), Massachusetts Institute of Technology (MIT), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
Subjects: Consensus, Scala, Computer science, Distributed computing, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Runtime system, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Round model, Formal verification, Implementation, computer.programming_language, Abstraction (linguistics), Automated verification, 020207 software engineering, Lockstep, Computer Graphics and Computer-Aided Design, Asynchrony (computer programming), 020202 computer hardware & architecture, 010201 computation theory & mathematics, Asynchronous communication, Distributed algorithm, 020201 artificial intelligence & image processing, Partially synchrony, computer, Fault-tolerant distributed algorithms, Software
Abstract: International audience; Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. We introduce PSYNC, a domain specific language based on the Heard-Of model, which views asynchronous faulty systems as synchronous ones with an adversarial environment that simulates asyn-chrony and faults by dropping messages. We define a runtime system for PSYNC that efficiently executes on asynchronous networks. We formalise the relation between the runtime system and PSYNC in terms of observational refinement. This high-level synchronous abstraction introduced by PSYNC simplifies the design and implementation of fault-tolerant distributed algorithms and enables automated formal verification. We have implemented an embedding of PSYNC in the SCALA programming language with a runtime system for partially synchronous networks. We show the applicability of PSYNC by implementing several important fault-tolerant distributed algorithms and we compare the implementation of consensus algorithms in PSYNC against implementations in other languages in terms of code size, runtime efficiency, and verification.
Published: 2016

19. Finding Non-Orientable Surfaces in 3-Manifolds

Author: Uli Wagner, Arnaud de Mesmay, Benjamin A. Burton, University of Queensland [Brisbane], Centre National de la Recherche Scientifique (CNRS), GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Institute of Science and Technology [Austria] (IST Austria), and Sandor Fekete and Anna Lubiw
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, Surface (mathematics), 0102 computer and information sciences, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Theoretical Computer Science, Combinatorics, symbols.namesake, Mathematics - Geometric Topology, 510 Mathematics, Genus (mathematics), [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT], FOS: Mathematics, Discrete Mathematics and Combinatorics, 0101 mathematics, Topology (chemistry), Mathematics, 000 Computer science, knowledge, general works, 010102 general mathematics, Geometric Topology (math.GT), Mathematics::Geometric Topology, 68U05, 57M50, 68Q25, ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems, Computational Theory and Mathematics, 010201 computation theory & mathematics, Computer Science, Euler's formula, symbols, Computer Science - Computational Geometry, Geometry and Topology, F.2.2
Abstract: We investigate the complexity of finding an embedded non-orientable surface of Euler genus $g$ in a triangulated $3$-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into $3$-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case., v2: minor changes
Published: 2016

20. Abstraction-Based Parameter Synthesis for Multiaffine Systems

Author: Hui Kong, Christian Schilling, Sergiy Bogomolov, Gregory Batt, Radu Grosu, Ezio Bartocci, Institute of Science and Technology [Austria] (IST Austria), University of Freiburg [Freiburg], Vienna University of Technology (TU Wien), Computational systems biology and optimization (Lifeware), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
Subjects: Model checking, 0209 industrial biotechnology, Theoretical computer science, Dynamical systems theory, Computer science, Kripke structure, 020207 software engineering, 02 engineering and technology, Automaton, Formalism (philosophy of mathematics), 020901 industrial engineering & automation, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-SY]Computer Science [cs]/Systems and Control [cs.SY], Hybrid automaton, Algorithm
Abstract: International audience; Multiaffine hybrid automata (MHA) represent a powerful formalism to model complex dynamical systems. This formalism is particularly suited for the representation of biological systems which often exhibit highly non-linear behavior. In this paper, we consider the problem of parameter identification for MHA. We present an abstraction of MHA based on linear hybrid automata, which can be analyzed by the SpaceEx model checker. This abstraction enables a precise handling of time-dependent properties. We demonstrate the potential of our approach on a model of a genetic regulatory network and a myocyte model.
Published: 2015

21. A reduction from parity games to simple stochastic games

Author: Krishnendu Chatterjee, Nathanaël Fijalkow, Institute of Science and Technology [Austria] (IST Austria), Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: FOS: Computer and information sciences, Computer Science::Computer Science and Game Theory, Theoretical computer science, Logarithm, Computer science, lcsh:Mathematics, 010102 general mathematics, ComputingMilieux_PERSONALCOMPUTING, 0102 computer and information sciences, lcsh:QA1-939, 01 natural sciences, lcsh:QA75.5-76.95, Computer Science - Computer Science and Game Theory, 010201 computation theory & mathematics, Reachability, [INFO]Computer Science [cs], lcsh:Electronic computers. Computer science, 0101 mathematics, Parity (mathematics), ComputingMilieux_MISCELLANEOUS, Computer Science and Game Theory (cs.GT), conference
Abstract: Games on graphs provide a natural model for reactive non-terminating systems. In such games, the interaction of two players on an arena results in an infinite path that describes a run of the system. Different settings are used to model various open systems in computer science, as for instance turn-based or concurrent moves, and deterministic or stochastic transitions. In this paper, we are interested in turn-based games, and specifically in deterministic parity games and stochastic reachability games (also known as simple stochastic games). We present a simple, direct and efficient reduction from deterministic parity games to simple stochastic games: it yields an arena whose size is linear up to a logarithmic factor in size of the original arena., In Proceedings GandALF 2011, arXiv:1106.0814
Published: 2011

22. The Need for Language Support for Fault-tolerant Distributed Systems

Author: Drăgoi, Cezara, Henzinger, Thomas, Zufferey, Damien, Analyse Statique par Interprétation Abstraite (ANTIQUE), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Institute of Science and Technology [Austria] (IST Austria), Computer Science and Artificial Intelligence Laboratory [Cambridge] (CSAIL), Massachusetts Institute of Technology (MIT), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
Subjects: 000 Computer science, knowledge, general works, 005 Computer programming, programs & data, 010201 computation theory & mathematics, Computer Science, 0202 electrical engineering, electronic engineering, information engineering, 020207 software engineering, [INFO]Computer Science [cs], 0102 computer and information sciences, 02 engineering and technology, 000 Computer science, knowledge & systems, 01 natural sciences
Abstract: International audience; Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asyn-chronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. Nonetheless there is surprisingly little language and verification support to build distributed systems based on fault-tolerant algorithms. In this paper, we present some of the challenges that a designer has to overcome to implement a fault-tolerant distributed system. Then we review different models that have been proposed to reason about distributed algorithms and sketch how such a model can form the basis for a domain-specific programming language. Adopting a high-level programming model can simplify the programmer's life and make the code amenable to automated verification, while still compiling to efficiently executable code. We conclude by summarizing the current status of an ongoing language design and implementation project that is based on this idea.
Published: 2015

23. Compositionality for Quantitative Specifications

Author: Louis-Marie Traonouez, Uli Fahrenberg, Jan Křetínský, Axel Legay, Efficient STAtistical methods in SYstems of systems (ESTASYS), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Inria Rennes, CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Institute of Science and Technology [Austria] (IST Austria), and UCL - SST/ICTM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Theoretical computer science, Iterative design, Computer science, Principle of compositionality, Computational intelligence, 0102 computer and information sciences, 02 engineering and technology, Residual, 01 natural sciences, Theoretical Computer Science, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 0202 electrical engineering, electronic engineering, information engineering, Trace distance, [INFO]Computer Science [cs], Quotient, Mathematics, 020207 software engineering, Logic in Computer Science (cs.LO), Modal, 010201 computation theory & mathematics, Geometry and Topology, Engineering design process, Algorithm, Software, Energy (signal processing)
Abstract: International audience; We provide a framework for compositional and iterative design and verification of systems with quantitative information, such as rewards, time or energy. It is based on disjunctive modal transition systems where we allow actions to bear various types of quantitative information. Throughout the design process the actions can be further refined and the information made more precise. We show how to compute the results of standard operations on the systems, including the quotient (residual), which has not been previously considered for quantitative non-deterministic systems. Our quantitative framework has close connections to the modal nu-calculus and is compositional with respect to general notions of distances between systems and the standard operations.
Published: 2015

24. Efficient zero-knowledge proofs for commitments from learning with errors over rings

Author: Vadim Lyubashevsky, Fabrice Benhamouda, Stephan Krenn, Krzysztof Pietrzak, École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL), Laboratoire d'informatique de l'école normale supérieure (LIENS), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Austrian Institute of Technology [Vienna] (AIT), Institute of Science and Technology [Austria] (IST Austria), ANR-13-JS02-0003,CLE,Cryptography from Learning with Errors(2013), European Project: 321310,EC:FP7:ERC,ERC-2012-ADG_20120216,PERCY(2013), European Project: 259668,EC:FP7:ERC,ERC-2010-StG_20091028,PSPC(2010), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)
Subjects: Discrete mathematics, Ring (mathematics), Mathematics::Commutative Algebra, Computer science, 004 Data processing & computer science, Multiplicative function, Rejection sampling, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 000 Computer science, knowledge & systems, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Commitment scheme, Zero-knowledge proof, Communication complexity, Constant (mathematics), Algorithm, Learning with errors, ComputingMilieux_MISCELLANEOUS
Abstract: We extend a commitment scheme based on the learning with errors over rings $$\mathsf{RLWE}$$ problem, and present efficient companion zero-knowledge proofs of knowledge. Our scheme maps elements from the ring or equivalently, n elements from $$\mathbb F_q$$ to a small constant number of ring elements. We then construct $$\varSigma $$-protocols for proving, in a zero-knowledge manner, knowledge of the message contained in a commitment. We are able to further extend our basic protocol to allow us to prove additive and multiplicative relations among committed values. Our protocols have a communication complexity of $$\mathcal {O}Mn\log q$$ and achieve a negligible knowledge error in one run. Here M is the constant from a rejection sampling technique that we employ, and can be set close to 1 by adjusting other parameters. Previously known $$\varSigma $$-protocols for LWE-related languages only achieved a noticeable or even constant knowledge error thus requiring many repetitions of the protocol, or relied on "smudging" out the error which necessitates working over large fields, resulting in poor efficiency.
Published: 2015

25. Majority Vote of Diverse Classifiers for Late Fusion

Author: Amaury Habrard, Stéphane Ayache, Emilie Morvant, Lampert Group, Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Laboratoire Hubert Curien (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), éQuipe AppRentissage et MultimediA [Marseille] (QARMA), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), European Project: 308036,EC:FP7:ERC,ERC-2012-StG_20111012,L3VISU(2013), Institute of Science and Technology [Austria] (IST Austria), Laboratoire Hubert Curien [Saint Etienne] (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: FOS: Computer and information sciences, Majority rule, Computer science, Machine Learning (stat.ML), 02 engineering and technology, Machine learning, computer.software_genre, Machine Learning (cs.LG), Set (abstract data type), Majority vote, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, 0202 electrical engineering, electronic engineering, information engineering, Quadratic programming, computer.programming_language, Modality (human–computer interaction), business.industry, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], 020207 software engineering, Pascal (programming language), 16. Peace & justice, Multimedia (cs.MM), Computer Science - Learning, Ranking, Classifier fusion, Benchmark (computing), Multimedia analysis, 020201 artificial intelligence & image processing, Pairwise comparison, Artificial intelligence, business, computer, Computer Science - Multimedia
Abstract: In the past few years, a lot of attention has been devoted to multimedia indexing by fusing multimodal informations. Two kinds of fusion schemes are generally considered: The early fusion and the late fusion. We focus on late classifier fusion, where one combines the scores of each modality at the decision level. To tackle this problem, we investigate a recent and elegant well-founded quadratic program named MinCq coming from the machine learning PAC-Bayesian theory. MinCq looks for the weighted combination, over a set of real-valued functions seen as voters, leading to the lowest misclassification rate, while maximizing the voters' diversity. We propose an extension of MinCq tailored to multimedia indexing. Our method is based on an order-preserving pairwise loss adapted to ranking that allows us to improve Mean Averaged Precision measure while taking into account the diversity of the voters that we want to fuse. We provide evidence that this method is naturally adapted to late fusion procedures and confirm the good behavior of our approach on the challenging PASCAL VOC'07 benchmark., Comment: IAPR Joint International Workshops on Statistical Techniques in Pattern Recognition and Structural and Syntactic Pattern Recignition, Joensuu : Finland (2014)
Published: 2014

26. Short Blind Signatures

Author: David Pointcheval, Olivier Blazy, Damien Vergnaud, Georg Fuchsbauer, Ruhr-Universität Bochum [Bochum], Institute of Science and Technology [Austria] (IST Austria), Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)
Subjects: mixed commitments, Theoretical computer science, Computer Networks and Communications, Computer science, Hash function, Bilinear interpolation, 0102 computer and information sciences, 02 engineering and technology, Computer security, computer.software_genre, 01 natural sciences, [SHS]Humanities and Social Sciences, 0202 electrical engineering, electronic engineering, information engineering, Blind signature, medicine, Session (computer science), Safety, Risk, Reliability and Quality, Computer Science::Cryptography and Security, Blindness, medicine.disease, WSN, Signature (logic), 010201 computation theory & mathematics, Hardware and Architecture, ComputingMilieux_COMPUTERSANDSOCIETY, Blind signatures, 020201 artificial intelligence & image processing, computer, e-cash, Software
Abstract: International audience; Blind signatures allow users to obtain signatures on messages hidden from the signer; moreover, the signer cannot link the resulting message/signature pair to the signing session. This paper presents blind signature schemes, in which the number of interactions between the user and the signer is minimal and whose blind signatures are short. Our schemes are defined over bilinear groups and are proved secure in the common-reference-string model without random oracles and under standard assumptions: CDH and the decision-linear assumption. (We also give variants over asymmetric groups based on similar assumptions.) The blind signatures are Waters signatures, which consist of 2 group elements. Moreover, we instantiate partially blind signatures, where the message consists of a part hidden from the signer and a commonly known public part, and schemes achieving perfect blindness. We propose new variants of blind signatures, such as signer-friendly partially blind signatures, where the public part can be chosen by the signer without prior agreement, 3-party blind signatures, as well as blind signatures on multiple aggregated messages provided by independent sources. We also extend Waters signatures to non-binary alphabets by proving a new result on the underlying hash function.
Published: 2013

27. Infinite-state games with finitary conditions

Author: Chatterjee, Krishnendu, Fijalkow, Nathanaël, Institute of Science and Technology [Austria] (IST Austria), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), and University of Warsaw (UW)
Subjects: FOS: Computer and information sciences, Computer Science::Computer Science and Game Theory, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, 02 engineering and technology, 000 Computer science, knowledge & systems, Computer Science - Computer Science and Game Theory, Computer Science::Logic in Computer Science, Bounds in omega-regularity, 0202 electrical engineering, electronic engineering, information engineering, Two-player games, [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, 060201 languages & linguistics, 000 Computer science, knowledge, general works, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Pushdown games, ComputingMilieux_PERSONALCOMPUTING, 06 humanities and the arts, Verification and synthesis, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Infinite-state systems, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, 0602 languages and literature, Computer Science, 020201 artificial intelligence & image processing, Computer Science::Formal Languages and Automata Theory, conference, Computer Science and Game Theory (cs.GT)
Abstract: We study two-player zero-sum games over infinite-state graphs equipped with ωB and finitary conditions. Our first contribution is about the strategy complexity, i.e the memory required for winning strategies: we prove that over general infinite-state graphs, memoryless strategies are sufficient for finitary BÃ¼chi, and finite-memory suffices for finitary parity games. We then study pushdown games with boundedness conditions, with two contributions. First we prove a collapse result for pushdown games with ωB-conditions, implying the decidability of solving these games. Second we consider pushdown games with finitary parity along with stack boundedness conditions, and show that solving these games is EXPTIME-complete.
Published: 2013

28. Nondeterminism in the Presence of a Diverse or Unknown Future

Author: Denis Kuperberg, Udi Boker, Orna Kupferman, Michał Skrzypczak, Institute of Science and Technology [Austria] (IST Austria), The Hebrew University of Jerusalem (HUJ), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), and University of Warsaw (UW)
Subjects: Discrete mathematics, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Nested word, Theoretical computer science, Computer science, 010102 general mathematics, 0102 computer and information sciences, ω-automaton, Nonlinear Sciences::Cellular Automata and Lattice Gases, 01 natural sciences, Mobile automaton, Nondeterministic algorithm, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 010201 computation theory & mathematics, Deterministic automaton, Quantum finite automata, Automata theory, Nondeterministic finite automaton, 0101 mathematics, Computer Science::Formal Languages and Automata Theory
Abstract: International audience; Choices made by nondeterministic word automata depend on both the past (the prefix of the word read so far) and the future (the suffix yet to be read). In several applications, most notably synthesis, the future is diverse or unknown, leading to algorithms that are based on deterministic automata. Hoping to retain some of the advantages of nondeterministic automata, researchers have studied restricted classes of nondeterministic automata. Three such classes are nondeterministic automata that are good for trees (GFT; i.e., ones that can be expanded to tree automata accepting the derived tree languages, thus whose choices should satisfy diverse futures), good for games (GFG; i.e., ones whose choices depend only on the past), and determinizable by pruning (DBP; i.e., ones that embody equivalent deterministic automata). The theoretical properties and relative merits of the different classes are still open, having vagueness on whether they really differ from deterministic automata. In particular, while DBP ⊆ GFG ⊆ GFT, it is not known whether every GFT automaton is GFG and whether every GFG automaton is DBP. Also open is the possible succinctness of GFG and GFT automata compared to deterministic automata. We study these problems for ω-regular automata with all common acceptance conditions. We show that GFT=GFG⊃DBP, and describe a determinization construction for GFG automata.
Published: 2013

29. Guest Editorial: Special Issue on Structured Prediction and Inference

Author: Christoph H. Lampert, Matthew B. Blaschko, Organ Modeling through Extraction, Representation and Understanding of Medical Image Content (GALEN), Ecole Centrale Paris-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre de vision numérique (CVN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec, Institute of Science and Technology [Austria] (IST Austria), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Ecole Centrale Paris, and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
Subjects: Computer science, business.industry, Dimensionality reduction, Word error rate, Inference, Machine learning, computer.software_genre, Field (computer science), Support vector machine, Statistical classification, Artificial Intelligence, Pattern recognition (psychology), [INFO]Computer Science [cs], Computer Vision and Pattern Recognition, Artificial intelligence, Structured prediction, business, computer, Software, ComputingMilieux_MISCELLANEOUS
Abstract: Computer vision has been profoundly influenced by machine learning in the past two decades. Canonical papers in the field, such as [Turk and Pentland(1991)], have applied statistical methods to visual data to achieve results that are both compelling and accurate. Classification algorithms, such as support vector machines, are now commonly applied to discriminatively train vision systems. Such systems empirically minimize risk functionals that measure the expected classification error rate given an i.i.d. sampling assumption [Vapnik(1998), Scholkopf and Smola(2002)]. While many intermediate goals in computer vision can be formulated as classification, regression, or dimensionality reduction– the settings most commonly addressed in the machine learning literature–more appropriate statistical methods are needed to train vision systems that make collections of related predictions, such as in segmentation, parts based models, or scene layout analysis. In these settings, the independence assumptions made by binary classifiers no longer hold, and independent prediction may not be computationally or statistically feasible. Structured output prediction [Bakir et al(2007)Bakir, Hofmann, Scholkopf, Smola, Taskar, and Vishwanathan, Nowozin and Lampert(2011)] is the task of predicting related variables given some input, such as image or video data. Study of structured output prediction in the machine learning field has led to a number of techniques be
Published: 2012

30. Synchronous interface theories and time triggered scheduling

Author: Uli Fahrenberg, Dejan Nickovic, Axel Legay, Benoît Delahaye, Thomas A. Henzinger, AELOS, Laboratoire d'Informatique de Nantes Atlantique (LINA), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Efficient STAtistical methods in SYstems of systems (ESTASYS), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Holger Giese, Grigore Rosu, TC 6, WG 6.1, Giese, Holger, Rosu, Grigore, Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), and Institute of Science and Technology [Austria] (IST Austria)
Subjects: Theoretical computer science, Computer science, Interface model, Computation, Distributed computing, 004 Data processing & computer science, Mathematical properties, 020207 software engineering, Shared variables, Interface theory, 02 engineering and technology, Systems modeling, Fully automatic, Compatibility (mechanics), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs]
Abstract: International audience; We propose synchronous interfaces, a new interface theory for discrete-time systems. We use an application to time-triggered scheduling to drive the design choices for our formalism; in particular, additionally to deriving useful mathematical properties, we focus on providing a syntax which is adapted to natural high-level system modeling. As a result, we develop an interface model that relies on a guarded-command based language and is equipped with shared variables and explicit discrete-time clocks. We define all standard interface operations: compatibility checking, composition, refinement, and shared refinement. Apart from the synchronous interface model, the contribution of this paper is the establishment of a formal relation between interface theories and real-time scheduling, where we demonstrate a fully automatic framework for the incremental computation of time-triggered schedules.
Published: 2012

31. Lapin: An efficient authentication protocol based on Ring-LPN

Author: Stefan Heyse, Krzysztof Pietrzak, Vadim Lyubashevsky, Christof Paar, Eike Kiltz, Horst Gortz Institute for IT Security, Ruhr University Bochum (RUB), Ruhr-Universität Bochum [Bochum], Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Austria] (IST Austria), Anne Canteaut, Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
Subjects: Ring (mathematics), Otway–Rees protocol, Computer science, business.industry, Byte, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, Authentication protocol, Universal composability, 0202 electrical engineering, electronic engineering, information engineering, Noise (video), business, Communication complexity, Protocol (object-oriented programming), Computer network
Abstract: International audience; We propose a new authentication protocol that is provably secure based on a ring variant of the learning parity with noise (LPN) problem. The protocol follows the design principle of the LPN-based protocol from Eurocrypt'11 (Kiltz et al.), and like it, is a two round protocol secure against active attacks. Moreover, our protocol has small communication complexity and a very small footprint which makes it applicable in scenarios that involve low-cost, resource-constrained devices. Performance-wise, our protocol is more efficient than previous LPN-based schemes, such as the many variants of the Hopper-Blum (HB) protocol and the aforementioned protocol from Eurocrypt'11. Our implementation results show that it is even comparable to the standard challenge-and-response protocols based on the AES block-cipher. Our basic protocol is roughly 20 times slower than AES, but with the advantage of having 10 times smaller code size. Furthermore, if a few hundred bytes of non-volatile memory are available to allow the storage of some off-line pre-computations, then the online phase of our protocols is only twice as slow as AES.
Published: 2012

32. Information transmission in genetic regulatory networks: a review

Author: Aleksandra M. Walczak, Gašper Tkačik, Laboratoire de Physique Théorique de l'ENS (LPTENS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Fédération de recherche du Département de physique de l'Ecole Normale Supérieure - ENS Paris (FRDPENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Austria] (IST Austria), Laboratoire de Physique Théorique de l'ENS [École Normale Supérieure] (LPTENS), Fédération de recherche du Département de physique de l'Ecole Normale Supérieure - ENS Paris (FRDPENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
Subjects: Computer science, Entropy, Molecular Networks (q-bio.MN), [PHYS.PHYS.PHYS-BIO-PH]Physics [physics]/Physics [physics]/Biological Physics [physics.bio-ph], Reliability (computer networking), media_common.quotation_subject, Information Theory, Gene regulatory network, FOS: Physical sciences, Information theory, 01 natural sciences, 03 medical and health sciences, 0103 physical sciences, Gene Regulatory Networks, General Materials Science, Quantitative Biology - Molecular Networks, Physics - Biological Physics, 010306 general physics, Function (engineering), 030304 developmental biology, media_common, Regulation of gene expression, 0303 health sciences, Information transmission, Models, Genetic, Condensed Matter Physics, Data science, Multicellular organism, Biological Physics (physics.bio-ph), FOS: Biological sciences, ComputingMethodologies_GENERAL, Transcription Factors
Abstract: Genetic regulatory networks enable cells to respond to the changes in internal and external conditions by dynamically coordinating their gene expression profiles. Our ability to make quantitative measurements in these biochemical circuits has deepened our understanding of what kinds of computations genetic regulatory networks can perform and with what reliability. These advances have motivated researchers to look for connections between the architecture and function of genetic regulatory networks. Transmitting information between network's inputs and its outputs has been proposed as one such possible measure of function, relevant in certain biological contexts. Here we summarize recent developments in the application of information theory to gene regulatory networks. We first review basic concepts in information theory necessary to understand recent work. We then discuss the functional complexity of gene regulation which arrises from the molecular nature of the regulatory interactions. We end by reviewing some experiments supporting the view that genetic networks responsible for early development of multicellular organisms might be maximizing transmitted 'positional' information., Submitted to J Phys: Condens Matter, 31 pages
Published: 2011

33. Finitary Languages

Author: Krishnendu Chatterjee, Nathanaël Fijalkow, Institute of Science and Technology [Austria] (IST Austria), and École normale supérieure - Cachan (ENS Cachan)
Subjects: FOS: Computer and information sciences, Class (set theory), liveness properties, Formal Languages and Automata Theory (cs.FL), Computer science, Existential quantification, Liveness, Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 02 engineering and technology, Characterization (mathematics), 01 natural sciences, finitary liveness, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Fragment (logic), Computer Science::Logic in Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Finitary, bounds in omega-regularity, Discrete mathematics, theoretical studies in language theory, 020207 software engineering, Specification language, Finitary languages, Automaton, 010201 computation theory & mathematics, verification, Computer Science::Formal Languages and Automata Theory
Abstract: International audience; The class of omega-regular languages provides a robust specification language in verification. Every omega-regular condition can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens ``eventually''. Finitary liveness was proposed by Alur and Henzinger as a stronger formulation of liveness. It requires that there exists an unknown, fixed bound b such that something good happens within b transitions. In this work we consider automata with finitary acceptance conditions defined by finitary Buchi, parity and Streett languages. We study languages expressible by such automata: we give their topological complexity and present a regular-expression characterization. We compare the expressive power of finitary automata and give optimal algorithms for classical decisions questions. We show that the finitary languages are Sigma 2-complete; we present a complete picture of the expressive power of various classes of automata with finitary and infinitary acceptance conditions; we show that the languages defined by finitary parity automata exactly characterize the star-free fragment of omega B-regular languages; and we show that emptiness is NLOGSPACE-complete and universality as well as language inclusion are PSPACE-complete for finitary parity and Streett automata.
Published: 2011

34. Randomness for Free

Author: Hugo Gimbert, Thomas A. Henzinger, Krishnendu Chatterjee, Laurent Doyen, Institute of Science and Technology [Austria] (IST Austria), Laboratoire Spécification et Vérification [Cachan] (LSV), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Petr Hliněný and Antonín Kučera
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computer Science::Computer Science and Game Theory, Theoretical computer science, Computer science, 004 Data processing & computer science, 0102 computer and information sciences, Characterization (mathematics), 01 natural sciences, Theoretical Computer Science, Computer Science - Computer Science and Game Theory, 0101 mathematics, Randomness, Mathematics, Discrete mathematics, Basis (linear algebra), [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Transition function, Transition (fiction), Stochastic game, 010102 general mathematics, Mode (statistics), Probabilistic logic, ComputingMilieux_PERSONALCOMPUTING, Randomized algorithms as zero-sum games, Computer Science Applications, Logic in Computer Science (cs.LO), Computational Theory and Mathematics, 010201 computation theory & mathematics, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Information Systems, Computer Science and Game Theory (cs.GT)
Abstract: International audience; We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (both players interact simultaneously); and (b) turn-based (both players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. In this work we present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games.
Published: 2010
Full Text: View/download PDF

35. Lumpability abstractions of rule-based systems

Author: Thomas A. Henzinger, Heinz Koeppl, Jérôme Feret, Tatjana Petrov, Abstract Interpretation and Static Analysis (ABSTRACTION), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Austria] (IST Austria), Ecole Polytechnique Fédérale de Lausanne (EPFL), Ciobanu, G. and Koutny, M., Ciobanu, G. and Koutny, M., ANR-09-CEXC-0001,AbstractCell,Abstraction formelle de sémantiques quantitatives pour les modèles de réseaux d'interactions entre protéines dans les celluces.(2009), BISON, Institut für Automatik - Automatic Control Laboratory (IFA), Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
Subjects: FOS: Computer and information sciences, Theoretical computer science, General Computer Science, Computer science, Systems biology, Lumpability, Markov process, 0102 computer and information sciences, 02 engineering and technology, 000 Computer science, knowledge & systems, 01 natural sciences, lcsh:QA75.5-76.95, Theoretical Computer Science, Computational Engineering, Finance, and Science (cs.CE), 010104 statistics & probability, symbols.namesake, Combinatorial complexity, 0202 electrical engineering, electronic engineering, information engineering, cell signaling, Bisimulation, 0101 mathematics, Invariant (mathematics), Computer Science - Computational Engineering, Finance, and Science, Equivalence class, Quotient, 005 Computer programming, programs & data, Markov chain, Markov chains, lcsh:Mathematics, Conditional probability, Rule-based system, lcsh:QA1-939, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Abstraction, 010201 computation theory & mathematics, Transition system, Thermodynamic limit, symbols, 570 Life sciences, biology, 020201 artificial intelligence & image processing, lcsh:Electronic computers. Computer science, ddc:004, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Algorithm, Kappa, Computer Science(all)
Abstract: The induction of a signaling pathway is characterized by transient complex formation and mutual posttranslational modification of proteins. To faithfully capture this combinatorial process in a mathematical model is an important challenge in systems biology. Exploiting the limited context on which most binding and modification events are conditioned, attempts have been made to reduce the combinatorial complexity by quotienting the reachable set of molecular species, into species aggregates while preserving the deterministic semantics of the thermodynamic limit. Recently we proposed a quotienting that also preserves the stochastic semantics and that is complete in the sense that the semantics of individual species can be recovered from the aggregate semantics. In this paper we prove that this quotienting yields a sufficient condition for weak lumpability and that it gives rise to a backward Markov bisimulation between the original and aggregated transition system. We illustrate the framework on a case study of the EGF/insulin receptor crosstalk., Comment: In Proceedings MeCBIC 2010, arXiv:1011.0051
Published: 2010

36. SpaceMint: A Cryptocurrency Based on Proofs of Space

Author: Albert Kwon, Sunoo Park, Peter Gaži, Joël Alwen, Georg Fuchsbauer, Krzysztof Pietrzak, Massachusetts Institute of Technology (MIT), Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), ANR-16-CE39-0002,EfTrEC,Monnaie électronique transférable efficace(2016), European Project: 682815,H2020,ERC-2015-CoG,TOCNeT(2016), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Institute of Science and Technology [Austria] (IST Austria), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris
Subjects: 0301 basic medicine, Cryptocurrency, Computer science, 02 engineering and technology, Space (commercial competition), Mathematical proof, Computer security, computer.software_genre, 03 medical and health sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 030104 developmental biology, Proof-of-work system, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Protocol (object-oriented programming), computer, Drawback
Abstract: International audience; Bitcoin has become the most successful cryptocurrency ever deployed, and its most distinctive feature is that it is decentralized. Its underlying protocol (Nakamoto consensus) achieves this by using proof of work, which has the drawback that it causes the consumption of vast amounts of energy to maintain the ledger. Moreover, Bitcoin mining dynamics have become less distributed over time.Towards addressing these issues, we propose SpaceMint, a cryptocurrency based on proofs of space instead of proofs of work. Miners in SpaceMint dedicate disk space rather than computation. We argue that SpaceMint's design solves or alleviates several of Bitcoin's issues: most notably, its large energy consumption. SpaceMint also rewards smaller miners fairly according to their contribution to the network, thus incentivizing more distributed participation.This paper adapts proof of space to enable its use in cryptocurrency, studies the attacks that can arise against a Bitcoin-like blockchain that uses proof of space, and proposes a new blockchain format and transaction types to address these attacks. Our prototype shows that initializing 1 TB for mining takes about a day (a one-off setup cost), and miners spend on average just a fraction of a second per block mined. Finally, we provide a game-theoretic analysis modeling SpaceMint as an extensive game (the canonical game-theoretic notion for games that take place over time) and show that this stylized game satisfies a strong equilibrium notion, thereby arguing for SpaceMint's stability and consensus.
Full Text: View/download PDF

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

36 results on '"Institute of Science and Technology [Austria] (IST Austria)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources