Search

Your search keyword '"École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France"' showing total 2,289 results
Start Over Author "École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France"
2,289 results on '"École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France"'

1. On the design of optimal health insurance contracts under ex post moral hazard

Author

Pierre Picard, Anasuya Raj, Pierre Martinon, Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems ( Commands ), Centre de Mathématiques Appliquées - Ecole Polytechnique ( CMAP ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Unité de Mathématiques Appliquées ( UMA ), École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech ) -École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech ), Département d'Économie de l'École Polytechnique, École polytechnique ( X ), Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems (Commands), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Département d'Économie de l'École Polytechnique (X-DEP-ECO), and École polytechnique (X)

Subjects
Economics and Econometrics, JEL : D - Microeconomics/D.D8 - Information, Knowledge, and Uncertainty/D.D8.D86 - Economics of Contract: Theory, Moral hazard, audit, 02 engineering and technology, Audit, Deductible, Morale hazard, JEL: C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling/C.C6.C63 - Computational Techniques • Simulation Modeling, optimal control, JEL: C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling/C.C6.C61 - Optimization Techniques • Programming Models • Dynamic Analysis, Accounting, JEL : D - Microeconomics/D.D8 - Information, Knowledge, and Uncertainty/D.D8.D82 - Asymmetric and Private Information • Mechanism Design, 0502 economics and business, 0202 electrical engineering, electronic engineering, information engineering, [ SHS.ECO ] Humanities and Social Sciences/Economies and finances, JEL: I - Health, Education, and Welfare/I.I3 - Welfare, Well-Being, and Poverty, 050207 economics, Risk management, Actuarial science, Ex-ante, JEL: D - Microeconomics/D.D8 - Information, Knowledge, and Uncertainty/D.D8.D86 - Economics of Contract: Theory, background risk, Risk aversion, business.industry, 05 social sciences, JEL : I - Health, Education, and Welfare/I.I3 - Welfare, Well-Being, and Poverty, [SHS.ECO]Humanities and Social Sciences/Economics and Finance, JEL : C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling/C.C6.C63 - Computational Techniques • Simulation Modeling, Incentive compatibility, health insurance, JEL : C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling/C.C6.C61 - Optimization Techniques • Programming Models • Dynamic Analysis, Business, Management and Accounting (miscellaneous), 020201 artificial intelligence & image processing, business, JEL: D - Microeconomics/D.D8 - Information, Knowledge, and Uncertainty/D.D8.D82 - Asymmetric and Private Information • Mechanism Design, ex post moral hazard, Finance
Abstract

We analyze the design of optimal medical insurance under ex post moral hazard, i.e., when illness severity cannot be observed by insurers and policyholders decide on their health expenditures. We characterize the trade-o§ between ex ante risk sharing and ex post incentive compatibility, in an optimal revelation mechanism under hidden information and risk aversion. We establish that the optimal contract provides partial insurance at the margin, with a deductible when insurersi rates are a§ected by a positive loading, and that it may also include an upper limit on coverage. We show that the potential to audit the health state leads to an upper limit on out-of-pocket expenses.

Published
2018

2. Computing Generic Abstractions from Application Datasets

Author

Barret, Nelly, Manolescu, Ioana, Upadhyay, Prajna, Rich Data Analytics at Cloud Scale (CEDAR), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and ANR-20-CHIA-0015,SourcesSay,Analyse et Interconnexion Intelligente des Contenus Héterogènes dans des Arènes Numériques(2020)

Subjects
Data sumarization, Semi-structured data, [INFO]Computer Science [cs], Entity-Relationship schema
Abstract

International audience; Digital data plays a central role in sciences, journalism, environment, digital humanities, etc. Open Data sharing initiatives lead to many large, interesting datasets being shared online. Some of these are RDF graphs, but other formats like CSV, relational, property graphs, JSON or XML documents are also frequent.Practitioners need to understand a dataset to decide whether it is suited to their needs. Datasets may come with a schema and/or may be summarized, however the first is not always provided and the latter is often too technical for non-IT users. To overcome these limitations, we present an end-to-end dataset abstraction approach, which (i) applies on any (semi)structured data model; (ii) computes a description meant for human users, in the form of an Entity- Relationship diagram; (ii) integrates Information Extraction and data profiling to classify dataset entities among a large set of intelligible categories. We implemented our approach in a system called Abstra, and detail its performance on various datasets.

Published
2024

3. WSDesc: Weakly Supervised 3D Local Descriptor Learning for Point Cloud Registration

Author

Lei Li, Hongbo Fu, Maks Ovsjanikov, La Géometrie au Service du Numérique (GEOMERIX), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Polytechnique de Paris (IP Paris), City University of Hong Kong [Hong Kong] (CUHK), the ANR AI Chair AIGRETTE, and European Project: 758800,ERC,ERC-2017-StG-758800,EXPROTEA(2018)

Subjects
FOS: Computer and information sciences, Computer Vision and Pattern Recognition (cs.CV), Computer Science - Computer Vision and Pattern Recognition, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], Computer Graphics and Computer-Aided Design, Graphics (cs.GR), [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], weak supervision, Point cloud, 3D CNN, Computer Science - Graphics, differentiable voxelization, Signal Processing, geometric registration, Computer Vision and Pattern Recognition, 3D local descriptor, Software
Abstract

In this work, we present a novel method called WSDesc to learn 3D local descriptors in a weakly supervised manner for robust point cloud registration. Our work builds upon recent 3D CNN-based descriptor extractors, which leverage a voxel-based representation to parameterize local geometry of 3D points. Instead of using a predefined fixed-size local support in voxelization, we propose to learn the optimal support in a data-driven manner. To this end, we design a novel differentiable voxelization layer that can back-propagate the gradient to the support size optimization. To train the extracted descriptors, we propose a novel registration loss based on the deviation from rigidity of 3D transformations, and the loss is weakly supervised by the prior knowledge that the input point clouds have partial overlap, without requiring ground-truth alignment information. Through extensive experiments, we show that our learned descriptors yield superior performance on existing geometric registration benchmarks., Comment: To appear in IEEE TVCG

Published
2023

4. Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria

Author

Marianne Akian, Stéphane Gaubert, Yang Qi, Omar Saadi, TROPICAL (TROPICAL), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
FOS: Computer and information sciences, Computer Science::Computer Science and Game Theory, Optimization and Control (math.OC), Computer Science - Computer Science and Game Theory, General Mathematics, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], MSC Primary 06F20, 14T10, 15A80, 16Y20, 16Y60, Secondary 20N20, 15A24, Mathematics - Optimization and Control, Physics::Atmospheric and Oceanic Physics, Computer Science and Game Theory (cs.GT)
Abstract

We study a tropical linear regression problem consisting in finding the best approximation of a set of points by a tropical hyperplane. We establish a strong duality theorem, showing that the value of this problem coincides with the maximal radius of a Hilbert's ball included in a tropical polyhedron. We also show that this regression problem is polynomial-time equivalent to mean payoff games. We illustrate our results by solving an inverse problem from auction theory. In this setting, a tropical hyperplane represents the set of equilibrium prices. Tropical linear regression allows us to quantify the distance of a market to the set of equilibria, and infer secret preferences of a decision maker.

Published
2023

5. Optimal Battery Aging : an Adaptive Weights Dynamic Programming Algorithm

Author

Benjamin Heymann, Pierre Martinon, Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems (Commands), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems ( Commands ), Centre de Mathématiques Appliquées - Ecole Polytechnique ( CMAP ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Unité de Mathématiques Appliquées ( UMA ), and École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech ) -École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech )

Subjects
Battery (electricity), [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], 0209 industrial biotechnology, Mathematical optimization, Aging, Control and Optimization, Applied Mathematics, Dynamic Programing, 02 engineering and technology, Management Science and Operations Research, 021001 nanoscience & nanotechnology, Energy management system, Dynamic programming, 020901 industrial engineering & automation, Energy Management System, Component (UML), Theory of computation, Control, Microgrid, Relaxation (approximation), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0210 nano-technology, Implementation, Mathematics
Abstract

International audience; We present an algorithm to handle the optimization over a long horizon of an electricmicrogrid including a battery energy storage system. While the battery is an important andcostly component of the microgrid, its aging process is often not taken into account by theEnergy Management System, mostly because of modeling and computing challenges. We addressthe computing aspect by a new approach combining dynamic programming, decomposition andrelaxation techniques. We illustrate this ’adaptive weight’ method with numerical simulationsfor a toy microgrid model. Compared to a straightforward resolution by dynamic programming,our algorithm decreases the computing time by more than one order of magnitude, can beparallelized, and allows for online implementations. We believe that this approach can be usedfor other applications presenting fast and slow variables.

Published
2018

6. Sensing Von Economo Neurons in the Insula with Multi-shell Diffusion MRI

Author

Wassermann, Demian, Nguyen, Dang Van, Gallardo, Guillermo, Li, Jing-Rebecca, Cai, Weidong, Menon, Vinod, Modelling brain structure, function and variability based on high-field MRI data (PARIETAL), Service NEUROSPIN (NEUROSPIN), Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Computational Imaging of the Central Nervous System (ATHENA), Inria Sophia Antipolis - Méditerranée (CRISAM), Royal Institute of Technology [Stockholm] (KTH ), Shape reconstruction and identification (DeFI ), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Stanford School of Medicine [Stanford], Stanford Medicine, Stanford University-Stanford University, LargeBrainNets, LargeSmallBrainNets, European Project: 757672,H2020 Pilier ERC,NeuroLang(2018), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Service NEUROSPIN (NEUROSPIN), Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Modelling brain structure, function and variability based on high-field MRI data ( PARIETAL ), Service NEUROSPIN ( NEUROSPIN ), Direction de Recherche Fondamentale (CEA) ( DRF (CEA) ), Commissariat à l'énergie atomique et aux énergies alternatives ( CEA ) -Université Paris-Saclay-Commissariat à l'énergie atomique et aux énergies alternatives ( CEA ) -Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) ( DRF (CEA) ), Commissariat à l'énergie atomique et aux énergies alternatives ( CEA ) -Université Paris-Saclay-Commissariat à l'énergie atomique et aux énergies alternatives ( CEA ) -Université Paris-Saclay-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Computational Imaging of the Central Nervous System ( ATHENA ), Inria Sophia Antipolis - Méditerranée ( CRISAM ), Royal Institute of Technology in Stockholm, Shape reconstruction and identification ( DeFI ), Centre de Mathématiques Appliquées - Ecole Polytechnique ( CMAP ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Saclay - Ile de France, Stanford University School of Medicine [Stanford], Stanford University [Stanford], and European Project : 757672,NeuroLang

Subjects
[ PHYS.PHYS.PHYS-BIO-PH ] Physics [physics]/Physics [physics]/Biological Physics [physics.bio-ph], [PHYS.PHYS.PHYS-BIO-PH]Physics [physics]/Physics [physics]/Biological Physics [physics.bio-ph], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2018

7. Sufficient optimality conditions for bilinear optimal control of the linear damped wave equation

Author

Bethke , Franz, Kröner , Axel, Humboldt-Universität zu Berlin, Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems (Commands), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Humboldt Universität Berlin, Humboldt University Of Berlin, Humboldt Universität zu Berlin, Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems ( Commands ), Centre de Mathématiques Appliquées - Ecole Polytechnique ( CMAP ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Unité de Mathématiques Appliquées ( UMA ), and École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech ) -École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech )

