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

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

Start Over Author "Institute of Science and Technology [Austria] (IST Austria)" Topic 02 engineering and technology

38 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. On a certain non-split cubic surface

Author: Yongqiang Zhao, Kevin Destagnol, Jie Wu, Jianya Liu, Régis de la Bretèche, Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)), Université Paris Diderot - Paris 7 (UPD7)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Austria] (IST Austria), Shandong University, Laboratoire d'Analyse et de Mathématiques Appliquées (LAMA), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Fédération de Recherche Bézout-Université Paris-Est Marne-la-Vallée (UPEM), Westlake University, Université Paris-Est Marne-la-Vallée (UPEM)-Fédération de Recherche Bézout-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS), and Institute of Science and Technology [Austria] - IST Austria (IST Austria)
Subjects: asymptotic formula, Pure mathematics, Cubic surface, singular cubic surface, Mathematics::Commutative Algebra, Mathematics - Number Theory, General Mathematics, Mathematics::Number Theory, 010102 general mathematics, 0211 other engineering and technologies, 021107 urban & regional planning, 02 engineering and technology, Term (logic), 01 natural sciences, non-split toric surface, rational points, Bounded function, FOS: Mathematics, Asymptotic formula, Number Theory (math.NT), 0101 mathematics, [MATH]Mathematics [math], Manin-Peyre conjecture, Mathematics, descent on torsors
Abstract: In this note, we establish an asymptotic formula for the number of rational points of bounded height on the singular cubic surface $$ x_0(x_1^2 + x_2^2)=x_3^3 $$ with a power-saving error term, which verifies the Manin-Peyre conjectures for this surface., v2. 18 pages, one author added
Published: 2017

3. A single-molecule approach to explore binding, uptake and transport of cancer cell targeting nanotubes

Author: Mario Brameshuber, Gerhard J. Schütz, Jürgen Danzberger, Elena Heister, Barbara Unterauer, Peter Hinterdorfer, Constanze Lamprecht, Stefan Wieser, Andreas Ebner, Birgit Plochberger, Emmanuel Flahaut, Verena Ruprecht, Christian Rankl, Petar Lukanov, Johannes Kepler Universität Linz (JKU), Christian-Albrechts-Universität zu Kiel (CAU), Vienna University of Technology (TU Wien), Institute of Science and Technology [Austria] (IST Austria), Agilent Technologies, University of Surrey (UNIS), Centre interuniversitaire de recherche et d'ingenierie des matériaux (CIRIMAT), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Institut de Chimie du CNRS (INC), Center for Advanced Bioanalysis - CBL (AUSTRIA), Centre National de la Recherche Scientifique - CNRS (FRANCE), Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE), Technische Universität Wien - TU Wien (AUSTRIA), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Agilent Technologies (USA), Christian-Albrechts-Universität zu Kiel - CAU (GERMANY), Institute of Science and Technology Austria - IST Austria (AUSTRIA), Linz Johannes Kepler University (AUSTRIA), University of Surrey (UNITED KINGDOM), Centre Interuniversitaire de Recherche et d'Ingénierie des Matériaux - CIRIMAT (Toulouse, France), and Institut National Polytechnique de Toulouse - INPT (FRANCE)
Subjects: Materials science, Matériaux, media_common.quotation_subject, Carbon nanotubes, Médecine humaine et pathologie, Bioengineering, Nanotechnology, 02 engineering and technology, Carbon nanotube, Microscopy, Atomic Force, law.invention, [SPI.MAT]Engineering Sciences [physics]/Materials, 03 medical and health sciences, Molecular recognition, Cytosol, Drug Delivery Systems, Folic Acid, law, Cell Line, Tumor, Molecule, Humans, General Materials Science, Electrical and Electronic Engineering, Receptor, Internalization, 030304 developmental biology, media_common, 0303 health sciences, Nanotubes, Carbon, Particle tracking, Mechanical Engineering, Nocodazole, Force spectroscopy, General Chemistry, [CHIM.MATE]Chemical Sciences/Material chemistry, 021001 nanoscience & nanotechnology, Molecular Docking Simulation, Mechanics of Materials, Docking (molecular), Biophysics, AFM, 0210 nano-technology, [SDV.MHEP]Life Sciences [q-bio]/Human health and pathology
Abstract: International audience; In the past decade carbon nanotubes (CNTs) have been widely studied as a potential drug-delivery system, especially with functionality for cellular targeting. Yet, little is known about the actual process of docking to cell receptors and transport dynamics after internalization. Here we performed single-particle studies of folic acid (FA) mediated CNT binding to human carcinoma cells and their transport inside the cytosol. In particular, we employed molecular recognition force spectroscopy, an atomic force microscopy based method, to visualize and quantify docking of FA functionalized CNTs to FA binding receptors in terms of binding probability and binding force. We then traced individual fluorescently labeled, FA functionalized CNTs after specific uptake, and created a dynamic 'roadmap' that clearly showed trajectories of directed diffusion and areas of nanotube confinement in the cytosol. Our results demonstrate the potential of a single-molecule approach for investigation of drug-delivery vehicles and their targeting capacity.
Published: 2014

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. The Topological Correctness of PL Approximations of Isomanifolds

