Japanese-French Laboratory for Informatics

This paper presents a method to automatically and efficiently detect face tampering in videos, and particularly focuses on two recent techniques used to generate hyper-realistic forged videos: Deepfake and Face2Face. Traditional image forensics techniques are usually not well suited to videos due to the compression that strongly degrades the data. Thus, this paper follows a deep learning approach and presents two networks, both with a low number of layers to focus on the mesoscopic properties of images. We evaluate those fast networks on both an existing dataset and a dataset we have constituted from online videos. The tests demonstrate a very successful detection rate with more than 98% for Deepfake and 95% for Face2Face.

In the mid 1990s, it was shown that the statistics of aggregated time series from Internet traffic departed from those of traditional short range-dependent models, and were instead characterized by asymptotic self-similarity. Following this seminal contribution, over the years, many studies have investigated the existence and form of scaling in Internet traffic. This contribution first aims at presenting a methodology, combining multiscale analysis (wavelet and wavelet leaders) and random projections (or sketches), permitting a precise, efficient and robust characterization of scaling, which is capable of seeing through non-stationary anomalies. Second, we apply the methodology to a data set spanning an unusually long period: 14 years, from the MAWI traffic archive, thereby allowing an in-depth longitudinal analysis of the form, nature, and evolutions of scaling in Internet traffic, as well as network mechanisms producing them. We also study a separate three-day long trace to obtain complementary insight into intra-day behavior. We find that a biscaling (two ranges of independent scaling phenomena) regime is systematically observed: long-range dependence over the large scales, and multifractallike scaling over the fine scales. We quantify the actual scaling ranges precisely, verify to high accuracy the expected relationship between the long range dependent parameter and the heavy tail parameter of the flow size distribution, and relate fine scale multifractal scaling to typical IP packet inter-arrival and to round-trip time distributions.

Discriminating between computer-generated images (CGIs) and photographic images (PIs) is not a new problem in digital image forensics. However, with advances in rendering techniques supported by strong hardware and in generative adversarial networks, CGIs are becoming indistinguishable from PIs in both human and computer perception. This means that malicious actors can use CGIs for spoofing facial authentication systems, impersonating other people, and creating fake news to be spread on social networks. The methods developed for discriminating between CGIs and PIs quickly become outdated and must be regularly enhanced to be able to reduce these attack surfaces. Leveraging recent advances in deep convolutional networks, we have built a modular CGI--PI discriminator with a customized VGG-19 network as the feature extractor, statistical convolutional neural networks as the feature transformers, and a discriminator. We also devised a probabilistic patch aggregation strategy to deal with high-resolution images. This proposed method outperformed a state-of-the-art method and achieved accuracy up to 100%.

We derive a theoretical framework for the experimental certification of non-Gaussian features of quantum states using double homodyne detection. We rank experimental non-Gaussian states according to the recently defined stellar hierarchy and we propose practical Wigner negativity witnesses. We simulate various use-cases ranging from fidelity estimation to witnessing Wigner negativity. Moreover, we extend results on the robustness of the stellar hierarchy of non-Gaussian states. Our results illustrate the usefulness of double homodyne detection as a practical measurement scheme for retrieving information about continuous-variable quantum states, and show that certification of high-order non-Gaussian features can be carried out experimentally with current technology.

Crystals arise as the result of the breaking of a spatial translation symmetry. Similarly, translation symmetries can also be broken in time so that discrete time crystals appear. Here, we introduce a method to describe, characterize, and explore the physical phenomena related to this phase of matter using tools from graph theory. The analysis of the graphs allows to visualizing time-crystalline order and to analyze features of the quantum system. For example, we explore in detail the melting process of a minimal model of a period-2 discrete time crystal and describe it in terms of the evolution of the associated graph structure. We show that during the melting process, the network evolution exhibits an emergent preferential attachment mechanism, directly associated with the existence of scale-free networks. Thus, our strategy allows us to propose a previously unexplored far-reaching application of time crystals as a quantum simulator of complex quantum networks.

Abstract A multiplex network has links of different types, allowing it to express many overlapping types of relationships. A core task in network analysis is to evaluate and understand group cohesion; that is, to explain why groups of elements belong together based on the underlying structure of the network. We present Detangler, a system that supports visual analysis of group cohesion in multiplex networks through dual linked views. These views feature new data abstractions derived from the original multiplex network: the substrate network and the catalyst network. We contribute two novel techniques that allow the user to analyze the complex structure of the multiplex network without the extreme visual clutter that would result from simply showing it directly. The harmonized layout visual encoding technique provides spatial stability between the substrate and catalyst views. The pivot brushing interaction technique supports linked highlighting between the views based on computations in the underlying multiplex network to leapfrog between subsets of catalysts and substrates. We present results from the motivating application domain of annotated news documents with a usage scenario and preliminary expert feedback. A second usage scenario presents group cohesion analysis of the social network of the early American independence movement.

