Publications

2020

• New characterizations and construction methods of bent and hyper-bent Boolean functions
  
  • Mesnager Sihem
  • Mandal B.
  • Tang C.
  Discrete Mathematics, Elsevier, 2020.
• KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs
  
  • Sun Bintao
  • Danisch Maximilien
  • Chan T-H Hubert
  • Sozio Mauro
  Proceedings of the VLDB Endowment (PVLDB), VLDB Endowment, 2020. The problem of finding densest subgraphs has received increasing attention in recent years finding applications in biology , finance, as well as social network analysis. The k-clique densest subgraph problem is a generalization of the densest subgraph problem, where the objective is to find a subgraph maximizing the ratio between the number of k-cliques in the subgraph and its number of nodes. It includes as a special case the problem of finding subgraphs with largest average number of triangles (k = 3), which plays an important role in social network analysis. Moreover, algorithms that deal with larger values of k can effectively find quasi-cliques. The densest subgraph problem can be solved in polynomial time with algorithms based on maximum flow, linear programming or a recent approach based on convex optimization. In particular, the latter approach can scale to graphs containing tens of billions of edges. While finding a densest subgraph in large graphs is no longer a bottleneck , the k-clique densest subgraph remains challenging even when k = 3. Our work aims at developing near-optimal and exact algorithms for the k-clique densest subgraph problem on large real-world graphs. We give a surprisingly simple procedure that can be employed to find the maximal k-clique densest subgraph in large-real world graphs. By leveraging appealing properties of existing results, we combine it with a recent approach for listing all k-cliques in a graph and a sampling scheme, obtaining the state-of-the-art approaches for the aforementioned problem. Our theoretical results are complemented with an extensive experimental evaluation showing the effectiveness of our approach in large real-world graphs.
• SENSITIVITY ANALYSIS FOR STOCHASTIC SIMULATORS USING DIFFERENTIAL ENTROPY
  
  • Azzi Soumaya
  • Sudret Bruno
  • Wiart Joe
  International Journal for Uncertainty Quantification, Begell House Publishers, 2020, 10 (1), pp.25-33. (10.1615/Int.J.UncertaintyQuantification.2020031610)
  DOI : 10.1615/Int.J.UncertaintyQuantification.2020031610
• Solving $x^{2^k+1}+x+a=0$ in $\mathbb{F}_{2^n}$ with $\gcd(n,k)=1$
  
  • Kim K. H.
  • Mesnager Sihem
  Finite Fields and Their Applications, Elsevier, 2020.
• Several classes of minimal linear codes with few weights from weakly regular plateaued function
  
  • Mesnager Sihem
  • Sinak A.
  IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2020.
• A Fully Connected Neural Network to Mitigate 200G DP-16-QAM Transmission System Impairments
  
  • Catanese Clara
  • Ayassi Reda
  • Pincemin Erwan
  • Jaouën Yves
  , 2020, pp.SpTh3I.1. (10.1364/SPPCOM.2020.SpTh3I.1)
  DOI : 10.1364/SPPCOM.2020.SpTh3I.1
• Explicit Regularisation in Gaussian Noise Injections
  
  • Camuto Alexander
  • Willetts Matthew
  • Şimşekli Umut
  • Roberts Stephen
  • Holmes Chris
  , 2020. We study the regularisation induced in neural networks by Gaussian noise injections (GNIs). Though such injections have been extensively studied when applied to data, there have been few studies on understanding the regularising effect they induce when applied to network activations. Here we derive the explicit regulariser of GNIs, obtained by marginalising out the injected noise, and show that it penalises functions with high-frequency components in the Fourier domain; particularly in layers closer to a neural network's output. We show analytically and empirically that such regularisation produces calibrated classifiers with large classification margins.
• Motion Correction for brain PET using a Real Time Motion Capture System
  
  • Chemli Y.
  • Tétrault M.-A.
  • Marin T.
  • Toussaint M.
  • Bloch Isabelle
  • El Fakhri G.
  • Normandin M.
  • Ouyang J.
  • Petibon Y.
  , 2020.