Subjects
[ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract

In this paper we discuss sufficient optimality conditions for an optimal control problem for the linear damped wave equation with the damping parameter as the control. We address the case that the control enters quadratic in the cost function as well as the singular case that the control enters affine. For the non-singular case we consider strong and weak local minima , in the singular case we derive sufficient optimality conditions for weak local minima. Thereby, we take advantage of the Goh transformation applying techniques recently established in Aronna, Bonnans, and Kröner [Math. Program. 168(1):717–757, 2018] and [INRIA research report, 2017]. Moreover, a numerical example for the singular case is presented.

Published
2018

8. A Lagrangian Approach for Aggregative Mean Field Games of Controls with Mixed and Final Constraints

Author

J. Frédéric Bonnans, Justina Gianatti, Laurent Pfeiffer, Controle, Optimisation, modèles, Méthodes et Applications pour les Systèmes Dynamiques non linéaires (COMMANDS), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Universidad Nacional de Rosario [Santa Fe], Centro Franco Argentino de Ciencias de la Información y de Sistemas [Rosario] (CIFASIS), Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires] (CONICET)-Universidad Nacional de Rosario [Santa Fe], Dynamical Interconnected Systems in COmplex Environments (DISCO), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire des signaux et systèmes (L2S), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), and Universidad Nacional de Rosario [Santa Fe]-Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires] (CONICET)

Subjects
Computer Science::Computer Science and Game Theory, aggregative games, Control and Optimization, Optimization and Control (math.OC), Applied Mathematics, Lagrangian equilibria, FOS: Mathematics, TheoryofComputation_GENERAL, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], constrained optimal control, Mathematics - Optimization and Control, Mean field games of controls
Abstract

The objective of this paper is to analyze the existence of equilibria for a class of deterministic mean field games of controls. The interaction between players is due to both a congestion term and a price function which depends on the distributions of the optimal strategies. Moreover, final state and mixed state-control constraints are considered, the dynamics being nonlinear and affine with respect to the control. The existence of equilibria is obtained by Kakutani's theorem, applied to a fixed point formulation of the problem. Finally, uniqueness results are shown under monotonicity assumptions.

Published
2023

9. Exploring heterogeneous data graphs through their entity paths

Author

Barret, Nelly, Gauquier, Antoine, Law, Jia-Jean, Manolescu, Ioana, Rich Data Analytics at Cloud Scale (CEDAR), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut Mines-Télécom [Paris] (IMT), École polytechnique (X), and ANR-20-CHIA-0015,SourcesSay,Analyse et Interconnexion Intelligente des Contenus Héterogènes dans des Arènes Numériques(2020)

Subjects
Graph exploration, [INFO]Computer Science [cs], Information Extraction, Data graphs
Abstract

International audience; Graphs, and notably RDF graphs, are a prominent way of sharing data. As data usage democratizes, users need help figuring out the useful content of a graph dataset. In particular, journalists with whom we collaborate are interested in identifying, in a graph, the connections between entities, e.g., people, organizations, emails, etc.We present a novel, interactive method for exploring data graphs through their data paths connecting Named Entities (NEs, in short); each data path leads to a tabular-looking set of results. NEs are extracted from the data through dedicated Information Extraction modules. Our method builds upon the pre-existing ConnectionLens platform and follow-up work on dataset abstraction. The contribution of the present work is in the interactive and efficient approach to enumerate and compute NE paths, based on an algorithm which automatically recommends subpaths to materialize, and rewrites the path queries using these subpaths. Our experiments demonstrate the interest of NE paths and the efficiency of our method for computing them.

Published
2023

10. The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems

Author

Akian, Marianne, Béreau, Antoine, Gaubert, Stéphane, TROPICAL (TROPICAL), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Tropical geometry, [MATH]Mathematics [math], Zero-sum games, Algorithmic complexity, Polynomial systems
Abstract

International audience

Published
2023

11. Evaluation of the impact of various modifications to CMA-ES that facilitate its theoretical analysis

Author

Gissler, Armand, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Randomized Optimisation (RANDOPT ), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Benchmarking, Black-box optimization, [MATH]Mathematics [math]
Abstract

International audience; In this paper we introduce modified versions of CMA-ES with the objective to help to prove convergence of CMA-ES. In order to ensure that the modifications do not alter the performances of the algorithm too much, we benchmark variants of the algorithm derived from them on problems of the bbob test suite. We observe that the main performances losses are observed on ill-conditioned problems, which is probably due to the absence of cumulation in the adaptation of the covariance matrix. However, the versions of CMA-ES presented in this paper have globally similar performances to the original CMA-ES.

Published
2023

12. Multiobjective optimization with a quadratic surrogate-assisted CMA-ES

Author

Gharafi, Mohamed, Hansen, Nikolaus, Brockhoff, Dimo, Le Riche, Rodolphe, Randomized Optimisation (RANDOPT ), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE), Centre National de la Recherche Scientifique (CNRS), GECCO, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Université Clermont Auvergne [2017-2020] (UCA [2017-2020])

Subjects
multiobjective optimization CMA-ES evolution strategies surrogateassisted optimization quadratic metamodel, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], evolution strategies, multiobjective optimization, surrogateassisted optimization, CMA-ES, quadratic metamodel, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE]
Abstract

International audience; We present a surrogate-assisted multiobjective optimization algorithm. The aggregation of the objectives relies on the Uncrowded Hypervolume Improvement (UHVI) which is partly replaced by a linear-quadratic surrogate that is integrated into the CMA-ES algorithm. Surrogating the UHVI poses two challenges. First, the UHVI is a dynamic function, changing with the empirical Pareto set. Second, it is a composite function, defined differently for dominated and nondominated points. The presented algorithm is thought to be used with expensive functions of moderate dimension (up to about 50) with a quadratic surrogate which is updated based on its ranking ability. We report numerical experiments which include tests on the COCO benchmark. The algorithm shows in particular linear convergence on the double sphere function with a convergence rate that is 6-20 times faster than without surrogate assistance.

Published
2023

13. Efficient Utility Improvement for Location Privacy

Author