Author: Mathijs Wintraecken, Jean-Daniel Boissonnat, Université Côte d'Azur (UCA), Understanding the Shape of Data (DATASHAPE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), European Project: 339025,EC:FP7:ERC,ERC-2013-ADG,GUDHI(2014), Institute of Science and Technology [Austria] (IST Austria), and ANR-19-P3IA-0002,3IA Côte d'Azur,Nice - Interdisciplinary Institute for Artificial Intelligence(2019)
Subjects: 0209 industrial biotechnology, Generalization, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Boundary (topology), Isotopy, 02 engineering and technology, 0102 computer and information sciences, Topology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Fréchet distance, 020901 industrial engineering & automation, [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT], Piecewise-linear approximation, 0202 electrical engineering, electronic engineering, information engineering, Isomanifolds, 0101 mathematics, PL-approximations, Mathematics, Triangulation (topology), and phrases PL-approximations, Zero set, Multivalued function, Applied Mathematics, 010102 general mathematics, Codimension, Isomanifold, Ambient space, Computational Mathematics, Solution manifolds, Computational Theory and Mathematics, 010201 computation theory & mathematics, [MATH.MATH-AT]Mathematics [math]/Algebraic Topology [math.AT], Topological correctness, 020201 artificial intelligence & image processing, Topological conjugacy, Analysis
Abstract: Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine triangulation 𝒯. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary., LIPIcs, Vol. 164, 36th International Symposium on Computational Geometry (SoCG 2020), pages 20:1-20:18
Published: 2021

6. Long-range Temporal Correlations in the Broadband Resting state Activity of the Human Brain revealed by Neuronal Avalanches

Author: Fabrizio Lombardi, Hans J. Herrmann, Oren Shriki, Lucilla de Arcangelis, Institute of Science and Technology [Austria] (IST Austria), Lombardi, F, Shriki, O, Herrmann, H. J., and de Arcangelis, L
Subjects: 0209 industrial biotechnology, Brain activity and meditation, Cognitive Neuroscience, Context (language use), 02 engineering and technology, Electroencephalography, 01 natural sciences, 03 medical and health sciences, [SCCO]Cognitive science, 020901 industrial engineering & automation, 0302 clinical medicine, Artificial Intelligence, 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, medicine, Feature (machine learning), 010306 general physics, Scaling, Physics, medicine.diagnostic_test, Resting state fMRI, Quantitative Biology::Neurons and Cognition, Magnetoencephalography, Human brain, Computer Science Applications, medicine.anatomical_structure, 020201 artificial intelligence & image processing, Neuroscience, 030217 neurology & neurosurgery
Abstract: Resting-state brain activity is characterized by the presence of neuronal avalanches showing absence of characteristic size. Such evidence has been interpreted in the context of criticality and associated with the normal functioning of the brain. A distinctive attribute of systems at criticality is the presence of long-range correlations. Thus, to verify the hypothesis that the brain operates close to a critical point and consequently assess deviations from criticality for diagnostic purposes, it is of primary importance to robustly and reliably characterize correlations in resting-state brain activity. Recent works focused on the analysis of narrow-band electroencephalography (EEG) and magnetoencephalography (MEG) signal amplitude envelope, showing evidence of long-range temporal correlations (LRTC) in neural oscillations. However, brain activity is a broadband phenomenon, and a significant piece of information useful to precisely discriminate between normal (critical) and pathological behavior (non-critical), may be encoded in the broadband spatio-temporal cortical dynamics. Here we propose to characterize the temporal correlations in the broadband brain activity through the lens of neuronal avalanches. To this end, we consider resting-state EEG and long-term MEG recordings, extract the corresponding neuronal avalanche sequences, and study their temporal correlations. We demonstrate that the broadband resting-state brain activity consistently exhibits long-range power-law correlations in both EEG and MEG recordings, with similar values of the scaling exponents. Importantly, although we observe that the avalanche size distribution depends on scale parameters, scaling exponents characterizing long-range correlations are quite robust. In particular, they are independent of the temporal binning (scale of analysis), indicating that our analysis captures intrinsic characteristics of the underlying dynamics. Because neuronal avalanches constitute a fundamental feature of neural systems with universal characteristics, the proposed approach may serve as a general, systems- and experiment-independent procedure to infer the existence of underlying long-range correlations in extended neural systems, and identify pathological behaviors in the complex spatio-temporal interplay of cortical rhythms.
Published: 2020