• MR based PET motion correction for irregular respiratory motion
  
  • Djebra Y.
  • Marin T.
  • Han P.
  • Chemli Y.
  • Bloch Isabelle
  • El Fakhri G.
  • Ouyang J.
  • Petibon Y.
  • Ma C.
  , 2020.
• Advanced Optical Communications and Networking
  
  • Gallion Philippe
  Proceeding of International Conference on Optical & Wireless Technologies , OWT 2019, 2020, Éditeurs : Ghanshyam Singh, Manish Tiwari, Tawfik Ismail, Vijay Janyani.
• New Characterizations for the Multi-output Correlation- Immune Boolean Functions
  
  • Chai J.
  • Mesnager Sihem
  • Wang Z.
  Discrete Mathematics, Elsevier, 2020.
• A new parametrization for the Rician distribution
  
  • Nicolas Jean Marie
  • Tupin Florence
  IEEE Geoscience and Remote Sensing Letters, IEEE - Institute of Electrical and Electronics Engineers, 2020. The Rician distribution is widely used in SAR imagery to model the backscattering of a strong target inside a resolution cell. Nevertheless the computation of the parameters of the Rice distribution remains a difficult task. In this paper, a new parametrization to model the Rice distribution is introduced. Thanks to the introduction of a new variable defined by the ratio of the target contribution to the speckle, the relationship between the coefficient of variation and this new parameter can be derived. An efficient numerical method is proposed to evaluate it from the coefficient of variation and a discussion on the variance of this estimator is led. A comparison with other methods of estimation showed that the proposed approach is a good compromise between the variance of the estimate and the computation time. At last, a link between permanent scatterers and Rice distributed targets is proposed through this new parametrization. (10.1109/LGRS.2019.2957240)
  DOI : 10.1109/LGRS.2019.2957240
• Resolution of a Routing and Wavelength Assignment Problem by Independent Sets in Conflict Graphs
  
  • Hudry Olivier
  , 2020.
• Popularity-Based Full Replica Caching For Erasure-Coded Distributed Storage Systems
  
  • Ruty Guillaume
  • Baccouch Hana
  • Nguyen Victor
  • Surcouf André
  • Rougier Jean Louis
  • Boukhatem Nadia
  Cluster Computing, Springer Verlag, 2020.
• Ultra-flat supercontinuum from 1.95 to 2.65 µm in a nanosecond pulsed Thulium-doped fiber laser
  
  • Romano Clément
  • Jaouën Yves
  • Tench Robert E
  • Delavaux Jean-Marc
  Optical Fiber Technology, Elsevier, 2020, 54, pp.102113. (10.1016/j.yofte.2019.102113)
  DOI : 10.1016/j.yofte.2019.102113
• Query Rewriting On Path Views Without Integrity Constraints
  
  • Romero Julien
  • Preda Nicoleta
  • Suchanek Fabian
  , 2020. A view with a binding pattern is a parameterised query on a database. Such views are used, e.g., to model Web services. To answer a query on such views, one has to orchestrate the views together in execution plans. The goal is usually to nd equivalent rewritings, which deliver precisely the same results as the query on all databases. However, such rewritings are usually possible only in the presence of integrity constraints and not all databases have such constraints. In this paper, we describe a class of plans that give practical guarantees about their result even if there are no integrity constraints. We provide a characterisation of such plans and a complete and correct algorithm to enumerate them. Finally, we show that our method can nd plans on real-world Web Services.
• Analyse de représentations spatiales de la musique par des opérateurs simples de morphologie mathématique
  
  • Lascabettes P.
  • Bloch Isabelle
  • Agon C.
  , 2020.