Konstantinos Chatzikokolakis, Catuscia Palamidessi, Ehab ElSalamouny, Concurrency, Mobility and Transactions (COMETE), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Microsoft Research - Inria Joint Centre (MSR - INRIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Microsoft Research Laboratory Cambridge-Microsoft Corporation [Redmond, Wash.], ANR-16-CE25-0011,REPAS,Des systèmes logiciels fiables et conscients des données privées, via les métriques de bisimulation(2016), Concurrency, Mobility and Transactions ( COMETE ), Laboratoire d'informatique de l'École polytechnique [Palaiseau] ( LIX ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Microsoft Research - Inria Joint Centre ( MSR - INRIA ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Microsoft Research Laboratory Cambridge-Microsoft Corporation [Redmond, Wash.], Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
optimal mechanism, Linear programming, Computer science, remap, Distributed computing, Bayesian probability, Optimal mechanism, location privacy, [ INFO.INFO-CR ] Computer Science [cs]/Cryptography and Security [cs.CR], 02 engineering and technology, computer.software_genre, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 0202 electrical engineering, electronic engineering, information engineering, planar laplace, geo-indistinguishability, General Environmental Science, Ethics, business.industry, Information technology, 020206 networking & telecommunications, QA75.5-76.95, BJ1-1725, Laplace distribution, Obfuscation (software), Electronic computers. Computer science, Key (cryptography), General Earth and Planetary Sciences, 020201 artificial intelligence & image processing, Noise (video), Data mining, business, computer
Abstract

The continuously increasing use of location-based services poses an important threat to the privacy of users. A natural defense is to employ an obfuscation mechanism, such as those providing geo-indistinguishability, a framework for obtaining formal privacy guarantees that has become popular in recent years. Ideally, one would like to employ an optimal obfuscation mechanism, providing the best utility among those satisfying the required privacy level. In theory optimal mechanisms can be constructed via linear programming. In practice, however, this is only feasible for a radically small number of locations. As a consequence, all known applications of geo-indistinguishability simply use noise drawn from a planar Laplace distribution. In this work, we study methods for substantially improving the utility of location obfuscation, while maintaining practical applicability as a main goal. We provide such solutions for both infinite (continuous or discrete) as well as large but finite domains of locations, using a Bayesian remapping procedure as a key ingredient. We evaluate our techniques in two real world complete datasets, without any restriction on the evaluation area, and show important utility improvements with respect to the standard planar Laplace approach.

Published
2017

14. Anytime Performance Assessment in Blackbox Optimization Benchmarking

Author

Nikolaus Hansen, Anne Auger, Dimo Brockhoff, Tea Tusar, Randomized Optimisation (RANDOPT ), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Jozef Stefan Institute [Ljubljana] (IJS), Slovenian Research Agency Grant P2-0209, Slovenian Research Agency Grant N2-0254, and ANR-12-MONU-0009,NumBBO,Analyse, Amelioration, Evaluation d'algorithmes numériques pour l'optimisation boîte-noire(2012)

Subjects
blackbox optimization, [INFO.INFO-CE]Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE], [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], Theoretical Computer Science, [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Computational Theory and Mathematics, anytime optimization, quality indicator, performance assessment, benchmarking, Software, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS]
Abstract

open access; International audience; We present concepts and recipes for the anytime performance assessment when benchmarking optimization algorithms in a blackbox scenario. We consider runtime-oftentimes measured in number of blackbox evaluations needed to reach a target quality-to be a universally measurable cost for solving a problem. Starting from the graph that depicts the solution quality versus runtime, we argue that runtime is the only performance measure with a generic, meaningful, and quantitative interpretation. Hence, our assessment is solely based on runtime measurements. We discuss proper choices for solution quality indicators in single-and multiobjective optimization, as well as in the presence of noise and constraints. We also discuss the choice of the target values, budget-based targets, and the aggregation of runtimes by using simulated restarts, averages, and empirical cumulative distributions which generalize convergence graphs of single runs. The presented performance assessment is to a large extent implemented in the comparing continuous optimizers (COCO) platform freely available at https://github.com/numbbo/coco.

Published
2022

15. On Rectangle-Decomposable 2-Parameter Persistence Modules

Author

Botnan, Magnus Bakke, Lebovici, Vadim, Oudot, Steve, Cabello, Sergio, Chen, Danny Z., Mathematics, Vrije Universiteit Amsterdam [Amsterdam] (VU), 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), Sergio Cabello, Danny Z. Chen, Schloss Dagstuhl--Leibniz-Zentrum für Informatik, La Géometrie au Service du Numérique (GEOMERIX), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Polytechnique de Paris (IP Paris), Cabello, Sergio, and Chen, Danny Z.

Subjects
Computational Geometry (cs.CG), FOS: Computer and information sciences, Topological data analysis, SDG 10 - Reduced Inequalities, Multiparameter persistence, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Theoretical Computer Science, Computational Theory and Mathematics, [MATH.MATH-AT]Mathematics [math]/Algebraic Topology [math.AT], FOS: Mathematics, Computer Science - Computational Geometry, Discrete Mathematics and Combinatorics, Algebraic Topology (math.AT), Mathematics - Algebraic Topology, Geometry and Topology, rank invaria, Rank invariant
Abstract

This paper addresses two questions: (a) can we identify a sensible class of 2-parameter persistence modules on which the rank invariant is complete? (b) can we determine efficiently whether a given 2-parameter persistence module belongs to this class? We provide positive answers to both questions, and our class of interest is that of rectangle-decomposable modules. Our contributions include: on the one hand, a proof that the rank invariant is complete on rectangle-decomposable modules, together with an inclusion-exclusion formula for counting the multiplicities of the summands; on the other hand, algorithms to check whether a module induced in homology by a bifiltration is rectangle-decomposable, and to decompose it in the affirmative, with a better complexity than state-of-the-art decomposition methods for general 2-parameter persistence modules. Our algorithms are backed up by a new structure theorem, whereby a 2-parameter persistence module is rectangle-decomposable if, and only if, its restrictions to squares are. This local characterization is key to the efficiency of our algorithms, and it generalizes previous conditions derived for the smaller class of block-decomposable modules. It also admits an algebraic formulation that turns out to be a weaker version of the one for block-decomposability. By contrast, we show that general interval-decomposability does not admit such a local characterization, even when locality is understood in a broad sense. Our analysis focuses on the case of modules indexed over finite grids, the more general cases are left as future work., Comment: This is the final version to be published in DCG. Changed the algorithm in Section 3 for computing the rank invariant, which was incorrect. The new algorithm reduces to computing 1-parameter vineyards along a family of paths in the grid. It was first proposed in the PhD thesis of D. Morozov

Published
2022

16. Interior point methods are not worse than Simplex

Author

Xavier Allamigeon, Daniel Dadush, Georg Loho, Bento Natura, Laszlo A. Vegh, Mathematics of Operations Research, TROPICAL (TROPICAL), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centrum voor Wiskunde en Informatica (CWI), Centrum Wiskunde & Informatica (CWI)-Netherlands Organisation for Scientific Research, Faculty of Electrical Engineering, Mathematics and Computer Science [Twente] (EEMCS), University of Twente, Department Mathematics [London] (LSE), London School of Economics and Political Science (LSE), and Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Subjects
FOS: Computer and information sciences, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Geometry, Time measurement, Computer science, Current measurement, Partitioning algorithms, n/a OA procedure, Optimization and Control (math.OC), Linear programming, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Data Structures and Algorithms (cs.DS), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Upper bound
Abstract

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound $O(2^{n}n^{15}\log n)$ for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. The number of iterations of our algorithm is at most $O(n^{15}\log n)$ times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths. From the existence of a line segment in the wide neighborhood we derive strong implications on the structure of the corresponding segment of the central path. Our algorithm is able to detect this structure from the local geometry at the current iterate, and constructs a step direction that descends along this segment. The bound $O(n^{15}\log n)$ that applies for arbitrarily long line segments is derived from a combinatorial progress measure. Our algorithm falls into the family of layered least squares interior point methods introduced by Vavasis and Ye (Math. Prog. 1996). In contrast to previous layered least squares methods that partition the kernel of the constraint matrix into coordinate subspaces, our method creates layers based on a general subspace providing more flexibility. Our result also implies the same bound on the number of iterations of the trust region interior point method by Lan, Monteiro, and Tsuchiya (SIOPT 2009).

Published
2022

17. Nonatomic aggregative games with infinitely many types

Author

Paulin Jacquot, Cheng Wan, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), TROPICAL (TROPICAL), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Optimisation, Simulation, Risque et Statistiques pour les Marchés de l’Energie (EDF R&D OSIRIS), EDF R&D (EDF R&D), and EDF (EDF)-EDF (EDF)

Subjects
FOS: Computer and information sciences, TheoryofComputation_MISCELLANEOUS, Computer Science::Computer Science and Game Theory, Information Systems and Management, General Computer Science, media_common.quotation_subject, 0211 other engineering and technologies, Monotonic function, 02 engineering and technology, Management Science and Operations Research, generalized variational inequality, Industrial and Manufacturing Engineering, nonatomic aggregative game, Computer Science - Computer Science and Game Theory, 0502 economics and business, Convergence (routing), FOS: Mathematics, 050207 economics, Mathematics - Optimization and Control, Finite set, Parametric statistics, Mathematics, media_common, Sequence, 021103 operations research, 05 social sciences, ComputingMilieux_PERSONALCOMPUTING, TheoryofComputation_GENERAL, Coupling (probability), Infinity, Optimization and Control (math.OC), variational equilibrium, Modeling and Simulation, Variational inequality, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], coupling aggregative constraints, Mathematical economics, monotone game, Computer Science and Game Theory (cs.GT)
Abstract

We define and analyze the notion of variational Wardrop equilibrium for nonatomic aggregative games with an infinity of players types. These equilibria are characterized through an infinite-dimensional variational inequality. We show, under monotonicity conditions, a convergence theorem enables to approximate such an equilibrium with arbitrary precision. To this end, we introduce a sequence of nonatomic games with a finite number of players types, which approximates the initial game. We show the existence of a symmetric Wardrop equilibrium in each of these games. We prove that those symmetric equilibria converge to an equilibrium of the infinite game, and that they can be computed as solutions of finite-dimensional variational inequalities. The model is illustrated through an example from smart grids: the description of a large population of electricity consumers by a parametric distribution gives a nonatomic game with an infinity of different players types, with actions subject to coupling constraints., arXiv admin note: substantial text overlap with arXiv:1806.06230

Published
2022

18. The theory of call-by-value solvability

Author

Beniamino Accattoli, Giulio Guerrieri, Automatisation et ReprésenTation: fOndation du calcUl et de la déducTion (PARTOUT), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and University of Bath [Bath]

Subjects
call-by-value, intersection types, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Safety, Risk, Reliability and Quality, solvability, Software
Abstract

International audience; The semantics of the untyped (call-by-name) lambda-calculus is a well developed field built around the concept of solvable terms, which are elegantly characterized in many different ways. In particular, unsolvable terms provide a consistent notion of meaningless term. The semantics of the untyped call-by-value lambda-calculus (CbV) is instead still in its infancy, because of some inherent difficulties but also because CbV solvable terms are less studied and understood than in call-by-name. On the one hand, we show that a carefully crafted presentation of CbV allows us to recover many of the properties that solvability has in call-by-name, in particular qualitative and quantitative characterizations via multi types. On the other hand, we stress that, in CbV, solvability plays a different role: identifying unsolvable terms as meaningless induces an inconsistent theory.

Published
2022

19. Multi types and reasonable space

Author

Beniamino Accattoli, Ugo Dal Lago, Gabriele Vanoni, Accattoli, B, Dal Lago, U, Vanoni, G, Automatisation et ReprésenTation: fOndation du calcUl et de la déducTion (PARTOUT), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Foundations of Component-based Ubiquitous Systems (FOCUS), 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)-Dipartimento di Informatica - Scienza e Ingegneria [Bologna] (DISI), Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)-Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO), and University of Bologna/Università di Bologna

Subjects
lambda calculu, intersection type, intersection types, abstract machines, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], cost model, lambda calculus, cost models, Safety, Risk, Reliability and Quality, space complexity, Software, abstract machine
Abstract

International audience; Accattoli, Dal Lago, and Vanoni have recently proved that the space used by the Space KAM, a variant of the Krivine abstract machine, is a reasonable space cost model for the λ-calculus accounting for logarithmic space, solving a longstanding open problem. In this paper, we provide a new system of multi types (a variant of intersection types) and extract from multi type derivations the space used by the Space KAM, capturing into a type system the space complexity of the abstract machine. Additionally, we show how to capture also the time of the Space KAM, which is a reasonable time cost model, via minor changes to the type system.

Published
2022

20. A gapless code-based hash proof system based on RQC and its applications

Author

Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Yann Connan, Philippe Gaborit, Worldline France, Technology Innovation Institute (TII), Geometry, arithmetic, algorithms, codes and encryption (GRACE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), and Université de Limoges (UNILIM)

Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Applied Mathematics, Computer Science Applications
Abstract

International audience

Published
2022

21. Point‐Pattern Synthesis using Gabor and Random Filters

Author

Xingchang Huang, Pooran Memari, Hans‐Peter Seidel, Gurprit Singh, Max Planck Institute for Informatics [Saarbrücken], Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), La Géometrie au Service du Numérique (GEOMERIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Polytechnique de Paris (IP Paris), Max-Planck-Institut für Informatik (MPII), and Max-Planck-Gesellschaft

Subjects
Computer Graphics and Computer-Aided Design, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR]
Abstract

International audience; Point pattern synthesis requires capturing both local and non-local correlations from a given exemplar. Recent works employ deep hierarchical representations from VGG-19 [SZ15] convolutional network to capture the features for both point-pattern and texture synthesis. In this work, we develop a simplified optimization pipeline that uses more traditional Gabor transform-based features. These features when convolved with simple random filters gives highly expressive feature maps. The resulting framework requires significantly less feature maps compared to VGG-19-based methods [TLH19; RGF∗20], better captures both the local and non-local structures, does not require any specific data set training and can easily extend to handle multi-class and multi-attribute point patterns, e.g., disk and other element distributions. To validate our pipeline, we perform qualitative and quantitative analysis on a large variety of point patterns to demonstrate the effectiveness of our approach. Finally, to better understand the impact of random filters, we include a spectral analysis using filters with different frequency bandwidths.

Published
2022

22. Coqlex: Generating Formally Verified Lexers

Author

Ouedraogo, Wendlasida, Scherer, Gabriel, Strassburger, Lutz, Automatisation et ReprésenTation: fOndation du calcUl et de la déducTion (PARTOUT), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), INRIA Saclay - Ile-de-France, and OUEDRAOGO, Wendlasida