7. 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

8. Extending Drawings of Graphs to Arrangements of Pseudolines

Author: Arroyo, Alan, Bensmail, Julien, Richter, R. Bruce, Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), University of Waterloo [Waterloo], Institute of Science and Technology [Austria] (IST Austria), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: graphs, 050101 languages & linguistics, crossing numbers, 05 social sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], arrangements of pseudolines, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, graph drawings, Combinatorics (math.CO), stretchability, 05C10, 05C85, 52C40, 52C30, geometric graph drawings
Abstract: In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of $K_n$ was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible., Journal of Computational Geometry, Vol. 12 No. 2 (2021)
Published: 2020

9. Broad spectral tuning of ultra-low-loss polaritons in a van der Waals crystal by intercalation

Author: Qiaoliang Bao, Ion Errea, Jiahua Duan, Kyle Crowley, Javier Martín-Sánchez, Weiliang Ma, Halyna Volkova, Marta Autore, Ivan Prieto, Alexey Y. Nikitin, Javier Taboada-Gutiérrez, Andrei Bylinkin, Pablo Alonso-González, Rainer Hillenbrand, Kenta Kimura, Gonzalo Álvarez-Pérez, Shaojuan Li, Marie-Hélène Berger, Xuan P. A. Gao, Tsuyoshi Kimura, Principado de Asturias, Agencia Estatal de Investigación (España), Ministerio de Ciencia, Innovación y Universidades (España), European Commission, Air Force Office of Scientific Research (US), Ministerio de Economía y Competitividad (España), Eusko Jaurlaritza, Australian Research Council, Ministerio de Economía, Industria y Competitividad (España), European Research Council, Institute of Science and Technology [Austria] (IST Austria), Centre des Matériaux (MAT), MINES ParisTech - École nationale supérieure des mines de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Graduate School of Engineering, Osaka University, Osaka University [Osaka], Donostia International Physics Center - DIPC (SPAIN), Donostia International Physics Center (DIPC), University of the Basque Country/Euskal Herriko Unibertsitatea (UPV/EHU)-University of the Basque Country/Euskal Herriko Unibertsitatea (UPV/EHU), CIC nanoGUNE Consolider, and Donostia International Physcis Center
Subjects: Materials science, Phonon, Intercalation (chemistry), Nanophotonics, Physics::Optics, 02 engineering and technology, 010402 general chemistry, 01 natural sciences, 7. Clean energy, Molecular physics, Crystal, symbols.namesake, Condensed Matter::Materials Science, Condensed Matter::Superconductivity, Polariton, General Materials Science, [PHYS.COND]Physics [physics]/Condensed Matter [cond-mat], business.industry, Mechanical Engineering, General Chemistry, Spectral bands, 021001 nanoscience & nanotechnology, Condensed Matter Physics, 0104 chemical sciences, Semiconductor, Mechanics of Materials, symbols, van der Waals force, 0210 nano-technology, business
Abstract: Phonon polaritons—light coupled to lattice vibrations—in polar van der Waals crystals are promising candidates for controlling the flow of energy on the nanoscale due to their strong field confinement, anisotropic propagation and ultra-long lifetime in the picosecond range1,2,3,4,5. However, the lack of tunability of their narrow and material-specific spectral range—the Reststrahlen band—severely limits their technological implementation. Here, we demonstrate that intercalation of Na atoms in the van der Waals semiconductor α-V2O5 enables a broad spectral shift of Reststrahlen bands, and that the phonon polaritons excited show ultra-low losses (lifetime of 4 ± 1 ps), similar to phonon polaritons in a non-intercalated crystal (lifetime of 6 ± 1 ps). We expect our intercalation method to be applicable to other van der Waals crystals, opening the door for the use of phonon polaritons in broad spectral bands in the mid-infrared domain., J.T.-G. and G.Á.-P. acknowledge support through the Severo Ochoa Program from the Government of the Principality of Asturias (nos. PA-18-PF-BP17-126 and PA-20-PF-BP19-053, respectively). J.M.-S. acknowledges finantial support from the Clarín Programme from the Government of the Principality of Asturias and a Marie Curie-COFUND grant (PA-18-ACB17-29) and the Ramón y Cajal Program from the Government of Spain (RYC2018-026196-I). K.C., X.P.A.G., H.V. and M.H.B. acknowledge the Air Force Office of Scientific Research (AFOSR) grant no. FA 9550-18-1-0030 for funding support. I.E. acknowledges financial support from the Spanish Ministry of Economy and Competitiveness (grant no. FIS2016-76617-P). A.Y.N. acknowledges the Spanish Ministry of Science, Innovation and Universities (national project no. MAT2017-88358-C3-3-R) and the Basque Government (grant no. IT1164-19). Q.B. acknowledges the support from Australian Research Council (grant nos. FT150100450, IH150100006 and CE170100039). R.H. acknowledges support from the Spanish Ministry of Economy, Industry, and Competitiveness (national project RTI2018-094830-B-100 and the Project MDM-2016-0618 of the María de Maeztu Units of Excellence Program) and the Basque Goverment (grant no. IT1164-19). P.A.-G. acknowledges support from the European Research Council under starting grant no. 715496, 2DNANOPTICA.
Published: 2020