• The POTUS Corpus, a database of weekly addresses for the study of stance in politics and virtual agents
  
  • Janssoone Thomas
  • Bailly Kevin
  • Richard Gael
  • Clavel Chloé
  , 2020, pp.11 - 16. One of the main challenges in the field of Embodied Conversational Agent (ECA) is to generate socially believable agents. The common strategy for agent behaviour synthesis is to rely on dedicated corpus analysis. Such a corpus is composed of multimedia files of socio-emotional behaviors which have been annotated by external observers. The underlying idea is to identify interaction information for the agent's socio-emotional behavior by checking whether the intended socio-emotional behavior is actually perceived by humans. Then, the annotations can be used as learning classes for machine learning algorithms applied to the social signals. This paper introduces the POTUS Corpus composed of high-quality audio-video files of political addresses to the American people. Two protagonists are present in this database. First, it includes speeches of former president Barack Obama to the American people. Secondly, it provides videos of these same speeches given by a virtual agent named Rodrigue. The ECA reproduces the original address as closely as possible using social signals automatically extracted from the original one. Both are annotated for social attitudes, providing information about the stance observed in each file. It also provides the social signals automatically extracted from Obama's addresses used to generate Rodrigue's ones.
• On the number of the rational zeros of linearized polynomials and the second-order nonlinearity of cubic Boolean functions.
  
  • Mesnager Sihem
  • Kim K.H.
  • Jo. M.S.
  Cryptography and Communications- Discrete Structures, Boolean Functions, and Sequences (CCDS),, 2020.
• Monadic Datalog, Tree Validity, and Limited Access Containment
  
  • Benedikt Michael
  • Bourhis Pierre
  • Gottlob Georg
  • Senellart Pierre
  ACM Transactions on Computational Logic, Association for Computing Machinery, 2020, 21 (1), pp.6:1-6:45. We reconsider the problem of containment of monadic datalog (MDL) queries in unions of conjunctive queries (UCQs). Prior work has dealt with special cases of the problem, but has left the precise complexity characterization open. In addition, the complexity of one important special case, that of containment under access patterns, was not known before. We start by revisiting the connection between MDL/UCQ containment and containment problems involving regular tree languages. We then present a general approach for getting tighter bounds on the complexity of query containment, based on analysis of the number of mappings of queries into tree-like instances. We give two applications of the machinery. We first give an important special case of the MDL/UCQ containment problem that is in EXPTIME, and use this bound to show an EXPTIME bound on containment under access patterns. Secondly we show that the same technique can be used to get a new tight upper bound for containment of tree automata in UCQs. We finally show that the new MDL/UCQ upper bounds are tight. We establish a 2EXPTIME lower bound on the MDL/UCQ containment problem, resolving an open problem from the early 1990s. This bound holds for the MDL/CQ containment problem as well. We also show that changes to the conditions given in our special cases can not be eliminated, and that in particular slight variations of the problem of containment under access patterns become 2EXPTIME-complete. (10.1145/3344514)
  DOI : 10.1145/3344514
• A Fundamental Storage-Communication Tradeoff for Distributed Computing with Straggling Nodes
  
  • Yan Qifa
  • Wigger Michèle
  • Yang Sheng
  • Tang Xiaohu
  IEEE Transactions on Communications, Institute of Electrical and Electronics Engineers, 2020. Placement delivery arrays for distributed computing (Comp-PDAs) have recently been proposed as a framework to construct universal computing schemes for MapReduce-like systems. In this work, we extend this concept to systems with straggling nodes, i.e., to systems where a subset of the nodes cannot accomplish the assigned map computations in due time. Unlike most previous works that focused on computing linear functions, our results are universal and apply for arbitrary map and reduce functions. Our contributions are as follows. Firstly, we show how to construct a universal coded computing scheme for MapReduce-like systems with straggling nodes from any given Comp-PDA. We also characterize the storage and communication loads of the resulting scheme in terms of the Comp-PDA parameters. Then, we prove an information-theoretic converse bound on the storage-communication (SC) tradeoff achieved by universal computing schemes with straggling nodes. We show that the information-theoretic bound matches the performance achieved by the coded computing schemes with straggling nodes corresponding to the Maddah-Ali and Niesen (MAN) PDAs, i.e., to the Comp-PDAs describing Maddah-Ali and Niesen's coded caching scheme. Interestingly, the MAN-PDAs are optimal for any number of straggling nodes. This implies that the map phase of optimal coded computing schemes does not need to be adapted to the number of stragglers in the system. We show that the points that lie exactly on the fundamental SC tradeoff cannot be achieved with Comp-PDAs that require smaller number of files than the MAN-PDAs. This is however possible for some of the points that lie close to the SC tradeoff. For these latter points, the decrease in the requested number of files can be exponential in the number of nodes of the system. We also model the total execution time, and numerically show that the active set size should be chosen to balance the duration of the map phase and the durations of the shuffle and reduce phases. (10.1109/TCOMM.2020.3020549)
  DOI : 10.1109/TCOMM.2020.3020549