Subjects
FOS: Computer and information sciences, Computer Science - Programming Languages, [INFO] Computer Science [cs], Lexer, Tokenizer, Formal verification, Lexical analyzers, OCamllex, Compilers, Verbatim++, Regexp, Coq, [INFO]Computer Science [cs], Programming Languages (cs.PL)
Abstract

A compiler consists of a sequence of phases going from lexical analysis to code generation. Ideally, the formal verification of a compiler should include the formal verification of each component of the tool-chain. An example is the CompCert project, a formally verified C compiler, that comes with associated tools and proofs that allow to formally verify most of those components. However, some components, in particular the lexer, remain unverified. In fact, the lexer of Compcert is generated using OCamllex, a lex-like OCaml lexer generator that produces lexers from a set of regular expressions with associated semantic actions. Even though there exist various approaches, like CakeML or Verbatim++, to write verified lexers, they all have only limited practical applicability. In order to contribute to the end-to-end verification of compilers, we implemented a generator of verified lexers whose usage is similar to OCamllex. Our software, called Coqlex, reads a lexer specification and generates a lexer equipped with a Coq proof of its correctness. It provides a formally verified implementation of most features of standard, unverified lexer generators. The conclusions of our work are two-fold: Firstly, verified lexers gain to follow a user experience similar to lex/flex or OCamllex, with a domain-specific syntax to write lexers comfortably. This introduces a small gap between the written artifact and the verified lexer, but our design minimizes this gap and makes it practical to review the generated lexer. The user remains able to prove further properties of their lexer. Secondly, it is possible to combine simplicity and decent performance. Our implementation approach that uses Brzozowski derivatives is noticeably simpler than the previous work in Verbatim++ that tries to generate a deterministic finite automaton (DFA) ahead of time, and it is also noticeably faster thanks to careful design choices. We wrote several example lexers that suggest that the convenience of using Coqlex is close to that of standard verified generators, in particular, OCamllex. We used Coqlex in an industrial project to implement a verified lexer of Ada. This lexer is part of a tool to optimize safety-critical programs, some of which are very large. This experience confirmed that Coqlex is usable in practice, and in particular that its performance is good enough. Finally, we performed detailed performance comparisons between Coqlex, OCamllex, and Verbatim++. Verbatim++ is the state-of-the-art tool for verified lexers in Coq, and the performance of its lexer was carefully optimized in previous work by Egolf and al. (2022). Our results suggest that Coqlex is two orders of magnitude slower than OCamllex, but two orders of magnitude faster than Verbatim++. Verified compilers and other language-processing tools are becoming important tools for safety-critical or security-critical applications. They provide trust and replace more costly approaches to certification, such as manually reading the generated code. Verified lexers are a missing piece in several Coq-based verified compilers today. Coqlex comes with safety guarantees, and thus shows that it is possible to build formally verified front-ends.

Published
2023

23. Pairings in Rank-1 Constraint Systems

Author

El Housni, Youssef, Geometry, arithmetic, algorithms, codes and encryption (GRACE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and El Housni, Youssef

Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR]
Abstract

International audience; Bilinear pairings have been used in different cryptographic applications and demonstrated to be a key building block for a plethora of constructions. In particular, some Succinct Non-interactive ARguments of Knowledge (SNARKs) have very short proofs and very fast verification thanks to a multi-pairing computation. This succinctness makes pairing-based SNARKs suitable for proof recursion, that is proofs verifying other proofs. In this scenario one requires to express efficiently a multi-pairing computation as a SNARK arithmetic circuit. Other compelling applications such as verifying Boneh-Lynn-Shacham (BLS) signatures or Kate-Zaverucha-Goldberg (KZG) polynomial commitment opening in a SNARK fall into the same requirement. The implementation of pairings is challenging but the literature has very detailed approaches on how to reach practical and optimized implementations in different contexts and for different target environments. However, to the best of our knowledge, no previous publication has addressed the question of efficiently implementing a pairing as a SNARK arithmetic circuit. In this work, we consider efficiently implementing pairings in Rank-1 Constraint Systems (R1CS), a widely used model to express SNARK statements. We implement our techniques in the gnark open-source ecosystem and show that the arithmetic circuit depth can be almost halved compared to the previously best known pairing implementation on a Barreto-Lynn-Scott (BLS) curve of embedding degree 12, resulting in a significantly faster proving time. We also investigate and implement the case of BLS curves of embedding degree 24.

Published
2023

24. Stable Vectorization of Multiparameter Persistent Homology using Signed Barcodes as Measures

Author

Loiseaux, David, Scoccola, Luis, Carrière, Mathieu, Botnan, Magnus Bakke, Oudot, Steve, 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), Northeastern University [Boston], Vrije Universiteit Amsterdam [Amsterdam] (VU), La Géometrie au Service du Numérique (GEOMERIX), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Polytechnique de Paris (IP Paris), and ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019)

Subjects
Computational Geometry (cs.CG), FOS: Computer and information sciences, Computer Science - Machine Learning, Statistics - Machine Learning, [MATH.MATH-AT]Mathematics [math]/Algebraic Topology [math.AT], FOS: Mathematics, Algebraic Topology (math.AT), Computer Science - Computational Geometry, Machine Learning (stat.ML), [INFO]Computer Science [cs], Mathematics - Algebraic Topology, Machine Learning (cs.LG)
Abstract

Persistent homology (PH) provides topological descriptors for geometric data, such as weighted graphs, which are interpretable, stable to perturbations, and invariant under, e.g., relabeling. Most applications of PH focus on the one-parameter case -- where the descriptors summarize the changes in topology of data as it is filtered by a single quantity of interest -- and there is now a wide array of methods enabling the use of one-parameter PH descriptors in data science, which rely on the stable vectorization of these descriptors as elements of a Hilbert space. Although the multiparameter PH (MPH) of data that is filtered by several quantities of interest encodes much richer information than its one-parameter counterpart, the scarceness of stability results for MPH descriptors has so far limited the available options for the stable vectorization of MPH. In this paper, we aim to bring together the best of both worlds by showing how the interpretation of signed barcodes -- a recent family of MPH descriptors -- as signed measures leads to natural extensions of vectorization strategies from one parameter to multiple parameters. The resulting feature vectors are easy to define and to compute, and provably stable. While, as a proof of concept, we focus on simple choices of signed barcodes and vectorizations, we already see notable performance improvements when comparing our feature vectors to state-of-the-art topology-based methods on various types of data., 23 pages, 3 figures, 8 tables

Published
2023

25. Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields

Author