10. Effect of the Anomalous Diffusion of Fluctuating Cooper Pairs in the Density of States of Superconducting NbN Thin Films

Author: Brigitte Leridon, Pietro Brighi, Marco Grilli, Sergio Caprara, Institute of Science and Technology [Austria] (IST Austria), Istituto Sistemi Complessi [ROME] (ISC), Consiglio Nazionale delle Ricerche [Roma] (CNR), Dipartimento di Fisica [Roma La Sapienza], Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Laboratoire de Physique et d'Etude des Matériaux (UMR 8213) (LPEM), Ecole Superieure de Physique et de Chimie Industrielles de la Ville de Paris (ESPCI Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Physique et d'Etude des Matériaux (LPEM), Centre National de la Recherche Scientifique (CNRS)-Ecole Superieure de Physique et de Chimie Industrielles de la Ville de Paris (ESPCI Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université Pierre et Marie Curie - Paris 6 (UPMC), Université Pierre et Marie Curie - Paris 6 (UPMC)-Ecole Superieure de Physique et de Chimie Industrielles de la Ville de Paris (ESPCI Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: disordered superconducting films, Anomalous diffusion, FOS: Physical sciences, 02 engineering and technology, 01 natural sciences, law.invention, Superconductivity (cond-mat.supr-con), Diffusion, anomalous diffusion, law, Condensed Matter::Superconductivity, 0103 physical sciences, 010306 general physics, Scanning tunneling microscopy, ComputingMilieux_MISCELLANEOUS, Quantum tunnelling, Superconducting films, Physics, Superconductivity, Condensed matter physics, Condensed Matter - Superconductivity, 021001 nanoscience & nanotechnology, Niobium compounds, [PHYS.COND.CM-S]Physics [physics]/Condensed Matter [cond-mat]/Superconductivity [cond-mat.supr-con], Unpaired electron, Density of states, [PHYS.COND.CM-MS]Physics [physics]/Condensed Matter [cond-mat]/Materials Science [cond-mat.mtrl-sci], Scanning tunneling microscope, Cooper pair, [PHYS.COND.CM-SCE]Physics [physics]/Condensed Matter [cond-mat]/Strongly Correlated Electrons [cond-mat.str-el], 0210 nano-technology, Pseudogap
Abstract: Recent scanning tunnelling microscopy experiments in NbN thin disordered superconducting films found an emergent inhomogeneity at the scale of tens of nanometers. This inhomogeneity is mirrored by an apparent dimensional crossover in the paraconductivity measured in transport above the superconducting critical temperature $T_c$. This behavior was interpreted in terms of an anomalous diffusion of fluctuating Cooper pairs, that display a {\em quasi-confinement} (i.e., a slowing down of their diffusive dynamics) on length scales shorter than the inhomogeneity identified by tunnelling experiments. Here we assume this anomalous diffusive behavior of fluctuating Cooper pairs and calculate the effect of these fluctuations on the electron density of states above $T_c$. We find that the density of states is substantially suppressed up to temperatures well above $T_c$. This behavior, which is closely reminiscent of a pseudogap, only arises from the anomalous diffusion of fluctuating Cooper pairs in the absence of stable preformed pairs, setting the stage for an intermediate behavior between the two common paradigms in the superconducting-insulator transition, namely the localisation of Cooper pairs (the so-called bosonic scenario) and the breaking of Cooper pairs into unpaired electrons due to strong disorder (the so-called fermionic scenario)., 6 pages 7 figures
Published: 2019

11. 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

12. Floating Wigner crystal with no boundary charge fluctuations

Author: Mathieu Lewin, Elliott H. Lieb, Robert Seiringer, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL), Centre National de la Recherche Scientifique (CNRS), Department of Physics, Princeton University, Institute of Science and Technology [Austria] (IST Austria), European Project: 725528,MDFT, European Project: 694227,H2020,ERC-2015-AdG,AQUAMS(2016), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
Subjects: Chemical Physics (physics.chem-ph), Physics, Strongly Correlated Electrons (cond-mat.str-el), Condensed matter physics, Jellium, [PHYS.MPHY]Physics [physics]/Mathematical Physics [math-ph], FOS: Physical sciences, Boundary (topology), Mathematical Physics (math-ph), 02 engineering and technology, Electron, 021001 nanoscience & nanotechnology, 01 natural sciences, Wigner crystal, Condensed Matter - Strongly Correlated Electrons, Physics - Chemical Physics, 0103 physical sciences, Periodic boundary conditions, Density functional theory, 010306 general physics, 0210 nano-technology, Ground state, Fermi gas, Mathematical Physics
Abstract: We modify the "floating crystal" trial state for the classical Homogeneous Electron Gas (also known as Jellium), in order to suppress the boundary charge fluctuations that are known to lead to a macroscopic increase of the energy. The argument is to melt a thin layer of the crystal close to the boundary and consequently replace it by an incompressible fluid. With the aid of this trial state we show that three different definitions of the ground state energy of Jellium coincide. In the first point of view the electrons are placed in a neutralizing uniform background. In the second definition there is no background but the electrons are submitted to the constraint that their density is constant, as is appropriate in Density Functional Theory. Finally, in the third system each electron interacts with a periodic image of itself, that is, periodic boundary conditions are imposed on the interaction potential., Includes some final corrections. Version to appear in Phys. Rev. B
Published: 2019
Full Text: View/download PDF

13. 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

14. 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

15. 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

16. Risk Upper Bounds for General Ensemble Methods with an application to Multiclass Classification

Author: Liva Ralaivola, Emilie Morvant, Jean-Francis Roy, François Laviolette, Department of Computer Science and Software Engineering [Québec], Université Laval [Québec] (ULaval), 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), é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), ANR-15-CE23-0026,LIVES,Apprendre avec des vues interactionnelles(2015), Lampert Group, Institute of Science and Technology [Austria] (IST Austria), éQuipe d'AppRentissage de MArseille (QARMA), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Weighted majority vote, PAC-Bayesian Theory, Majority rule, Cognitive Neuroscience, Binary number, 02 engineering and technology, 010501 environmental sciences, Machine learning, computer.software_genre, 01 natural sciences, Upper and lower bounds, Multiclass Classification, Multiclass classification, Majority vote, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Artificial Intelligence, Multilabel Prediction, 0202 electrical engineering, electronic engineering, information engineering, Ensemble Methods, 0105 earth and related environmental sciences, Mathematics, business.industry, 16. Peace & justice, Ensemble learning, Computer Science Applications, ComputingMethodologies_PATTERNRECOGNITION, Binary classification, 020201 artificial intelligence & image processing, Artificial intelligence, business, Classifier (UML), Algorithm, computer
Abstract: Published version: http://www.sciencedirect.com/science/article/pii/S0925231216310177; International audience; This paper generalizes a pivotal result from the PAC-Bayesian literature ---the C-bound--- primarily designed for binary classification to the general case of ensemble methods of voters with arbitrary outputs. We provide a generic version of the C-bound, an upper bound over the risk of models expressed as a weighted majority vote that is based on the first and second statistical moments of the vote's margin. On the one hand, this bound may advantageously be applied on more complex outputs than mere binary outputs, such as multiclass labels and multilabel, and on the other hand, it allows us to consider margin relaxations. We provide a specialization of the bound to multiclass classification together with empirical evidence that the presented theoretical result is tightly bound to the risk of the majority vote classifier. We also give insights as to how the proposed bound may be of use to characterize the risk of multilabel predictors.
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. Constrained PRFs for Unbounded Inputs with Short Keys

