Search

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.

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

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.

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.

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.

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.

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

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

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

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.

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.

International audience

International audience

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.

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.

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.

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.

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

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

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.

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.

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.

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.

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

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

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.

International audience; Infrared cooled photodetectors must operate at higher temperatures to reduce their size, weight and power consumption (SWaP context). Their stability and image quality are then challenged by extra electrical activity of crystal defects. Knowledge of defect populations is mandatory to improve the material quality of the epitaxial Hg1−xCdxTe (MCT) active layer and the Cd1−xZnxTe (CZT) substrate. Positron annihilation spectroscopy with a slow positron beam was used to study near-surface open-volume defects profiles. Low- and high-momentum fractions (S,W) were used to characterize the Doppler broadening of the 511 keV electron-positron pair annihilation-line as a function of the positron implantation energy E. The results show that three regions can be identified beneath the surface of the as-grown non-optimized MCT layer. The quasi-linear relationship between the annihilation characteristics in the regions suggests that the defect populations mainly correspond to the same open-volume defect in different concentrations. The probed defect is thought to be related to the mercury vacancy. This hypothesis is discussed in an original way with near-surface elemental profiles using scanning transmission electron spectroscopy combined to energy dispersive x-ray spectroscopy (STEM-EDX). Afterwards, this approach is extended to CZT substrates showing that surface and bulk properties of those fabricated by LYNRED tend to match those that are state-of-the-art. A common open-volume defect is probed, in concentration estimated by Hall effect around 1015 cm−3 and thought to be related to the cadmium vacancy.

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.

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.

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

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.

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.

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.

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.

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.

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.

Temperature variation of the lower critical field in the noncentrosymmetric superconductor $\alpha$-BiPd was probed by local magnetization measurements using Hall micromagnetometry, performed down to 0.3 K in a magnetic field applied along the crystallographic $b$ axis. Below a critical temperature $T_c \simeq$ 3.8 K, a conventional $H_{c1}(T)$ dependence was found, typical for a single-band $s$-wave BCS superconductor. The obtained data imply an absence of spin-triplet component in the superconducting wavefunction and marginal multiband effects in this material, which contradicts some literature reports., Comment: 14 pages, 5 figures

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.

We introduce a new general-purpose approach to deep learning on 3D surfaces, based on the insight that a simple diffusion layer is highly effective for spatial communication. The resulting networks are automatically robust to changes in resolution and sampling of a surface -- a basic property which is crucial for practical applications. Our networks can be discretized on various geometric representations such as triangle meshes or point clouds, and can even be trained on one representation then applied to another. We optimize the spatial support of diffusion as a continuous network parameter ranging from purely local to totally global, removing the burden of manually choosing neighborhood sizes. The only other ingredients in the method are a multi-layer perceptron applied independently at each point, and spatial gradient features to support directional filters. The resulting networks are simple, robust, and efficient. Here, we focus primarily on triangle mesh surfaces, and demonstrate state-of-the-art results for a variety of tasks including surface classification, segmentation, and non-rigid correspondence., Published in ACM Transactions on Graphics, presented at SIGGRAPH 2022

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.

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

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

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

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.

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.

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.

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.

The symmetrized tropical semiring is an extension of the tropical semifield, initially introduced to solve tropical linear systems using Cramer's rule. It is equivalent to the real tropical hyperfield, which has been used in the study of tropicalizations of semialgebraic sets. Polynomials over the symmetrized tropical semiring, and their factorizations, were considered by Quadrat. Recently, Baker and Lorscheid introduced a notion of multiplicity for the roots of univariate polynomials over hyperfields. In the special case of the hyperfield of signs, they related multiplicities with Descarte's rule of sign for real polynomials. We investigate here the factorizations of univariate polynomial functions over symmetrized tropical semirings, and relate them with the multiplicities of roots over these semirings. We deduce a Descartes' rule for ``signs and valuations'', which applies to polynomials over a real closed field with a convex valuation and an arbitrary (divisible) value group. We show in particular that the inequality of the Descartes' rule is tight when the value group is non-trivial. This extends to arbitrary value groups a characterization of Gunn in the rank one case, answering also to the tightness question. Our results are obtained using the framework of semiring systems introduced by Rowen, together with model theory of valued fields.

International audience; Denoising is a common, yet critical operation in geometry processing aiming at recovering high-fidelity models of piecewisesmooth objects from noise-corrupted pointsets. Despite a sizable literature on the topic, there is a dearth of approaches capable of processing very noisy and outlier-ridden input pointsets for which no normal estimates and no assumptions on the underlying geometric features or noise type are provided. In this paper, we propose a new robust-statistics approach to denoising pointsets based on line processes to offer robustness to noise and outliers while preserving sharp features possibly present in the data. While the use of robust statistics in denoising is hardly new, most approaches rely on prescribed filtering using data-independent blending expressions based on the spatial and normal closeness of samples. Instead, our approach deduces a geometric denoising strategy through robust and regularized tangent plane fitting of the initial pointset, obtained numerically via alternating minimizations for efficiency and reliability. Key to our variational approach is the use of line processes to identify inliers vs. outliers, as well as the presence of sharp features. We demonstrate that our method can denoise sampled piecewise-smooth surfaces for levels of noise and outliers at which previous works fall short. CCS Concepts • Computing methodologies → Point-based models

We provide a semi-grammatical description of the set of normal proofs of positive formulae in minimal predicate logic, i.e. a grammar that generates a set of schemes, from each of which we can produce a finite number of normal proofs. This method is complete in the sense that each normal proof-term of the formula is produced by some scheme generated by the grammar. As a corollary, we get a similar description of the set of normal proofs of positive formulae for a large class of theories including simple type theory and System F.