Banegas, Gustavo, Gilchrist, Valerie, Dévéhat, Anaëlle Le, Smith, Benjamin, Qualcomm France RFFE SARL (Qualcomm France ), Université libre de Bruxelles (ULB), Geometry, arithmetic, algorithms, codes and encryption (GRACE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-22-PETQ-0008,PQ-TLS,Post-quantum padlock for web browser(2022), and ANR-19-CE48-0008,CIAO,Cryptographie, isogenies et variété abéliennes surpuissantes(2019)

Subjects
FOS: Computer and information sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Computer Science - Cryptography and Security, elliptic curve cryptography, Cryptography and Security (cs.CR), post-quantum cryptography, isogeny
Abstract

Consider the problem of efficiently evaluating isogenies $\phi: E \to E/H$ of elliptic curves over a finite field $\mathbb{F}_q$, where the kernel $H = \langle G\rangle$ is a cyclic group of odd (prime) order: given $E$, $G$, and a point (or several points) $P$ on $E$, we want to compute $\phi(P)$. This problem is at the heart of efficient implementations of group-action- and isogeny-based post-quantum cryptosystems such as CSIDH. Algorithms based on V{\'e}lu's formulae give an efficient solution to this problem when the kernel generator $G$ is defined over $\mathbb{F}_q$. However, for general isogenies, $G$ is only defined over some extension $\mathbb{F}_{q^k}$, even though $\langle G\rangle$ as a whole (and thus $\phi$) is defined over the base field $\mathbb{F}_q$; and the performance of V{\'e}lu-style algorithms degrades rapidly as $k$ grows. In this article we revisit the isogeny-evaluation problem with a special focus on the case where $1 \le k \le 12$. We improve V{\'e}lu-style isogeny evaluation for many cases where $k = 1$ using special addition chains, and combine this with the action of Galois to give greater improvements when $k > 1$.

Published
2023

26. PathWays: entity-focused exploration of heterogeneous data graphs

Author

Barret, Nelly, Gauquier, Antoine, Law, Jia-Jean, Manolescu, Ioana, Rich Data Analytics at Cloud Scale (CEDAR), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut Mines-Télécom [Paris] (IMT), École polytechnique (X), DIM RFSI PHD 2020-01 (Domaine d'Interêt Majeur - Réseau Francilien en Sciences Informatiques), and ANR-20-CHIA-0015,SourcesSay,Analyse et Interconnexion Intelligente des Contenus Héterogènes dans des Arènes Numériques(2020)

Subjects
Graph exploration, [INFO]Computer Science [cs], Information Extraction, Data graphs
Abstract

International audience; Graphs, and notably RDF graphs, are a prominent way of sharing data. As data usage democratizes, users need help figuring out the useful content of a graph dataset. In particular, journalists with whom we collaborate [3] are interested in identifying, in a graph, the connections between entities, e.g., people, organizations, emails, etc. We propose PathWays, an interactive tool for exploring data graphs through their data paths connecting Named Entities (NEs, in short); each data path leads to a tabular-looking set of results. NEs are extracted from the data through dedicated Information Extraction modules. PathWays leverages the ConnectionLens platform [4,6] and follow-up work on dataset abstraction [5]. Its novelty lies in its interactive and efficient approach to enumerate, compute, and analyze NE paths.

Published
2023

27. More power to SPARQL: From paths to trees

Author

Anadiotis, Angelos, Manolescu, Ioana, Mohanty, Madhulika, Oracle Labs Switzerland, Rich Data Analytics at Cloud Scale (CEDAR), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and ANR-20-CHIA-0015,SourcesSay,Analyse et Interconnexion Intelligente des Contenus Héterogènes dans des Arènes Numériques(2020)

Subjects
Keyword Search, Exploratory Search, [INFO]Computer Science [cs], Graph Queries
Abstract

International audience; Exploring Knowledge Graphs (KGs, in short) to discover facts and links is tedious even for experts with knowledge of SPARQL due to their unfamiliarity with the structure and labels of entities, classes and relations. Some KG applications require finding the connections between groups of nodes, even if users ignore the shape of these connections. However, SPARQL only allows checking if paths exist, not returning them. A recent property graph query language, GPML, allows also returning connecting paths, but not connections between three or more nodes. We propose to demonstrate RelSearch, a system supporting extended SPARQL queries, featuring standard Basic Graph Patterns (BGPs) as well as novel Connecting Tree Patterns (CTPs); each CTP requests the connections (paths, or trees) between nodes bound to variables. RelSearch evaluates such extended queries using novel algorithms which, unlike prior keyword search methods, return connections regardless of the edge directions and are independent of how we measure the quality (score) of each connection. We will demonstrate RelSearch's expressivity and efficiency using a variety of RDF graphs, user-selected score functions, and search exploration orders.

Published
2023

28. Collaborative Ad Transparency: Promises and Limitations

Author

Gkiouzepi, Eleni, Andreou, Athanasios, Goga, Oana, Loiseau, Patrick, Technical University of Berlin / Technische Universität Berlin (TU), Algorithmic Transparency Institute (ATI), Rich Data Analytics at Cloud Scale (CEDAR), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), IA coopérative : équité, vie privée, incitations (FAIRPLAY), Centre de Recherche en Économie et Statistique (CREST), Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz] (ENSAI)-École polytechnique (X)-École Nationale de la Statistique et de l'Administration Économique (ENSAE Paris)-Centre National de la Recherche Scientifique (CNRS)-Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz] (ENSAI)-École polytechnique (X)-École Nationale de la Statistique et de l'Administration Économique (ENSAE Paris)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Polytechnique de Paris (IP Paris)-Criteo AI Lab, Criteo [Paris]-Criteo [Paris], ANR-17-CE23-0014,PRoTecT,Vie Privee et Confiance dans l'Internet Oriente Utilisateur(2017), ANR-21-CE23-0031,PROPEOS,Personnalisation de services en ligne respectueuse de la vie privée(2021), ANR-20-CE23-0007,FairPlay,Algorithmes équitables via la théorie des jeux et l'apprentissage séquentiel(2020), ANR-19-P3IA-0003,MIAI,MIAI @ Grenoble Alpes(2019), European Project: 952215,TAILOR(2020), European Project: 101021377,TRUST aWARE(2021), Loiseau, Patrick, Vie Privee et Confiance dans l'Internet Oriente Utilisateur - - PRoTecT2017 - ANR-17-CE23-0014 - AAPG2017 - VALID, Personnalisation de services en ligne respectueuse de la vie privée - - PROPEOS2021 - ANR-21-CE23-0031 - AAPG2021 - VALID, Algorithmes équitables via la théorie des jeux et l'apprentissage séquentiel - - FairPlay2020 - ANR-20-CE23-0007 - AAPG2020 - VALID, MIAI @ Grenoble Alpes - - MIAI2019 - ANR-19-P3IA-0003 - P3IA - VALID, and Foundations of Trustworthy AI - Integrating Reasoning, Learning and Optimization - TAILOR - 2020-09-01 - 2023-08-31 - 952215 - VALID

Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], [INFO.INFO-SI] Computer Science [cs]/Social and Information Networks [cs.SI], [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR]
Abstract

International audience; Several targeted advertising platforms offer transparency mechanisms, but researchers and civil societies repeatedly showed that those have major limitations. In this paper, we propose a collaborative ad transparency method to infer, without the cooperation of ad platforms, the targeting parameters used by advertisers to target their ads. Our idea is to ask users to donate data about their attributes and the ads they receive and to use this data to infer the targeting attributes of an ad campaign. We propose a Maximum Likelihood Estimator based on a simplified Bernoulli ad delivery model. We first test our inference method through controlled ad experiments on Facebook. Then, to further investigate the potential and limitations of collaborative ad transparency, we propose a simulation framework that allows varying key parameters. We validate that our framework gives accuracies consistent with real-world observations such that the insights from our simulations are transferable to the real world. We then perform an extensive simulation study for ad campaigns that target a combination of two attributes. Our results show that we can obtain good accuracy whenever at least ten monitored users receive an ad. This usually requires a few thousand monitored users, regardless of population size. Our simulation framework is based on a new method to generate a synthetic population with statistical properties resembling the actual population, which may be of independent interest.

Published
2023

29. Dimension results for extremal-generic polynomial systems over complete toric varieties

Author

Bender, Matías, Spaenlehauer, Pierre-Jean, TROPICAL (TROPICAL), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Cryptology, arithmetic : algebraic methods for better algorithms (CARAMBA), 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 European Project: 787840,COCAN(2019)

Subjects
FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Science - Symbolic Computation, Mathematics - Algebraic Geometry, FOS: Mathematics, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Symbolic Computation (cs.SC), Algebraic Geometry (math.AG)
Abstract

We study polynomial systems with prescribed monomial supports in the Cox rings of toric varieties built from complete polyhedral fans. We present combinatorial formulas for the dimensions of their associated subvarieties under genericity assumptions on the coefficients of the polynomials. Using these formulas, we identify at which degrees generic systems in polytopal algebras form regular sequences. Our motivation comes from sparse elimination theory, where knowing the expected dimension of these subvarieties leads to specialized algorithms and to large speed-ups for solving sparse polynomial systems. As a special case, we classify the degrees at which regular sequences defined by weighted homogeneous polynomials can be found, answering an open question in the Gr\"obner bases literature. We also show that deciding whether a sparse system is generically a regular sequence in a polytopal algebra is hard from the point of view of theoretical computational complexity.

Published
2023

30. The Algebraic Weak Factorisation System for Delta Lenses

Author

Clarke, Bryce, Automatisation et ReprésenTation: fOndation du calcUl et de la déducTion (PARTOUT), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
lens, monad, algebra for a monad, bidirectional transformation, algebraic weak factorisation system, FOS: Mathematics, Category Theory (math.CT), Mathematics - Category Theory, MSC classes:18A32, 18C15, 18A32, 18C15, [MATH]Mathematics [math]
Abstract

Delta lenses are functors equipped with a suitable choice of lifts, and are used to model bidirectional transformations between systems. In this paper, we construct an algebraic weak factorisation system whose R-algebras are delta lenses. Our approach extends a semi-monad for delta lenses previously introduced by Johnson and Rosebrugh, and generalises to any suitable category equipped with an orthogonal factorisation system and an idempotent comonad. We demonstrate how the framework of an algebraic weak factorisation system provides a natural setting for understanding the lifting operation of a delta lens, and also present an explicit description of the free delta lens on a functor., 14 pages + 2 page appendix, submitted to ACT 2023

Published
2023

31. Open Information Extraction with Entity Focused Constraints

Author

Upadhyay, Prajna, Balalau, Oana, Manolescu, Ioana, University of Hyderabad, Rich Data Analytics at Cloud Scale (CEDAR), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This work was performed using HPC resources from GENCI-IDRIS (Grant 2022-AD011011614R2). The authors were partially funded by the ANR-20-CHIA-0015 project andby the Hi!PARIS Center., and ANR-20-CHIA-0015,SourcesSay,Analyse et Interconnexion Intelligente des Contenus Héterogènes dans des Arènes Numériques(2020)

Subjects
Seq2seq model, neural network, named entities, open information extraction, [INFO]Computer Science [cs]
Abstract

International audience; Open Information Extraction (OIE) is the task of extracting tuples of the form (subject, predicate, object), without any knowledge of the type and lexical form of the predicate, the subject, or the object. In this work, we focus on improving OIE quality by exploiting domain knowledge about the subject and object. More precisely, knowing that the subjects and objects in sentences are often named entities, we explore how to inject constraints in the extraction through constrained inference and constraint-aware training. Our work leverages the state-of-the-art OpenIE6 platform, which we adapt to our setting. Through a carefully constructed training dataset and constrained training, we obtain a 29.17% F1-score improvement in the CaRB metric and a 24.37% F1-score improvement in the WIRe57 metric. Our technique has important applications-one of them is investigative journalism, where automatically extracting conflict-of-interest between scientists and funding organizations helps understand the type of relations companies engage with the scientists. Our code and data are available at https: //github.com/prajnaupadhyay/ openie-with-entities

Published
2023

32. Well-posedness of wave scattering in perturbed elastic waveguides and plates: application to an inverse problem of shape defect detection

Author

Éric Bonnetier, Angèle Niclas, Laurent Seppecher, Institut Fourier (IF), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Université Grenoble Alpes (UGA), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), École polytechnique (X), Analyse d’interactions stochastiques intelligentes et coopératives (ASCII), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut Camille Jordan (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Université de Lyon, Modélisation mathématique, calcul scientifique (MMCS), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL)

Subjects
[MATH.MATH-MP]Mathematics [math]/Mathematical Physics [math-ph], General Mathematics, General Engineering, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], General Physics and Astronomy
Abstract

International audience; The aim of this work is to present theoretical tools to study wave propagation in elastic waveguides and perform multi-frequency scattering inversion to reconstruct small shape defects in elastic waveguides and plates. Given surface multi-frequency wavefield measurements, we use a Born approximation to reconstruct localized defect in the geometry of the plate. To justify this approximation, we introduce a rigorous framework to study the propagation of elastic wavefield generated by arbitrary sources. By studying the decreasing rate of the series of inhomogeneous Lamb mode, we prove the well-posedness of the PDE that model elastic wave propagation in two- and three-dimensional planar waveguides. We also characterize the critical frequencies for which the Lamb decomposition is not valid. By using these results, we generalize the shape reconstruction method already developed for acoustic waveguide to two-dimensional elastic waveguides and provide a stable reconstruction method based on a mode-by-mode spacial Fourier inversion given by the scattered field.

Published
2023

33. On Detecting Policy-Related Political Ads: An Exploratory Analysis of Meta Ads in 2022 French Election

Author

Vera Sosnovik, Romaissa Kessi, Maximin Coavoux, Oana Goga, Université Grenoble Alpes (UGA), Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Groupe d’Étude en Traduction Automatique/Traitement Automatisé des Langues et de la Parole (GETALP), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Rich Data Analytics at Cloud Scale (CEDAR), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-17-CE23-0014,PRoTecT,Vie Privee et Confiance dans l'Internet Oriente Utilisateur(2017), ANR-21-CE23-0031,PROPEOS,Personnalisation de services en ligne respectueuse de la vie privée(2021), ANR-19-P3IA-0003,MIAI,MIAI @ Grenoble Alpes(2019), European Project: 101021377,TRUST aWARE(2021), and European Project: 952215,TAILOR(2020)

Subjects
FOS: Computer and information sciences, Computer Science - Computers and Society, Computers and Society (cs.CY), [INFO]Computer Science [cs]
Abstract