The rich nature of news makes it a classic subject of visual analytics research. Such analysis is often based on rich textual data. However, we want to test how much we can understand the news from video information through face detection and tracking. Towards this goal, we propose a visual analytics system and discuss its design and implementation to support media experts in understanding political interactions in an archive of 12 years of the Japanese public broadcaster NHK's News 7 program. After identifying the tasks and abstraction required for our analysis, we construct links from face detection and tracking to derive multiple political networks. Our proposed design embeds this rich data into a visual analytics framework that presents four levels of abstraction: time period, network, timeline, and face-tracks within video. We present how the exploration of the archive with our system results in good understanding of the Japanese politico-media scene during these 12 years while finding evidence of “presidentialization” of the media.

We consider Gaussian quantum circuits supplemented with non-Gaussian input states and derive sufficient conditions for efficient classical strong simulation of these circuits. In particular, we generalise the stellar representation of continuous-variable quantum states to the multimode setting and relate the stellar rank of the input non-Gaussian states, a recently introduced measure of non-Gaussianity, to the cost of evaluating classically the output probability densities of these circuits. Our results have consequences for the strong simulability of a large class of near-term continuous-variable quantum circuits.

Thermal imaging has become a valuable tool in various fields for remote sensing and can provide relevant information to perform object recognition or classification. In this paper, we present an automated method to obtain a 3D model fusing data from a visible and a thermal camera. The RGB and thermal point clouds are generated independently by structure from motion. The registration process includes a normalization of the point cloud scale, a global registration based on calibration data and the output of the structure from motion, and a fine registration employing a variant of the Iterative Closest Point optimization. Experimental results demonstrate the accuracy and robustness of the overall process.

We study supervised learning algorithms in which a quantum device is used to perform a computational subroutine – either for prediction via probability estimation, or to compute a kernel via estimation of quantum states overlap. We design implementations of these quantum subroutines using Boson Sampling architectures in linear optics, supplemented by adaptive measurements. We then challenge these quantum algorithms by deriving classical simulation algorithms for the tasks of output probability estimation and overlap estimation. We obtain different classical simulability regimes for these two computational tasks in terms of the number of adaptive measurements and input photons. In both cases, our results set explicit limits to the range of parameters for which a quantum advantage can be envisaged with adaptive linear optics compared to classical machine learning algorithms: we show that the number of input photons and the number of adaptive measurements cannot be simultaneously small compared to the number of modes. Interestingly, our analysis leaves open the possibility of a near-term quantum advantage with a single adaptive measurement.

Gradient-domain rendering can improve the convergence of surface-based light transport by exploiting smoothness in image space. Scenes with participating media exhibit similar smoothness and could potentially benefit from gradient-domain techniques. We introduce the first gradient-domain formulation of image synthesis with homogeneous participating media, including four novel and efficient gradient-domain volumetric density estimation algorithms. We show that naïve extensions of gradient domain path-space and density estimation methods to volumetric media, while functional, can result in inefficient estimators. Focussing on point-, beam- and plane-based gradient-domain estimators, we introduce a novel shift mapping that eliminates redundancies in the naïve formulations using spatial relaxation within the volume. We show that gradient-domain volumetric rendering improve convergence compared to primal domain state-of-the-art, across a suite of scenes. Our formulation and algorithms support progressive estimation and are easy to incorporate atop existing renderers.

Monitoring delays in the Internet is essential to understand the network condition and ensure the good functioning of time-sensitive applications. Large-scale measurements of round-trip time (RTT) are promising data sources to gain better insights into Internet-wide delays. However, the lack of efficient methodology to model RTTs prevents researchers from leveraging the value of these datasets. In this work, we propose a log-normal mixture model to identify, characterize, and monitor spatial and temporal dynamics of RTTs. This data-driven approach provides a coarse grained view of numerous RTTs in the form of a graph, thus, it enables efficient and systematic analysis of Internet-wide measurements. Using this model, we analyze more than 13 years of RTTs from about 12 millions unique IP addresses in passively measured backbone traffic traces. We evaluate the proposed method by comparison with external data sets, and present examples where the proposed model highlights interesting delay fluctuations due to route changes or congestion. We also introduce an application based on the proposed model to identify hosts deviating from their typical RTTs fluctuations, and we envision various applications for this empirical model.

Multi-view dynamic three-dimensional reconstruction has typically required the use of custom shutter-synchronized camera rigs in order to capture scenes containing rapid movements or complex topology changes. In this paper, we demonstrate that multiple unsynchronized low-cost RGB-D cameras can be used for the same purpose. To alleviate issues caused by unsynchronized shutters, we propose a novel depth frame interpolation technique that allows synchronized data capture from highly dynamic 3D scenes. To manage the resulting huge number of input depth images, we also introduce an efficient moving least squares-based volumetric reconstruction method that generates triangle meshes of the scene. Our approach does not store the reconstruction volume in memory, making it memory-efficient and scalable to large scenes. Our implementation is completely GPU based and works in real time. The results shown herein, obtained with real data, demonstrate the effectiveness of our proposed method and its advantages compared to state-of-the-art approaches.