Author: Georg Fuchsbauer, Hamza Abusalah, Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), 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 [Austria] (IST Austria), 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), 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: Combinatorics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0102 computer and information sciences, 02 engineering and technology, Function (mathematics), 01 natural sciences, Algorithm, Mathematics
Abstract: International audience; A constrained pseudorandom function (CPRF) F:K×X→Y for a family T of subsets of X is a function where for any key k∈K and set S∈T one can efficiently compute a short constrained key k_S, which allows to evaluate F(k,⋅) on all inputs x∈S, while the outputs on all inputs x∉S look random even given k_S.Abusalah et al. recently constructed the first constrained PRF for inputs of arbitrary length whose sets S are decided by Turing machines. They use their CPRF to build broadcast encryption and the first ID-based non-interactive key exchange for an unbounded number of users. Their constrained keys are obfuscated circuits and are therefore large.In this work we drastically reduce the key size and define a constrained key for a Turing machine M as a short signature on M. For this, we introduce a new signature primitive with constrained signing keys that let one only sign certain messages, while forging a signature on others is hard even when knowing the coins for key generation.
Published: 2016

19. 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

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. 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

22. 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

23. 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

24. Perfect-Information Stochastic Mean-Payoff Parity Games

Author: Krishnendu Chatterjee, Hugo Gimbert, Laurent Doyen, Youssouf Oualhadj, 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), Institut de Mathématiques [Mons], and Université de Mons (UMons)
Subjects: Computer Science::Computer Science and Game Theory, 005 Computer programming, programs & data, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Stochastic process, Stochastic game, Perfect information, ComputingMilieux_PERSONALCOMPUTING, Mean payoff, Functional requirement, 0102 computer and information sciences, 02 engineering and technology, 000 Computer science, knowledge & systems, 01 natural sciences, Combinatorics, 510 Mathematics, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Markov decision process, Special case, 000 Computer science, knowledge general works, Reactive system, Mathematics
Abstract: International audience; The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2-1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2-1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running in time O(d * n^{2d}*MeanGame) to compute the set of almost-sure winning states from which the objective can be ensured with probability 1, where n is the number of states of the game, d the number of priorities of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states in 2-1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective).
Published: 2014

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. Learning A Priori Constrained Weighted Majority Votes