• A Proof of the Beierle-Kranz-Leander Conjecture related to Lightweight Multiplication in $F_2^n$
  
  • Mesnager Sihem
  • Kim K. H.
  • Jo D.
  • Choe J.
  • Han M.
  • Lee D. N.
  Journal of Designs, Codes, and Cryptography, 2020.
• Low Complexity MIMO Detection for CDL Mitigation in Multi-Core Fiber Transmission
  
  • Abouseif Akram
  • Rekaya-Ben Othman Ghaya
  • Jaouën Yves
  , 2020.
• Multimodal Analysis of Cohesion in Multi-party Interactions
  
  • B Kantharaju Reshmashree
  • Langlet Caroline
  • Barange Mukesh
  • Clavel Chloé
  • Pelachaud Catherine I
  , 2020. Group cohesion is an emergent phenomenon that describes the tendency of the group members' shared commitment to group tasks and the interpersonal attraction among them. This paper presents a multimodal analysis of group cohesion using a corpus of multi-party interactions. 16 two-minute segments annotated with cohesion data is used. We define three layers of modalities: non-verbal social cues, dialogue acts and interruptions. The initial analysis is performed at the individual level and later, we combine the different modalities to observe their impact on perceived level of cohesion. Results indicate that occurrence of laughter and interruption are higher in high cohesive segments. We also observed that, dialogue acts and head nods did not have an impact on the level of cohesion by itself. However, when combined there was an impact on the perceived level of cohesion. Overall, the analysis shows that multimodal cues are crucial for accurate analysis of group cohesion.
• A Model-Based Combination Language for Scheduling Verification
  
  • Zhao Hui
  • Apvrille Ludovic
  • Mallet Frédéric
  , 2020. Cyber-Physical Systems (CPSs) are built upon discrete software and hardware components, as well as continuous physical components. Such heterogeneous systems involve numerous domains with competencies and expertise that go far beyond traditional software engineering: systems engineering. In this paper , we explore a model-based approach for systems engineering that advocates the composition of several heterogeneous artifacts (called views) into a sound and consistent system model. A model combination Language is proposed for this purpose. Thus, rather than trying to build the universal language able to capture all possible aspects of systems, the proposed language proposes to relate small subsets of languages in order to offer specific analysis capabilities while keeping a global consistency between all joined models. We demonstrate the interest of our approach through an industrial process based on Capella, which provides (among others) a large support for functional analysis from requirements to components deployment. Even though Capella is already quite expressive, it lacks support for schedulability analysis. AADL is also a language dedicated to system analysis. If it is backed with advanced schedulability tools, it lacks support for functional analysis. Thus, instead of proposing ways to add missing aspects in either Capella or AADL, we rather extract a relevant subset of both languages to build a view adequate for conducting schedulability analysis of Capella functional models. Finally, our combination language is generic enough to extract pertinent subsets of languages and combine them to build views for different experts. It also helps maintaining a global consistency between different modeling views.