Abstract Noise is the greatest obstacle in quantum metrology that limits it achievable precision and sensitivity. There are many techniques to mitigate the effect of noise, but this can never be done completely. One commonly proposed technique is to repeatedly apply quantum error correction. Unfortunately, the required repetition frequency needed to recover the Heisenberg limit is unachievable with the existing quantum technologies. In this article we explore the discrete application of quantum error correction with current technological limitations in mind. We establish that quantum error correction can be beneficial and highlight the factors which need to be improved so one can reliably reach the Heisenberg limit level precision.

This paper presents GHOST, a combinatorial optimization framework that a real-time strategy (RTS) AI developer can use to model and solve any problem encoded as a constraint satisfaction/optimization problem (CSP/COP). We show a way to model three different problems as a CSP/COP, using instances from the RTS game StarCraft as test beds. Each problem belongs to a specific level of abstraction (the target selection as reactive control problem, the wall-in as a tactics problem, and the build order planning as a strategy problem). In our experiments, GHOST shows good results computed within some tens of milliseconds. We also show that GHOST outperforms state-of-the-art constraint solvers, matching them on the resources allocation problem, a common combinatorial optimization problem.

We introduce a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">goal-aware</i> extension of responsibility-sensitive safety (RSS), a recent methodology for rule-based safety guarantee for automated driving systems (ADS). Making RSS rules guarantee goal achievement—in addition to collision avoidance as in the original RSS—requires complex planning over long sequences of manoeuvres. To deal with the complexity, we introduce a compositional reasoning framework based on program logic, in which one can systematically develop RSS rules for smaller subscenarios and combine them to obtain RSS rules for bigger scenarios. As the basis of the framework, we introduce a program logic <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\text{dFHL}$</tex-math></inline-formula> that accommodates continuous dynamics and safety conditions. Our framework presents a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\text{dFHL}$</tex-math></inline-formula> -based workflow for deriving goal-aware RSS rules; we discuss its software support, too. We conducted experimental evaluation using RSS rules in a safety architecture. Its results show that goal-aware RSS is indeed effective in realising both collision avoidance and goal achievement.

QUBO is the input language of quantum computers based on quantum annealing such as the D-Wave systems and of the "quantum-inspired" dedicated hardware such as Fujitsu’s Digital Annealing Unit. We propose a new way to represent integer variables in QUBO together with constraints on those variables by using unary/domain-wall encoding in order to solve constrained optimization problem by quantum annealing. We detail in particular how to encode permutation constraints on integers within the unary/domain-wall encoding scheme, as these constraints are omnipresent in complex combinatorial problems. This new encoding in QUBO is interesting in the context of quantum annealing because it minimizes interactions between variables, and therefore connections needed between qubits in hardware. When compared to the usual one-hot encoding of integers in QUBO, we show than the new encoding scheme divides by nearly a factor 2 the number of connections between qubits for complex problems involving permutation constraints and makes it possible to cope with larger problem instances on current quantum and quantum-inspired hardware.

Graph states are a large class of multipartite entangled quantum states that form the basis of schemes for quantum computation, communication, error correction, metrology, and more. In this work, we consider verification of graph states generated by an untrusted source and shared between a network of possibly dishonest parties. This has implications in certifying the application of graph states for various distributed tasks. We present a protocol which is globally efficient for a large family of useful graph states, including cluster states, GHZ states, cycle graph states, and more. For general graph states, efficiency with respect to the security parameter is maintained, though there is a cost increase with the size of the graph state. The protocols are practical, requiring only multiple copies of the graph state, local measurements, and classical communication.

There is a well-known asymptotic formula, due to W. M. Schmidt [Duke Math. J., 35 (1968), pp. 327--339], for the number of full-rank integer lattices of index at most $V$ in ${\mathbb{Z}}^n$. This set of lattices $L$ can naturally be partitioned with respect to the factor group ${\mathbb{Z}}^n/L$. Accordingly, we count the number of full-rank integer lattices $L \subseteq {\mathbb{Z}}^n$ such that ${\mathbb{Z}}^n/L$ is cyclic and of order at most $V$, and deduce that these co-cyclic lattices are dominant among all integer lattices: their natural density is $(\zeta(6) \prod_{k=4}^n \zeta(k))^{-1} \approx 85\%$. The problem is motivated by complexity theory, namely worst-case to average-case reductions for lattice problems.

Anytime algorithms for optimization problems are of particular interest since they allow to trade off execution time with result quality. However, the selection of the best anytime algorithm for a given problem instance has been focused on a particular budget for execution time or particular target result quality. Moreover, it is often assumed that these anytime preferences are known when developing or training the algorithm selection methodology. In this work, we study the algorithm selection problem in a context where the decision maker's anytime preferences are defined by a general utility function, and only known at the time of selection. To this end, we first examine how to measure the performance of an anytime algorithm with respect to this utility function. Then, we discuss approaches for the development of selection methodologies that receive a utility function as an argument at the time of selection. Then, to illustrate one of the discussed approaches, we present a preliminary study on the selection between an exact and a heuristic algorithm for a bi-objective knapsack problem. The results show that the proposed methodology has an accuracy greater than 96% in the selected scenarios, but we identify room for improvement.