Online political advertising has become the cornerstone of political campaigns. The budget spent solely on political advertising in the U.S. has increased by more than 100% from \$700 million during the 2017-2018 U.S. election cycle to \$1.6 billion during the 2020 U.S. presidential elections. Naturally, the capacity offered by online platforms to micro-target ads with political content has been worrying lawmakers, journalists, and online platforms, especially after the 2016 U.S. presidential election, where Cambridge Analytica has targeted voters with political ads congruent with their personality To curb such risks, both online platforms and regulators (through the DSA act proposed by the European Commission) have agreed that researchers, journalists, and civil society need to be able to scrutinize the political ads running on large online platforms. Consequently, online platforms such as Meta and Google have implemented Ad Libraries that contain information about all political ads running on their platforms. This is the first step on a long path. Due to the volume of available data, it is impossible to go through these ads manually, and we now need automated methods and tools to assist in the scrutiny of political ads. In this paper, we focus on political ads that are related to policy. Understanding which policies politicians or organizations promote and to whom is essential in determining dishonest representations. This paper proposes automated methods based on pre-trained models to classify ads in 14 main policy groups identified by the Comparative Agenda Project (CAP). We discuss several inherent challenges that arise. Finally, we analyze policy-related ads featured on Meta platforms during the 2022 French presidential elections period., Proceedings of the ACM Web Conference 2023 (WWW '23), May 1--5, 2023, Austin, TX, USA

Published
2023

34. Analysis of a periodic optimal control problem connected to microalgae anaerobic digestion

Author

Bayen, Térence, Mairet, Francis, Martinon, Pierre, Sebbah, Matthieu, Modelling and Optimisation of the Dynamics of Ecosystems with MICro-organisme (MODEMIC), 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)-Mathématiques, Informatique et STatistique pour l'Environnement et l'Agronomie (MISTEA), Institut National de la Recherche Agronomique (INRA)-Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro)-Institut National de la Recherche Agronomique (INRA)-Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro), Mathématiques, Informatique et STatistique pour l'Environnement et l'Agronomie (MISTEA), Institut National de la Recherche Agronomique (INRA)-Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro), Institut Montpelliérain Alexander Grothendieck (IMAG), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Biological control of artificial ecosystems (BIOCORE), Laboratoire d'océanographie de Villefranche (LOV), Observatoire océanologique de Villefranche-sur-mer (OOVM), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Observatoire océanologique de Villefranche-sur-mer (OOVM), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-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)-Institut National de la Recherche Agronomique (INRA), Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems (Commands), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM), Programa de Financiamiento Basal from Center of Mathematical Modeling, Universidad de Chile, INRIA Associated team with Chile: DYMECOS, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut National de la Recherche Agronomique (INRA)-Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Centre National de la Recherche Scientifique (CNRS)-Institut national des sciences de l'Univers (INSU - CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Institut national des sciences de l'Univers (INSU - CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Observatoire océanologique de Villefranche-sur-mer (OOVM), Centre National de la Recherche Scientifique (CNRS)-Institut national des sciences de l'Univers (INSU - CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Institut national des sciences de l'Univers (INSU - CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro)-Institut National de la Recherche Agronomique (INRA)-Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro)-Institut National de la Recherche Agronomique (INRA), Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro)-Institut National de la Recherche Agronomique (INRA), Institut National de la Recherche Agronomique (INRA)-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)-Laboratoire d'océanographie de Villefranche (LOV), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut national des sciences de l'Univers (INSU - CNRS)-Observatoire océanologique de Villefranche-sur-mer (OOVM), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut national des sciences de l'Univers (INSU - CNRS)-Observatoire océanologique de Villefranche-sur-mer (OOVM), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), Unité de Mathématiques Appliquées (UMA), École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Modelling and Optimisation of the Dynamics of Ecosystems with MICro-organisme ( MODEMIC ), 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 ) -Mathématiques, Informatique et STatistique pour l'Environnement et l'Agronomie ( MISTEA ), Institut National de la Recherche Agronomique ( INRA ) -Institut national d’études supérieures agronomiques de Montpellier ( Montpellier SupAgro ) -Institut National de la Recherche Agronomique ( INRA ) -Institut national d’études supérieures agronomiques de Montpellier ( Montpellier SupAgro ), Institut de Mathématiques et de Modélisation de Montpellier ( I3M ), Université Montpellier 2 - Sciences et Techniques ( UM2 ) -Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ), Mathématiques, Informatique et STatistique pour l'Environnement et l'Agronomie ( MISTEA ), Institut National de la Recherche Agronomique ( INRA ) -Institut national d’études supérieures agronomiques de Montpellier ( Montpellier SupAgro ), Biological control of artificial ecosystems ( BIOCORE ), Laboratoire d'océanographie de Villefranche ( LOV ), Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Institut national des sciences de l'Univers ( INSU - CNRS ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Institut national des sciences de l'Univers ( INSU - CNRS ) -Centre National de la Recherche Scientifique ( CNRS ) -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 ) -Institut National de la Recherche Agronomique ( INRA ), Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems ( Commands ), Centre de Mathématiques Appliquées - Ecole Polytechnique ( CMAP ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Unité de Mathématiques Appliquées ( UMA ), École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech ) -École Nationale Supérieure de Techniques Avancées ( Univ. Paris-Saclay, ENSTA ParisTech ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ), Universidad Tecnica Federico Santa Maria [Valparaiso] ( UTFSM ), Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro), and Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut National de la Recherche Agronomique (INRA)

Subjects
[ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], [ MATH ] Mathematics [math], [ SDV ] Life Sciences [q-bio], Optimal Control, [SDV]Life Sciences [q-bio], Micro-algae, Periodic Differential Equations, [SPI]Engineering Sciences [physics], Chemostat, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, [ INFO.INFO-AU ] Computer Science [cs]/Automatic Control Engineering, [ SPI ] Engineering Sciences [physics], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH]Mathematics [math]
Abstract

International audience; In this work, we study the coupling of a culture of microalgae limited by light and an anaerobic digester in a two-tank bioreactor. The model for the reactor combines a periodic day-night light for the culture of microalgae and a classical chemostat model for the digester. We first prove the existence and attraction of periodic solutions of this problem for a 1 day period. Then, we study the optimal control problem of optimizing the production of methane in the digester during a certain timeframe, the control on the system being the dilution rate (the input flow of microalgae in the digester). We apply Pontryagin's Maximum Principle in order to characterize optimal controls, including the computation of singular controls. We present numerical simulations by direct and indirect methods for different light models and compare the optimal 1-day periodic solution to the optimal strategy over larger timeframes. Finally, we also investigate the dependence of the optimal cost with respect to the volume ratio of the two tanks.

Published
2015

35. Modeling In-Flight Ice Accretion Under Uncertain Conditions

Author

Alberto Guardone, Tommaso Bellosta, Giulio Gori, Olivier Le Maitre, Pietro Marco Congedo, Uncertainty Quantification in Scientific Computing and Engineering (PLATON), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Dipartimento di Scienze e Tecnologie Aerospaziali [Milano] (DAER), Politecnico di Milano [Milan] (POLIMI), European Project: 722734,H2020 Pilier Excellent Science,H2020-MSCA-ITN-2016,UTOPIAE(2017), and European Project: 824310,H2020,H2020-MG-2018-SingleStage-INEA,ICE GENESIS(2020)

Subjects
[PHYS.PHYS.PHYS-FLU-DYN]Physics [physics]/Physics [physics]/Fluid Dynamics [physics.flu-dyn], 020301 aerospace & aeronautics, Aerospace Engineering, 02 engineering and technology, Geophysics, Ice accretion, 01 natural sciences, Physics::Geophysics, 010305 fluids & plasmas, 0203 mechanical engineering, 0103 physical sciences, Astrophysics::Earth and Planetary Astrophysics, ComputingMilieux_MISCELLANEOUS, Physics::Atmospheric and Oceanic Physics, Geology, Parametric statistics, Icing
Abstract

International audience; In-flight ice accretion under parametric uncertainty is investigated. Three test cases are presented which reproduce experiments carried out at the NASA's Glenn Icing Research Tunnel (IRT) facility. A preliminary accuracy assessment, achieved comparing numerical predictions against experimental observations, confirm the robustness and the predictiveness of the computerized icing model. Besides, sensitivity analyses highlight the variance of the targeted outputs with respect to the different uncertain inputs. In rime icing conditions, a predominant role is played by the uncertainty affecting the airfoil angle of attack, the cloud liquid water content and the droplets’ mean volume diameter. In glaze icing condition, the sensitivity analysis shows instead that the output variability is due mainly to the ambient temperature uncertainty. Results expose a major criticality of standard uncertainty quantification techniques. The issue is inherent the approximation of the full icing model behavior in domain regions scarcely affected by ice build up. To mitigate the issue, a non-linear regression method is proposed and applied.

Published
2022

36. A Quantization Procedure for Nonlinear Pricing with an Application to Electricity Markets

Author

Jacquet, Quentin, van Ackooij, Wim, Alasseur, Clémence, Gaubert, Stéphane, Optimisation, Simulation, Risque et Statistiques pour les Marchés de l’Energie (EDF R&D OSIRIS), EDF R&D (EDF R&D), EDF (EDF)-EDF (EDF), TROPICAL (TROPICAL), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Finance des Marchés d'Energie (FiME Lab), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-CREST-EDF R&D (EDF R&D), and École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract

We consider a revenue maximization model, in which a company aims at designing a menu of contracts, given a population of customers. A standard approach consists in constructing an incentive-compatible continuum of contracts, i.e., a menu composed of an infinite number of contracts, where each contract is especially adapted to an infinitesimal customer, taking his type into account. Nonetheless, in many applications, the company is constrained to offering a limited number of contracts. We show that this question reduces to an optimal quantization problem, similar to the pruning problem that appeared in the max-plus based numerical methods in optimal control. We develop a new quantization algorithm, which, given an initial menu of contracts, iteratively prunes the less important contracts, to construct an implementable menu of the desired cardinality, while minimizing the revenue loss. We apply this algorithm to solve a pricing problem with price-elastic demand, originating from the electricity retail market. Numerical results show an improved performance by comparison with earlier pruning algorithms.

Published
2023

37. SQISignHD: New Dimensions in Cryptography

Author