Author: Emilie Morvant, Aurélien Bellet, Amaury Habrard, Marc Sebban, University of Southern California (USC), Laboratoire Hubert Curien (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), ANR-13-BS02-0001,CompA,Complexité algébrique(2013), European Project: 308036,EC:FP7:ERC,ERC-2012-StG_20111012,L3VISU(2013), 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), Institute of Science and Technology [Austria] (IST Austria), and Similarity of locally structured data in computer vision, SoLSTiCe, ANR-13-BS02-01,Similarity of locally structured data in computer vision, SoLSTiCe, ANR-13-BS02-01
Subjects: 0102 computer and information sciences, 02 engineering and technology, Machine learning, computer.software_genre, Mathematical proof, 01 natural sciences, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Artificial Intelligence, Ensemble learning, Sample compression, 0202 electrical engineering, electronic engineering, information engineering, Mathematics, Randomized weighted majority algorithm, Weighted Majority Algorithm, PAC-Bayesian bounds, business.industry, Weighted majority vote, 010201 computation theory & mathematics, A priori and a posteriori, 020201 artificial intelligence & image processing, Artificial intelligence, Minification, business, Nearest neighbors, computer, Classifier (UML), Software, Large margin nearest neighbor
Abstract: The published version is available here: http://link.springer.com/article/10.1007/s10994-014-5462-z; International audience; Weighted majority votes allow one to combine the output of several classifiers or voters. MinCq is a recent algorithm for optimizing the weight of each voter based on the minimization of a theoretical bound over the risk of the vote with elegant PAC-Bayesian generalization guarantees. However, while it has demonstrated good performance when combining weak classifiers, MinCq cannot make use of the useful a priori knowledge that one may have when using a mixture of weak and strong voters. In this paper, we propose P-MinCq, an extension of MinCq that can incorporate such knowledge in the form of a constraint over the distribution of the weights, along with general proofs of convergence that stand in the sample compression setting for data-dependent voters. The approach is applied to a vote of k-NN classifiers with a specific modeling of the voters' performance. P-MinCq significantly outperforms the classic k-NN classifier, a symmetric NN and MinCq using the same voters. We show that it is also competitive with LMNN, a popular metric learning algorithm, and that combining both approaches further reduces the error.
Published: 2014

27. 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

28. Hennessy-Milner Logic with Greatest Fixed Points as a Complete Behavioural Specification Theory

Author: Uli Fahrenberg, Axel Legay, Nikola Beneš, Jan Křetínský, Benoît Delahaye, Masaryk University [Brno] (MUNI), AELOS, Laboratoire d'Informatique de Nantes Atlantique (LINA), 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), 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), 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), Pedro R. D’Argenio, Hernán Melgratti, 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), 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), and Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria)
Subjects: Model checking, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Normal modal logic, Modal logic, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, Fixed point, 01 natural sciences, Rotation formalisms in three dimensions, Linear logic, Logic in Computer Science (cs.LO), Algebra, Modal, 010201 computation theory & mathematics, Computer Science::Logic in Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Hennessy–Milner logic, [INFO]Computer Science [cs], Algorithm, Mathematics
Abstract: International audience; There are two fundamentally different approaches to specifying and verifying properties of systems. The logical approach makes use of specifications given as formulae of temporal or modal logics and relies on efficient model checking algorithms; the behavioural approach exploits various equivalence or refinement checking methods, provided the specifications are given in the same formalism as implementations. In this paper we provide translations between the logical formalism of Hennessy-Milner logic with greatest fixed points and the behavioural formalism of disjunctive modal transition systems. We also introduce a new operation of quotient for the above equivalent formalisms, which is adjoint to structural composition and allows synthesis of missing specifications from partial implementations. This is a substantial generalisation of the quotient for deterministic modal transition systems defined in earlier papers.
Published: 2013

29. 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

30. Contracts for System Design