Dartois, Pierrick, Leroux, Antonin, Robert, Damien, Wesolowski, Benjamin, Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Lithe and fast algorithmic number theory (LFANT), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Geometry, arithmetic, algorithms, codes and encryption (GRACE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Direction Générale de l'Armement, Direction Generale de l'Armement, Centre National de la Recherche Scientifique (CNRS), Unité de Mathématiques Pures et Appliquées (UMPA-ENSL), École normale supérieure de Lyon (ENS de Lyon)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0008,CIAO,Cryptographie, isogenies et variété abéliennes surpuissantes(2019), and ANR-22-PETQ-0008,PQ-TLS,Post-quantum padlock for web browser(2022)

Subjects
Kani's lemma, Post-quantum cryptography, Isogenies, SQISign, [INFO]Computer Science [cs], SIDH, [MATH]Mathematics [math]
Abstract

We introduce SQISignHD, a new post-quantum digital signature scheme inspired by SQISign. SQISignHD exploits the recent algorithmic breakthrough underlying the attack on SIDH, which allows to efficiently represent isogenies of arbitrary degrees as components of a higher dimensional isogeny. SQISignHD overcomes the main drawbacks of SQISign. First, it scales well to high security levels, since the public parameters for SQISignHD are easy to generate: the characteristic of the underlying field needs only be of the form 2 f 3 f ′ − 1. Second, the signing procedure is simpler and more efficient. Third, the scheme is easier to analyse, allowing for a much more compelling security reduction. Finally, the signature sizes are even more compact than (the already record-breaking) SQISign, with compressed signatures as small as 105 bytes for the post-quantum NIST-1 level of security. These advantages may come at the expense of the verification, which now requires the computation of an isogeny in dimension 4, a task whose optimised cost is still uncertain, as it has been the focus of very little attention.

Published
2023

38. Échantillonneur rapide de la distribution de von Mises Fisher en Python

Author

Pinzón, Carlos, Jung, Kangsoo, Concurrency, Mobility and Transactions (COMETE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and European Project: 835294,H2020 Pilier ERC,HYPATIA(2019)

Subjects
Sampling Algorithms, [INFO]Computer Science [cs], Python Implementation, [MATH]Mathematics [math], Von Mises Fisher distribution
Abstract

This paper implements a method for sampling from the d-dimensional Von Mises Fisher distribution using NumPy, focusing on speed and readability. The complexity of the algorithm is O(nd) for n samples, which is theoretically optimal taking into account that nd is the output size.

Published
2023

39. Using the Charlap-Coley-Robbins polynomials for computing isogenies

Author

Morain, François, Geometry, arithmetic, algorithms, codes and encryption (GRACE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Mathematics - Number Theory, modular polynomials, isogenies, FOS: Mathematics, Elliptic curves, Number Theory (math.NT), [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT]
Abstract

The SEA algorithm for computing the cardinality of elliptic curves over finite fields in many characteristic uses modular polynomials. These polynomials come into different flavors, and methods to compute them flourished. Once equipped with some modular polynomials for prime $\ell$, algebraic formulas are used to compute a curve $\mathcal{E}^*/\mathbb{F}_q$ that is $\ell$-isogenous to the curve of interest $\mathcal{E}$. These formulas involve derivatives of the modular polynomial that may sometime vanish. One way to overcome this problem is to use alternative trivariate polynomials $U_\ell$, $V_\ell$, and $W_\ell$ introduced by Charlap, Coley and Robbins to overcome some difficulties in the first versions of Elkies's approach. We give properties of these polynomials, as well as formulas to compute the isogenous curve that were sketched by Atkin. Also we investigate another suggestion of Atkin using modular polynomials associated to a power product of Dedekind's $\eta$ function.

Published
2023

40. Échantillonneur rapide de la distribution de von Mises Fisher en Python

Author

Pinzón, Carlos, Concurrency, Mobility and Transactions (COMETE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and European Project: 835294,H2020 Pilier ERC,HYPATIA(2019)

Subjects
Sampling Algorithms, [INFO]Computer Science [cs], Python Implementation, [MATH]Mathematics [math], Von Mises Fisher distribution
Abstract

This paper implements a method for sampling from the d-dimensional Von Mises Fisher distribution using NumPy, focusing on speed and readability. The complexity of the algorithm is O(nd) for n samples, which is theoretically optimal taking into account that nd is the output size.

Published
2023

41. A positive perspective on term representation: Extended paper

Author

Miller, Dale, Wu, Jui-Hsuan, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Automatisation et ReprésenTation: fOndation du calcUl et de la déducTion (PARTOUT), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
sharing, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Term representation, Focused proof systems
Abstract

International audience; We use the focused proof system LJF as a framework for describing term structures and substitution. Since the proof theory of LJF does not pick a canonical polarization for primitive types, two different approaches to term representation arise. When primitive types are given the negative polarity, LJF proofs encode terms as tree-like structures in a familiar fashion. In this situation, cut elimination also yields the familiar notion of substitution. On the other hand, when primitive types are given the positive polarity, LJF proofs yield a structure in which explicit sharing of term structures is possible. Such a representation of terms provides an explicit method for sharing term structures. In this setting, cut elimination yields a different notion of substitution. We illustrate these two approaches to term representation by applying them to the encoding of untyped λ-terms. We also exploit concurrency theory techniques-namely traces and simulation-to compare untyped λ-terms using such different structuring disciplines.

Published
2023

42. Accuracy assessment of an internal resistance model of Li-ion batteries in immersion cooling configuration

Author

Elie Solai, Héloïse Beaugendre, Ulrich Bieder, Pietro Marco Congedo, Certified Adaptive discRete moDels for robust simulAtions of CoMplex flOws with Moving fronts (CARDAMOM), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), CEA- Saclay (CEA), Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Uncertainty Quantification in Scientific Computing and Engineering (PLATON), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), and École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France

Subjects
[PHYS.PHYS.PHYS-FLU-DYN]Physics [physics]/Physics [physics]/Fluid Dynamics [physics.flu-dyn], Lithium-ion batteries, Kriging, Bayesian calibration, Energy Engineering and Power Technology, Immersion cooling, Numerical simulation, Industrial and Manufacturing Engineering, Uncertainty quantification, Surrogate model
Abstract

International audience; Internal resistance is a critical parameter of the thermal behavior of Li-ion battery cells. This paper proposes an innovative way to deal with the uncertainties related to this physical parameter using experimental data and numerical simulation. First, a CFD model is validated against an experimental configuration representing the behavior of heated Li-ion battery cells under constant discharging current conditions. Secondly, an Uncertainty Quantification based methodology is proposed to represent the internal resistance and its inherent uncertainties. Thanks to an accurate and fast to compute surrogate model, the impact of those uncertainties on the temperature evolution of Li-ion cells is quantified. Finally, Bayesian inference of the internal resistance model parameters using experimental measurements is performed, reducing the prediction uncertainty by almost 95% for some temperatures of interest. Finally, an enhanced internal model is constructed by considering the state of charge and temperature dependency on internal resistance. This model is implemented in the CFD code and used to model a full discharge of the Li-ion batteries. The resulting temperature evolution computed with the two different resistance models is compared for the low state of charge situations.

Published
2023

43. Backtracking reference stores

Author

Noûs, Camille, Scherer, Gabriel, Laboratoire Cogitamus, Automatisation et ReprésenTation: fOndation du calcUl et de la déducTion (PARTOUT), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Timothy Bourke, and Delphine Demange

Subjects
[INFO]Computer Science [cs]
Abstract

National audience; François Pottier's unionFind library is parameterized over an underlying store of mutable references, and provides the usual references, transactional reference stores (for rolling back some changes in case of higher-level errors), and persistent reference stores. We extend this library with a new implementation of backtracking reference stores, to get a Union-Find implementation that efficiently supports arbitrary backtracking and also subsumes the transactional interface. Our backtracking reference stores are not specific to unionFind, they can be used to build arbitrary backtracking data structures. The natural implementation, using a journal to record all writes, provides amortized-constant-time operations with a space overhead linear in the number of store updates. A refined implementation reduces the memory overhead to be linear in the number of store cells updated, and gives performance that match non-backtracking references in practice.

Published
2023

44. NCP: Neural Correspondence Prior for Effective Unsupervised Shape Matching

Author

Attaiki, Souhaib, Ovsjanikov, Maks, La Géometrie au Service du Numérique (GEOMERIX), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Polytechnique de Paris (IP Paris), and European Project: 758800,ERC,ERC-2017-StG-758800,EXPROTEA(2018)

Subjects
FOS: Computer and information sciences, Computer Science - Graphics, Computer Vision and Pattern Recognition (cs.CV), Computer Science - Computer Vision and Pattern Recognition, [INFO]Computer Science [cs], Graphics (cs.GR)
Abstract

We present Neural Correspondence Prior (NCP), a new paradigm for computing correspondences between 3D shapes. Our approach is fully unsupervised and can lead to high-quality correspondences even in challenging cases such as sparse point clouds or non-isometric meshes, where current methods fail. Our first key observation is that, in line with neural priors observed in other domains, recent network architectures on 3D data, even without training, tend to produce pointwise features that induce plausible maps between rigid or non-rigid shapes. Secondly, we show that given a noisy map as input, training a feature extraction network with the input map as supervision tends to remove artifacts from the input and can act as a powerful correspondence denoising mechanism, both between individual pairs and within a collection. With these observations in hand, we propose a two-stage unsupervised paradigm for shape matching by (i) performing unsupervised training by adapting an existing approach to obtain an initial set of noisy matches, and (ii) using these matches to train a network in a supervised manner. We demonstrate that this approach significantly improves the accuracy of the maps, especially when trained within a collection. We show that NCP is data-efficient, fast, and achieves state-of-the-art results on many tasks. Our code can be found online: https://github.com/pvnieo/NCP., NeurIPS 2022, 10 pages, 9 figures

Published
2023

45. State and parameter learning with PaRIS particle Gibbs

Author

Cardoso, Gabriel Victorino, Janati, Yazid, Le Corff, Sylvain, Moulines, Éric, Olsson, Jimmy, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), IHU-LIRYC, Université Bordeaux Segalen - Bordeaux 2-CHU Bordeaux [Bordeaux], Institut Polytechnique de Paris (IP Paris), Communications, Images et Traitement de l'Information (TSP - CITI), Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP), Traitement de l'Information Pour Images et Communications (TIPIC-SAMOVAR), Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux (SAMOVAR), Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP)-Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP), Laboratoire de Probabilités, Statistique et Modélisation (LPSM (UMR_8001)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Modélisation en pharmacologie de population (XPOP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Mathematics (KTH Royal Institute of Technology), and Royal Institute of Technology [Stockholm] (KTH )

Subjects
State-space models, Methodology (stat.ME), FOS: Computer and information sciences, State-space, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Statistics - Machine Learning, Machine learning, Machine Learning (stat.ML), Statistics - Methodology
Abstract

Non-linear state-space models, also known as general hidden Markov models, are ubiquitous in statistical machine learning, being the most classical generative models for serial data and sequences in general. The particle-based, rapid incremental smoother PaRIS is a sequential Monte Carlo (SMC) technique allowing for efficient online approximation of expectations of additive functionals under the smoothing distribution in these models. Such expectations appear naturally in several learning contexts, such as likelihood estimation (MLE) and Markov score climbing (MSC). PARIS has linear computational complexity, limited memory requirements and comes with non-asymptotic bounds, convergence results and stability guarantees. Still, being based on self-normalised importance sampling, the PaRIS estimator is biased. Our first contribution is to design a novel additive smoothing algorithm, the Parisian particle Gibbs PPG sampler, which can be viewed as a PaRIS algorithm driven by conditional SMC moves, resulting in bias-reduced estimates of the targeted quantities. We substantiate the PPG algorithm with theoretical results, including new bounds on bias and variance as well as deviation inequalities. Our second contribution is to apply PPG in a learning framework, covering MLE and MSC as special examples. In this context, we establish, under standard assumptions, non-asymptotic bounds highlighting the value of bias reduction and the implicit Rao--Blackwellization of PPG. These are the first non-asymptotic results of this kind in this setting. We illustrate our theoretical results with numerical experiments supporting our claims., preprint. arXiv admin note: text overlap with arXiv:2209.10351

Published
2023

46. R-miss-tastic: a unified platform for missing values methods and workflows

Author

Mayer, Imke, Sportisse, Aude, Josse, Julie, Tierney, Nicholas, Vialaneix, Nathalie, Charité Center for Internal Medicine and Dermatology, Clinic for Psychosomatic Medicine, Charité-Universitätsmedizin Berlin, Berlin, Germany., Modèles et algorithmes pour l’intelligence artificielle (MAASAI), 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)-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)-Laboratoire Jean Alexandre Dieudonné (LJAD), 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)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), 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)-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)-Centre National de la Recherche Scientifique (CNRS), Médecine de précision par intégration de données et inférence causale (PREMEDICAL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Desbrest de santé publique (IDESP), Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM), Monash university, Unité de Mathématiques et Informatique Appliquées de Toulouse (MIAT INRAE), Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Institute of Public Health (IPH), Charité - UniversitätsMedizin = Charité - University Hospital [Berlin], Institut National de Recherche en Informatique et en Automatique (Inria), Institut Desbrest de santé publique (IDESP), Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM), University of Melbourne, Unité de Mathématiques et Informatique Appliquées de Toulouse (MIAT INRA), Centre d'Analyse et de Mathématique sociales (CAMS), École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Modélisation en pharmacologie de population (XPOP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Interdisciplinary Institute for Artificial Intelligence (3iA Côte d’Azur), and R Consortium project (2018/2020)

Subjects
FOS: Computer and information sciences, Statistics and Probability, [STAT.AP]Statistics [stat]/Applications [stat.AP], Numerical Analysis, bibliography, guided workflows, state of the art, Methodology (stat.ME), missing data, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], teaching material, Statistics, Probability and Uncertainty, [MATH]Mathematics [math], reproducibility, statistical analysis community, Statistics - Methodology
Abstract

Missing values are unavoidable when working with data. Their occurrence is exacerbated as more data from different sources become available. However, most statistical models and visualization methods require complete data, and improper handling of missing data results in information loss or biased analyses. Since the seminal work of Rubin (1976), a burgeoning literature on missing values has arisen, with heterogeneous aims and motivations. This led to the development of various methods, formalizations, and tools. For practitioners, it remains nevertheless challenging to decide which method is most suited for their problem, partially due to a lack of systematic covering of this topic in statistics or data science curricula. To help address this challenge, we have launched the "R-miss-tastic" platform, which aims to provide an overview of standard missing values problems, methods, and relevant implementations of methodologies. Beyond gathering and organizing a large majority of the material on missing data (bibliography, courses, tutorials, implementations), "R-miss-tastic" covers the development of standardized analysis workflows. Indeed, we have developed several pipelines in R and Python to allow for hands-on illustration of and recommendations on missing values handling in various statistical tasks such as matrix completion, estimation and prediction, while ensuring reproducibility of the analyses. Finally, the platform is dedicated to users who analyze incomplete data, researchers who want to compare their methods and search for an up-to-date bibliography, and also teachers who are looking for didactic materials (notebooks, video, slides)., Comment: 36 pages, 9 figures

Published
2023

47. Intégration de la recherche de connexion dans les requêtes de graphique

Author

Anadiotis, Angelos Christos, Manolescu, Ioana, Mohanty, Madhulika, Mohanty, Madhulika, Oracle Labs Switzerland, École polytechnique (X), Rich Data Analytics at Cloud Scale (CEDAR), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-20-CHIA-0015,SourcesSay,Analyse et Interconnexion Intelligente des Contenus Héterogènes dans des Arènes Numériques(2020), and Inria Saclay - Île de France

Subjects
FOS: Computer and information sciences, Artificial Intelligence (cs.AI), [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Computer Science - Databases, [INFO.INFO-WB] Computer Science [cs]/Web, Computer Science - Artificial Intelligence, [INFO.INFO-WB]Computer Science [cs]/Web, Keyword Search on Graphs, [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], Databases (cs.DB), [INFO]Computer Science [cs], Graph Queries, Graph Data Management
Abstract

National audience; Graph data management and querying has many practical applications. When graphs are very heterogeneous and/or users are unfamiliar with their structure, they may need to find how two or more groups of nodes are connected in a graph, even when users are not able to describe the connections. This is only partially supported by existing query languages, which allow searching for paths, but not for trees connecting three or more node groups. The latter is related to the NP-hard Group Steiner Tree problem, and has been previously considered for keyword search in databases. In this work, we formally show how to integrate connecting tree patterns (CTPs, in short) within a graph query language such as SPARQL or Cypher, leading to an Extended Query Language (or EQL, in short). We then study a set of algorithms for evaluating CTPs; we generalize prior keyword search work, most importantly by (i) considering bidirectional edge traversal and (ii) allowing users to select any score function for ranking CTP results. To cope with very large search spaces, we propose an efficient pruning technique and formally establish a large set of cases where our algorithm, MOLESP, is complete even with pruning. Our experiments validate the performance of our CTP and EQL evaluation algorithms on a large set of synthetic and real-world workloads.

Published
2023

48. Group privacy for personalized federated learning

Author

Filippo Galli, Sayan Biswas, Kangsoo Jung, Tommaso Cucinotta, Catuscia Palamidessi, Scuola Normale Superiore di Pisa (SNS), Concurrency, Mobility and Transactions (COMETE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Scuola Universitaria Superiore Sant'Anna [Pisa] (SSSUP), European Project: 835294,H2020 Pilier ERC,HYPATIA(2019), Biswas, Sayan, and Privacy and Utility Allied - HYPATIA - - H2020 Pilier ERC2019-10-01 - 2024-09-30 - 835294 - VALID

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, personalized models, Artificial Intelligence (cs.AI), Computer Science - Cryptography and Security, d-privacy, federated learning, Computer Science - Artificial Intelligence, differential privacy, [INFO]Computer Science [cs], [INFO] Computer Science [cs], Cryptography and Security (cs.CR), Machine Learning (cs.LG)
Abstract

ISSN 2184-4356; International audience; Federated learning (FL) is a type of collaborative machine learning where participating peers/clients process their data locally, sharing only updates to the collaborative model. This enables to build privacy-aware distributed machine learning models, among others. The goal is the optimization of a statistical model's parameters by minimizing a cost function of a collection of datasets which are stored locally by a set of clients. This process exposes the clients to two issues: leakage of private information and lack of personalization of the model. On the other hand, with the recent advancements in various techniques to analyze data, there is a surge of concern for the privacy violation of the participating clients. To mitigate this, differential privacy and its variants serve as a standard for providing formal privacy guarantees. Often the clients represent very heterogeneous communities and hold data which are very diverse. Therefore, aligned with the recent focus of the FL community to build a framework of personalized models for the users representing their diversity, it is also of utmost importance to protect the clients' sensitive and personal information against potential threats. To address this goal we consider $d$-privacy, also known as metric privacy, which is a variant of local differential privacy, using a a metric-based obfuscation technique that preserves the topological distribution of the original data. To cope with the issue of protecting the privacy of the clients and allowing for personalized model training to enhance the fairness and utility of the system, we propose a method to provide group privacy guarantees exploiting some key properties of $d$-privacy which enables personalized models under the framework of FL. We provide theoretical justifications to the applicability and experimental validation on real datasets to illustrate the working of our method.

Published
2023

49. Security Assessment of NTRU Against Non-Profiled SCA

Author

Luk Bettale, Julien Eynard, Simon Montoya, Guénaël Renault, Rémi Strullu, Idemia, Agence nationale de la sécurité des systèmes d'information (ANSSI), Geometry, arithmetic, algorithms, codes and encryption (GRACE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], NTRU, Non-profiled SCA, Post-Quantum Cryptography
Abstract

International audience; NTRU was first introduced by J. Hoffstein, J. Pipher and J.H Silverman in 1998. Its security, efficiency and compactness properties have been carefully studied for more than two decades. A key encapsulation mechanism (KEM) version was even submitted to the NIST standardization competition and made it to the final round. Even though it has not been chosen to be a new standard, NTRU remains a relevant, practical and trustful post-quantum cryptographic primitive. In this paper, we investigate the side-channel resistance of the NTRU Decrypt procedure. In contrast with previous works about side-channelanalysis on NTRU, we consider a weak attacker model and we focus on an implementation that incorporates some side-channel countermeasures. The attacker is assumed to be unable to mount powerful attacks by using templates or by forging malicious ciphertexts for instance. In this context, we show how a non-profiled side-channel analysis can be done against a core operation of NTRU decryption. Despite the consideredcountermeasures and the weak attacker model, our experiments show that the secret key can be fully retrieved with a few tens of traces.

Published
2023

50. Multispecies cross-diffusions: from a nonlocal mean-field to a porous medium system without self-diffusion

Author

Doumic, Marie, Hecht, Sophie, Perthame, Benoit, Peurichard, Diane, Mathématiques pour l’évolution, la reproduction, la croissance et l’émergence (MERGE), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Polytechnique de Paris (IP Paris), Centre National de la Recherche Scientifique (CNRS), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Modelling and Analysis for Medical and Biological Applications (MAMBA), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Emergence project MATHREGEN de Sorbonne Alliance University, and ANR-22-CE45-0024,ENERGENCE,Modélisation ENERgétique de l'émerGENCE et de l'homéorhésie de l'architecture tissulaire(2022)

Subjects
Aggregation equation, Mathematics - Analysis of PDEs, [MATH.MATH-GM]Mathematics [math]/General Mathematics [math.GM], General Mathematics (math.GM), Cross-diffusion, Mathematical biology, FOS: Mathematics, Nonlocal interactions, 2010 Mathematics Subject Classification. 35Q92, 35K55, 35R09, 35B25, Localisation limit, Mathematics - General Mathematics, Multispecies models, Analysis of PDEs (math.AP)
Abstract

Systems describing the long-range interaction between individuals have attracted a lot of attention in the last years, in particular in relation with living systems. These systems are quadratic, written under the form of transport equations with a nonlocal self-generated drift. We establish the localisation limit, that is the convergence of nonlocal to local systems, when the range of interaction tends to 0. These theoretical results are sustained by numerical simulations. The major new feature in our analysis is that we do not need diffusion to gain compactness, at odd with the existing literature. The central compactness result is provided by a full rank assumption on the interaction kernels. In turn, we prove existence of weak solutions for the resulting system, a cross-diffusion system of quadratic type.

Published
2023
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results