Author: Kim G. Larsen, Thomas A. Henzinger, Werner Damm, Alberto Sangiovanni-Vincentelli, Philipp Reinkemeier, Jean-Baptiste Raclet, Roberto Passerone, Dejan Nickovic, Benoît Caillaud, Albert Benveniste, System synthesis and supervision, scenarios (S4), 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)-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Austrian Institute of Technology [Vienna] (AIT), Department of Information Engineering and Computer Science (DISI), University of Trento [Trento], Assistance à la Certification d’Applications DIstribuées et Embarquées (IRIT-ACADIE), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institute for Information Technology [Oldenburg] (OFFIS), Department of Electrical Engineering and Computer Science [Berkeley] (EECS), University of California [Berkeley] (UC Berkeley), University of California (UC)-University of California (UC), Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Aalborg University [Denmark] (AAU), iCyPhy program sponsored by IBM and United Technology Corporation, VKR Center of Excellence MT-LAB, German Innovation Alliance on Embedded Systems SPES2020, INRIA, European Project: 214373,ICT,FP7-ICT-2007-1,ARTISTDESIGN(2007), Modélisation hybride & conception par contrats pour les systèmes embarqués multi-physiques (HYCOMES), 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), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-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)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Department of Electrical Engineering and Computer Sciences (Berkeley EECS), Department für Informatik [Oldenburg], Carl Von Ossietzky Universität Oldenburg, Institute of Science and Technology [Austria] (IST Austria), 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)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-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)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Carl Von Ossietzky Universität Oldenburg = Carl von Ossietzky University of Oldenburg (OFFIS), CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-Université de Rennes (UNIV-RENNES)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES), Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), University of California [Berkeley], University of California, Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-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 National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, AIT, and University of California-University of California
Subjects: system design, 0209 industrial biotechnology, Test, Interface Theories, Embedded systems, component based design, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 02 engineering and technology, Contract based design, 020901 industrial engineering & automation, SoftwareMica, Contract-based Design, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], ContBasedDesign, ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.1: Requirements/Specifications, System Level Design, Program Verification, Verification, ACM: D.: Software/D.3: PROGRAMMING LANGUAGES/D.3.1: Formal Definitions and Theory, 020207 software engineering, Computer Graphics and Computer-Aided Design, Formal semantics, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, 020202 computer hardware & architecture, Hardware and Architecture, interface, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, contract
Abstract: Systems design has become a key challenge and differentiating factor over the last decades for system companies. Aircrafts, trains, cars, plants, distributed telecommunication military or health care systems, and more, involve systems design as a critical step. Complexity has caused system design times and costs to go severely over budget so as to threaten the health of entire industrial sectors. Heuristic methods and standard practices do not seem to scale with complexity so that novel design methods and tools based on a strong theoretical foundation are sorely needed. Model-based design as well as other methodologies such as layered and compositional design have been used recently but a unified intellectual framework with a complete design flow supported by formal tools is still lacking albeit some attempts at this framework such as Platform-based Design have been successfully deployed. Recently an "orthogonal" approach has been proposed that can be applied to all methodologies proposed thus far to provide a rigorous scaffolding for verification, analysis and abstraction/refinement: contractbased design. Several results have been obtained in this domain but a unified treatment of the topic that can help in putting contract-based design in perspective is still missing. This paper intends to provide such treatment where contracts are precisely defined and characterized so that they can be used in design methodologies such as the ones mentioned above with no ambiguity. In addition, the paper provides an important link between interfaces and contracts to show similarities and correspondences. Examples of the use of contracts in design are provided as well as in depth analysis of existing literature.; Cet article fait le point sur le concept de contrat pour la conception de systèmes. Les contrats que nous proposons portent, non seulement sur des propriétés de typage de leurs interfaces, mais incluent une description abstraite de comportements. Nous proposons une méta-théorie, ou, si l'on veut, une théorie générique des contrats, qui permet le développement séparé de sous-systèmes. Nous montrons que cette méta-théorie se spécialise en l'une ou l'autre des théories connues.
Published: 2012

31. 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

32. 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

33. Partial-observation Stochastic games: How to win when belief fails

Author: Laurent Doyen, Krishnendu Chatterjee, Chatterjee Group, Institute of Science and Technology [Austria] (IST Austria), Laboratoire Spécification et Vérification [Cachan] (LSV), and École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Successor cardinal, FOS: Computer and information sciences, Computational complexity theory, General Computer Science, Logic, 0102 computer and information sciences, 02 engineering and technology, 000 Computer science, knowledge & systems, 01 natural sciences, Upper and lower bounds, Theoretical Computer Science, Positive and Almost-sure winning, Bayesian game, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 000 Computer science, knowledge & general works, Reachability, Computer Science - Computer Science and Game Theory, 0202 electrical engineering, electronic engineering, information engineering, Memory bounds, Equivalence (measure theory), Mathematics, Discrete mathematics, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], 005 Computer programming, programs & data, Stochastic process, Reachability and Buechi objectives, ComputingMilieux_PERSONALCOMPUTING, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Complexity, State (functional analysis), Computational Mathematics, 010201 computation theory & mathematics, Path (graph theory), Probability distribution, 020201 artificial intelligence & image processing, Partial-observation games, Mathematical economics, Stochastic games, Computer Science and Game Theory (cs.GT)
Abstract: In two-player finite-state stochastic games of partial observation on graphs, in every state of the graph, the players simultaneously choose an action, and their joint actions determine a probability distribution over the successor states. The game is played for infinitely many rounds and thus the players construct an infinite path in the graph. We consider reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1) or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and to the power of randomization available to the players. On the basis of information, the game can be one-sided with either ( a ) player 1, or ( b ) player 2 having partial observation (and the other player has perfect observation), or two-sided with ( c ) both players having partial observation. On the basis of randomization, ( a ) the players may not be allowed to use randomization (pure strategies), or ( b ) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or ( c ) they may use full randomization. Our main results for pure strategies are as follows: (1) For one-sided games with player 2 having perfect observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almost-sure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete and present symbolic algorithms that avoid the explicit exponential construction. (2) For one-sided games with player 1 having perfect observation we show that nonelementary memory is both necessary and sufficient for both almost-sure and positive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least nonelementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibit serious flaws in previous results of the literature: we show a nonelementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed.
Published: 2011

34. 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

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

37. Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions

Author: Christian Hanser, Georg Fuchsbauer, Chethan Kamath, Daniel Slamanig, 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), Graz University of Technology [Graz] (TU Graz), Institute of Science and Technology [Austria] (IST Austria), 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)-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: Scheme (programming language), Blindness, Bilinear interpolation, 0102 computer and information sciences, 02 engineering and technology, medicine.disease, 01 natural sciences, Inversion (discrete mathematics), Random oracle, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, Simple (abstract algebra), 0202 electrical engineering, electronic engineering, information engineering, medicine, Blind signature, 020201 artificial intelligence & image processing, Algorithm, computer, Mathematics, computer.programming_language, Standard model (cryptography)
Abstract: International audience; At Crypto'15 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model construction of efficient round-optimal blind signatures that does not require complexity leveraging. It is conceptually simple and builds on the primitive of structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme and hardness of a version of the DH inversion problem. Blindness under adversarially chosen keys is proven under an interactive variant of the DDH assumption.We propose a variant of their scheme whose blindness can be proven under a non-interactive assumption, namely a variant of the bilinear DDH assumption. We moreover prove its unforgeability assuming only unforgeability of the underlying SPS-EQ but no additional assumptions as needed for the FHS scheme.
Full Text: View/download PDF

38. Offline Witness Encryption

Author: Georg Fuchsbauer, Hamza Abusalah, Krzysztof Pietrzak, 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 - 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)-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), É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, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), 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: Theoretical computer science, 005 Computer programming, programs & data, business.industry, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, Encryption, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Multiple encryption, 010201 computation theory & mathematics, Probabilistic encryption, 600 Technology, Ciphertext, 0202 electrical engineering, electronic engineering, information engineering, 40-bit encryption, 020201 artificial intelligence & image processing, Attribute-based encryption, Link encryption, On-the-fly encryption, business, computer, Mathematics
Abstract: International audience; Witness encryption (WE) was introduced by Garg et al. (STOC'13). A WE scheme is defined for some NP language L and lets a sender encrypt messages relative to instances x. A ciphertext for x can be decrypted using w witnessing x∈L, but hides the message if x∉L. Garg et al. construct WE from multilinear maps and give another construction (FOCS'13) using indistinguishability obfuscation (iO) for encryption. Due to the reliance on such heavy tools, WE can currently hardly be implemented on powerful hardware and will unlikely be realizable on constrained devices like smart cards any time soon.We construct a WE scheme where encryption is done by simply computing a Naor-Yung ciphertext (two CPA encryptions and a NIZK proof). To achieve this, our scheme has a setup phase, which outputs public parameters containing an obfuscated circuit (only required for decryption), two encryption keys and a common reference string (used for encryption). This setup need only be run once, and the parameters can be used for arbitrary many encryptions. Our scheme can also be turned into a functional WE scheme, where a message is encrypted w.r.t. a statement and a function f, and decryption with a witness w yields f(m,w).Our construction is inspired by the functional encryption scheme by Garg et al. and we prove (selective) security assuming iO and statistically simulation-sound NIZK. We give a construction of the latter in bilinear groups and combining it with ElGamal encryption, our ciphertexts are of size 1.3 kB at a 128-bit security level and can be computed on a smart card.
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

Database

Publisher

38 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