Publications

2022

• Pulling, Pressing, and Sensing with In-Flat: Transparent Touch Overlay for Smartphones
  
  • Zhang Zhuoming
  • Alvina Jessalyn
  • Détienne Françoise
  • Lecolinet Eric
  , 2022, pp.1-9. (10.1145/3531073.3531111)
  DOI : 10.1145/3531073.3531111
• Autoregressive Moving Average Jointly-Diagonalizable Spatial Covariance Analysis for Joint Source Separation and Dereverberation
  
  • Sekiguchi Kouhei
  • Bando Yoshiaki
  • Nugraha Aditya Arie
  • Fontaine Mathieu
  • Yoshii Kazuyoshi
  • Kawahara Tatsuya
  IEEE/ACM Transactions on Audio, Speech and Language Processing, Institute of Electrical and Electronics Engineers, 2022, 30, pp.2368 - 2382. This article describes a computationally-efficient statistical approach to joint (semi-)blind source separation and dereverberation for multichannel noisy reverberant mixture signals. A standard approach to source separation is to formulate a generative model of a multichannel mixture spectrogram that consists of source and spatial models representing the time-frequency power spectral densities (PSDs) and spatial covariance matrices (SCMs) of source images, respectively, and find the maximum-likelihood estimates of these parameters. A state-of-the-art blind source separation method in this thread of research is fast multichannel nonnegative matrix factorization (FastMNMF) based on the lowrank PSDs and jointly-diagonalizable full-rank SCMs. To perform mutually-dependent separation and dereverberation jointly, in this paper we integrate both moving average (MA) and autoregressive (AR) models that represent the early reflections and late reverberations of sources, respectively, into the FastMNMF formalism. Using a pretrained deep generative model of speech PSDs as a source model, we realize semi-blind joint speech separation and dereverberation. We derive an iterative optimization algorithm based on iterative projection or iterative source steering for jointly and efficiently updating the AR parameters and the SCMs. Our experimental results showed the superiority of the proposed ARMA extension over its AR-or MA-ablated version in a speech separation and/or dereverberation task. (10.1109/taslp.2022.3190734)
  DOI : 10.1109/taslp.2022.3190734
• Revisiting Distributed Acoustic Sensing: A Telecom Approach Inspired from Optical Transmission
  
  • Dorize Christian
  • Guerrier Sterenn
  • Awwad Elie
  • Renaudier Jérémie
  , 2022. <jats:p>we review digital techniques used in transmission through telecom fibres and show they can be tailored to Distributed Acoustic Sensing (DAS), with key advantages in terms of noise floor and scalability to targeted applications.</jats:p> (10.1364/OFS.2022.Th4.7)
  DOI : 10.1364/OFS.2022.Th4.7
• Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems
  
  • Pethick Thomas
  • Latafat Puya
  • Patrinos Panagiotis
  • Fercoq Olivier
  • Cevher Volkan
  , 2022. This paper introduces a new extragradient-type algorithm for a class of nonconvex-nonconcave minimax problems. It is well-known that finding a local solution for general minimax problems is computationally intractable. This observation has recently motivated the study of structures sufficient for convergence of first order methods in the more general setting of variational inequalities when the so-called weak Minty variational inequality (MVI) holds. This problem class captures non-trivial structures as we demonstrate with examples, for which a large family of existing algorithms provably converge to limit cycles. Our results require a less restrictive parameter range in the weak MVI compared to what is previously known, thus extending the applicability of our scheme. The proposed algorithm is applicable to constrained and regularized problems, and involves an adaptive stepsize allowing for potentially larger stepsizes. Our scheme also converges globally even in settings where the underlying operator exhibits limit cycles. Moreover, a variant with stochastic oracles is proposed-making it directly relevant for training of generative adversarial networks. For the stochastic algorithm only one of the stepsizes is required to be diminishing while the other may remain constant, making it interesting even in the monotone setting.
• Advanced Fiber Sensing Leveraging Coherent Systems Technology for Smart Network Monitoring
  
  • Dorize Christian
  • Guerrier Sterenn
  • Awwad Elie
  • Benyahya Kaoutar
  • Mardoyan Haik
  • Renaudier Jérémie
  , 2022, pp.M2F.6. (10.1364/OFC.2022.M2F.6)
  DOI : 10.1364/OFC.2022.M2F.6
• Secure and Robust MIMO Transceiver for Multicast Mission Critical Communications
  
  • Jagyasi Deepa
  • Coupechoux Marceau
  IEEE Transactions on Vehicular Technology, Institute of Electrical and Electronics Engineers, 2022, 71 (6), pp.6351-6366. Mission-critical communications (MCC) involve all communications between people in charge of the safety of the civil society. MCC have unique requirements that include improved reliability, security and group communication support. In this paper, we propose secure and robust Multiple-Input-Multiple-Output (MIMO) transceivers, designed for multiple Base Stations (BS) supporting multicast MCC in presence of multiple eavesdroppers. We formulate minimization problems with the Sum-Mean-Square-Error (SMSE) at legitimate users as an objective function, and a lower bound for the MSE at eavesdroppers as a constraint. Security is achieved thanks to physical layer security mechanisms, namely MIMO beamforming and Artificial Noise (AN). Reliability is achieved by designing a system which is robust to two types of channel state information errors: stochastic and norm-bounded. We propose a coordinate descent-based algorithm and a worst-case iterative algorithm to solve these problems. Numerical results at physical layer and system level reveal the crucial role of robust designs for reliable MCC. We show the interest of both robust design and AN to improve the security gap. We also show that full BS cooperation in preferred for highly secured and reliable MCC but dynamic clustering allows to trade-off security and reliability against capacity. Index Terms-mission critical communication (MCC), physical layer security, robust transceiver design I. INTRODUCTION Mission critical communications (MCC) are all communications between people in charge of the security and the safety of the civil society. Employees of public safety services, like policemen, firemen, rescue teams and ambulance nurses, but also from large companies managing critical infrastructures in the energy or transportation sectors require MCC for their operations [1]. MCC are conveyed by dedicated Private Mobile Radio (PMR) networks [2] that offer a group (or multicast) communication service. This is a one-to-many or many-tomany communication [3], which is one of the most important features of PMR networks and is essential to manage teams of employees. In 5G New Radio, group communication will be supported for MCC from Release R17 onwards [4]. Due to the critical aspects of their missions, MCC users also inherently require highly reliable and secure communication. In particular, sensitive information should not leak to unintended receivers although the broadcast nature of the wireless channel makes the network vulnerable to malicious eavesdroppers. (10.1109/TVT.2022.3160348)
  DOI : 10.1109/TVT.2022.3160348
• On the decoding of lattices constructed via a single parity check
  
  • Corlay Vincent
  • Boutros Joseph J
  • Ciblat Philippe
  IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2022, 68 (5), pp.2951 - 2968. This paper investigates the decoding of a remarkable set of lattices: We treat in a unified framework the Leech lattice in dimension 24, the Nebe lattice in dimension 72, and the Barnes-Wall lattices. A new interesting lattice is constructed as a simple application of single parity-check principle on the Leech lattice. The common aspect of these lattices is that they can be obtained via a single parity check or via the king construction. We exploit these constructions to introduce a new efficient paradigm for decoding. This leads to efficient list decoders and quasi-optimal decoders on the Gaussian channel. Both theoretical and practical performance (point error probability and complexity) of the new decoders are provided. (10.1109/TIT.2022.3148196)
  DOI : 10.1109/TIT.2022.3148196
• Compositional Equivalences Based on Open pNets
  
  • Ameur-Boulifa Rabéa
  • Henrio Ludovic
  • Madelaine Eric
  Journal of Logical and Algebraic Methods in Programming, Elsevier, 2022, 131, pp.100842. Establishing equivalences between programs is crucial both for verifying correctness of programs and for justifying optimisations and program transformations. There exist several equivalence relations for programs, and bisimulations are among the most versatile of these equivalences. Among bisimulations one distinguishes strong bisimulation that requires that each action of a program is simulated by a single action of the equivalent program, and weak bisimulation that allows some of the actions to be invisible, and thus not simulated. pNet is a generalisation of automata that model open systems. They feature variables and hierarchical composition. Open pNets are pNets with holes, i.e. placeholders that can be filled later by subsystems. However, there is no standard tool for defining the semantics of an open system in this context. This article first defines open automata that are labelled transition systems with parameters and holes. Relying on open automata, it then defines bisimilarity relations for the comparison of systems specified as pNets. We first present a strong bisimilarity for open pNets called FH-bisimilarity. Next we offer an equivalence relation similar to the classical weak bisimulation equivalence, and study its properties. Among these properties we are interested in compositionality: if two systems are proven equivalent they will be indistinguishable by their context, and they will also be indistinguishable when their holes are filled with equivalent systems. We identify sufficient conditions to ensure compositionality of strong and weak bisimulation. The contributions of this article are illustrated using a transport protocol as running example. (10.1016/j.jlamp.2022.100842)
  DOI : 10.1016/j.jlamp.2022.100842
• Unsupervised Audio Source Separation Using Differentiable Parametric Source Models
  
  • Schulze-Forster Kilian
  • Doire Clement S J
  • Richard Gael
  • Badeau Roland
  Computing Research Repository, ACM / ArXiv, 2022. Supervised deep learning approaches to underdetermined audio source separation achieve state-of-the-art performance but require a dataset of mixtures along with their corresponding isolated source signals. Such datasets can be extremely costly to obtain for musical mixtures. This raises a need for unsupervised methods. We propose a novel unsupervised modelbased deep learning approach to musical source separation. Each source is modelled with a differentiable parametric sourcefilter model. A neural network is trained to reconstruct the observed mixture as a sum of the sources by estimating the source models' parameters given their fundamental frequencies. At test time, soft masks are obtained from the synthesized source signals. The experimental evaluation on a vocal ensemble separation task shows that the proposed method outperforms learning-free methods based on nonnegative matrix factorization and a supervised deep learning baseline. Integrating domain knowledge in the form of source models into a data-driven method leads to high data efficiency: the proposed approach achieves good separation quality even when trained on less than three minutes of audio. This work makes powerful deep learning based separation usable in scenarios where training data with ground truth is expensive or nonexistent.
• Introduction
  
  • Bloch Isabelle
  • Euzenat Jérôme
  • Lang Jérôme
  • Schwarzentruber François
  Revue Ouverte d'Intelligence Artificielle, Association pour la diffusion de la recherche francophone en intelligence artificielle, 2022, 3, pp.193-199. no abstract (10.5802/roia.28fr)
  DOI : 10.5802/roia.28fr
• Post-actes de la Conférence Nationale en Intelligence Artificielle (CNIA 2018-2020)
  
  • Bloch Isabelle
  • Euzenat Jérôme
  • Lang Jérôme
  • Schwarzentruber François
  Revue Ouverte d'Intelligence Artificielle, Association pour la diffusion de la recherche francophone en intelligence artificielle, 2022, 3, pp.193-413. no abstract
• High-capacity free-space optical link in the midinfrared thermal atmospheric windows using unipolar quantum devices
  
  • Didier Pierre
  • Dely Hamza
  • Bonazzi Thomas
  • Spitz Olivier
  • Awwad Elie
  • Rodriguez Étienne
  • Vasanelli Angela
  • Sirtori Carlo
  • Grillot Frédéric
  Advanced photonics, SPIE, 2022, 4 (5), pp.056004. Free-space optical communication is a very promising alternative to fiber communication systems, in terms of ease of deployment and costs. Midinfrared light has several features of utter relevance for free-space applications: low absorption when propagating in the atmosphere even under adverse conditions, robustness of the wavefront during long-distance propagation, and absence of regulations and restrictions for this range of wavelengths. A proof-of-concept of high-speed transmission taking advantage of intersubband devices has recently been demonstrated, but this effort was limited by the short-distance optical path (up to 1 m). In this work, we study the possibility of building a long-range link using unipolar quantum optoelectronics. Two different detectors are used: an uncooled quantum cascade detector and a nitrogen-cooled quantum well-infrared photodetector. We evaluate the maximum data rate of our link in a back-to-back configuration before adding a Herriott cell to increase the length of the light path up to 31 m. By using pulse shaping, pre- and post-processing, we reach a record bitrate of 30 Gbit s − 1 for both two-level (OOK) and four-level (PAM-4) modulation schemes for a 31-m propagation link and a bit error rate compatible with error-correction codes. (10.1117/1.AP.4.5.056004)
  DOI : 10.1117/1.AP.4.5.056004
• LAKE DETECTION WITH SENTINEL-1 DATA USING A GRAB-CUT METHOD AND ITS MULTI-TEMPORAL EXTENSION
  
  • Gasnier Nicolas
  • Denis Loïc
  • Fjørtoft Roger
  • Liege Frédéric
  • Tupin Florence
  , 2022. This paper presents a semi-guided method to detect lakes in Sentinel-1 SAR data. The proposed approach is an adaptation of the grab-cut framework developed in [1]. Starting from a coarse bounding box around the lake, an accurate segmentation is extracted using a Conditional Random Field formalism and a graph-cut based optimization. Then an extension of this approach to process jointly a stack of multi-temporal data is presented. A temporal regularization term is introduced to control the joint segmentation. The proposed approach is evaluated on Sentinel-1 datasets. Qualitative and quantitative results demonstrate the interest of the proposed framework and its robustness to the initialization polygon of the lake. (10.1109/IGARSS46834.2022.9883219)
  DOI : 10.1109/IGARSS46834.2022.9883219
• Combining Embeddings and Rules for Fact Prediction
  
  • Boschin Armand
  • Jain Nitisha
  • Keretchashvili Gurami
  • Suchanek Fabian M.
  , 2022. Knowledge bases are typically incomplete, meaning that they are missing information that we would expect to be there. Recent years have seen two main approaches to guess missing facts: Rule Mining and Knowledge Graph Embeddings. The first approach is symbolic, and finds rules such as "If two people are married, they most likely live in the same city". These rules can then be used to predict missing statements. Knowledge Graph Embeddings, on the other hand, are trained to predict missing facts for a knowledge base by mapping entities to a vector space. Each of these approaches has their strengths and weaknesses, and this article provides a survey of neuro-symbolic works that combine embeddings and rule mining approaches for fact prediction. (10.4230/OASIcs.AIB.2022.4)
  DOI : 10.4230/OASIcs.AIB.2022.4
• (Complex) natural gradient optimization for optical quantum circuit design
  
  • Yao Yuan
  • Cussenot Pierre
  • Wolf Richard A.
  • Miatto Filippo M.
  Physical Review A, American Physical Society, 2022, 105 (5), pp.052402. Few-mode optical quantum circuits can be simulated and optimized using gradient-descent methods, as optical gates can be parametrized by continuous parameters. However, the parameter space as seen by a nonholomorphic cost function is not Euclidean, which means that the Euclidean gradient does not generally point in the direction of steepest ascent. In order to retrieve the true steepest-ascent direction, one must take into account the local metric in what is known as the natural-gradient (NG) method. In this work we implement the NG for the optimization of optical quantum circuits. Specifically, we adapt the NG approach to a complex-valued parameter space, allowing us to apply the NG method directly within the Bargmann formalism, which we rely on for transforming between phase space and Fock space. We then compare the NG approach to vanilla gradient descent and to Adam over two standard state-preparation benchmarks: a single-photon source and a Gottesman-Kitaev-Preskill state source. We observe that the NG approach converges significantly faster (due in part to the possibility of using larger learning rates) and with a smoother decay of the cost function throughout the optimization. This result further improves our ability to design quantum circuits via classical optimization methods. (10.1103/PhysRevA.105.052402)
  DOI : 10.1103/PhysRevA.105.052402
• Handwriting and Drawing Features for Detecting Personality Traits: An Analysis on Big Five Sub-dimensions
  
  • Esposito Anna
  • Amorese Terry
  • Buonanno Michele
  • Cuciniello Marialucia
  • Esposito Antonietta
  • Faundez-Zanuy Marcos
  • Likforman-Sulem Laurence
  • Riviello Maria Teresa
  • Spagnuolo Carmine
  • Troncone Alda
  • Cordasco Gennaro
  Acta Polytechnica Hungarica, Óbuda University, 2022, 19 (11), pp.65-84. : Handwriting and Drawing are functional tasks involving physical and cognitive processes. Recently they have been investigated for detecting cognitive and motor disorders. In this work, handwriting/drawing features are investigated for identifying connections with personality traits. For this purpose, an experiment comprising seven handwriting/drawing tasks has been administrated to 78 young adults (mean age=24.6 ± 2.4 years) equally balanced by gender. Handwriting and Drawing activities - both on and close to the paper – had been recorded online through a digitizing tablet able to measure handwriting and drawing features such as pressure, speed, dimension, and inclination of each pen-stroke on the paper. Participants were asked to fill the Big Five Personality Questionnaire (BFQ) and according to the scores obtained for each of the 5 dimensions and 10 Big Five sub-dimensions, were partitioned into three categories: low, typical, and high. To evaluate whether the recorded handwriting/drawing features are connected with personality traits ANOVA repeated measures have been performed with gender and group category (low, typical, and high) as between and the listed handwriting/drawing features as within factors. The analyses show significant differences among low, typical and, high BFQ scores for the main Big Five dimensions and the ten Big Five sub-dimensions, indicating that personality traits can be revealed by a quantitative analysis of the proposed handwriting/drawing features. (10.12700/APH.19.11.2022.11.4)
  DOI : 10.12700/APH.19.11.2022.11.4
• Enhanced four-wave mixing dynamics in epitaxial quantum dot laser on silicon
  
  • Ding Shihao
  • Dong Bozhang
  • Chow Weng
  • Bowers John
  • Grillot Frédéric
  , 2022, pp.NpTh3D.1. The four-wave mixing conversion efficiency of quantum dot laser is much higher than that of quantum well. These results are important for self-mode-locked pulse production and high-bandwidth optical frequency comb generation. (10.1364/NP.2022.NpTh3D.1)
  DOI : 10.1364/NP.2022.NpTh3D.1
• A Quadrature Rule combining Control Variates and Adaptive Importance Sampling
  
  • Leluc Rémi
  • Portier François
  • Zhuman Aigerim
  • Segers Johan
  Advances in Neural Information Processing Systems, Morgan Kaufmann Publishers, 2022, 35, pp.11842--11853. Driven by several successful applications such as in stochastic gradient descent or in Bayesian computation, control variates have become a major tool for Monte Carlo integration. However, standard methods do not allow the distribution of the particles to evolve during the algorithm, as is the case in sequential simulation methods. Within the standard adaptive importance sampling framework, a simple weighted least squares approach is proposed to improve the procedure with control variates. The procedure takes the form of a quadrature rule with adapted quadrature weights to reflect the information brought in by the control variates. The quadrature points and weights do not depend on the integrand, a computational advantage in case of multiple integrands. Moreover, the target density needs to be known only up to a multiplicative constant. Our main result is a non-asymptotic bound on the probabilistic error of the procedure. The bound proves that for improving the estimate's accuracy, the benefits from adaptive importance sampling and control variates can be combined. The good behavior of the method is illustrated empirically on synthetic examples and real-world data for Bayesian linear regression.
• Selected Topics in Malliavin Calculus
  
  • Decreusefond Laurent
  , 2022, 10. (10.1007/978-3-031-01311-9)
  DOI : 10.1007/978-3-031-01311-9
• Towards Outdoor Electromagnetic Field Exposure Mapping Generation Using Conditional GANs
  
  • Mallik Mohammed
  • Tesfay Angesom Ataklity
  • Allaert Benjamin
  • Kassi Rédha
  • Egea-Lopez Esteban
  • Molina-Garcia-Pardo Jose-Maria
  • Wiart Joe
  • Gaillot Davy
  • Clavier Laurent
  Sensors, MDPI, 2022, 22 (24), pp.9643. With the ongoing fifth-generation cellular network (5G) deployment, electromagnetic field exposure has become a critical concern. However, measurements are scarce, and accurate electromagnetic field reconstruction in a geographic region remains challenging. This work proposes a conditional generative adversarial network to address this issue. The main objective is to reconstruct the electromagnetic field exposure map accurately according to the environment’s topology from a few sensors located in an outdoor urban environment. The model is trained to learn and estimate the propagation characteristics of the electromagnetic field according to the topology of a given environment. In addition, the conditional generative adversarial network-based electromagnetic field mapping is compared with simple kriging. Results show that the proposed method produces accurate estimates and is a promising solution for exposure map reconstruction. (10.3390/s22249643)
  DOI : 10.3390/s22249643
• New decoding techniques for modified product code used in critical applications
  
  • Freitas David C.C.
  • Marcon César
  • Silveira Jarbas A.N.
  • Naviner Lirida A.B.
  • Mota João C.M.
  Microelectronics Reliability, Elsevier, 2022, 128, pp.114444. The shrinking of memory devices increased the probability of system failures due to the higher sensitivity to electromagnetic radiation. Critical memory systems employ fault-tolerant techniques like Error Correction Code (ECC) to mitigate these failures. This work explores error correction techniques and algorithms employing the Line Product Code (LPC), a product-like ECC. We propose to decode LPC codewords using a single error correction algorithm (AlgSE) followed by a double error correction algorithm (AlgDE). Both algorithms explore the LPC characteristics to attain greater decoding efficiency. AlgSE is implemented with an iterative technique associated with a correction heuristic, while AlgDE is an innovative proposal that allows increasing correction effectiveness through the inference of errors. AlgDE allows increasing the efficiency of the LPC decoder significantly when used together with AlgSE. It corrects 100% of the cases up to three bitflips as well as 98% and 92%, respectively, for four and five upsets in exhaustive tests. Besides, we present tradeoffs concerning the error correction potential versus the costs of implementing the correction algorithms. (10.1016/j.microrel.2021.114444)
  DOI : 10.1016/j.microrel.2021.114444
• Generalized Fast Multichannel Nonnegative Matrix Factorization Based on Gaussian Scale Mixtures for Blind Source Separation
  
  • Fontaine Mathieu
  • Sekiguchi Kouhei
  • Nugraha Aditya
  • Bando Yoshiaki
  • Yoshii Kazuyoshi
  IEEE/ACM Transactions on Audio, Speech and Language Processing, Institute of Electrical and Electronics Engineers, 2022, pp.1-1. This paper describes heavy-tailed extensions of a state-of-the-art versatile blind source separation method called fast multichannel nonnegative matrix factorization (FastMNMF) from a unified point of view. The common way of deriving such an extension is to replace the multivariate complex Gaussian distribution in the likelihood function with its heavy-tailed generalization, e.g., the multivariate complex Student's t and leptokurtic generalized Gaussian distributions, and tailor-make the corresponding parameter optimization algorithm. Using a wider class of heavy-tailed distributions called a Gaussian scale mixture (GSM), i.e., a mixture of Gaussian distributions whose variances are perturbed by positive random scalars called impulse variables, we propose GSM-FastMNMF and develop an expectationmaximization algorithm that works even when the probability density function of the impulse variables have no analytical expressions. We show that existing heavy-tailed FastMNMF extensions are instances of GSM-FastMNMF and derive a new instance based on the generalized hyperbolic distribution that include the normal-inverse Gaussian, Student's t, and Gaussian distributions as the special cases. Our experiments show that the normalinverse Gaussian FastMNMF outperforms the state-of-the-art FastMNMF extensions and ILRMA model in speech enhancement and separation in terms of the signal-to-distortion ratio. (10.1109/TASLP.2022.3172631)
  DOI : 10.1109/TASLP.2022.3172631
• Reasoning about Moving Target Defense in Attack Modeling Formalisms
  
  • Ballot Gabriel
  • Malvone Vadim
  • Leneutre Jean
  • Borde Etienne
  , 2022. Since 2009, Moving Target Defense (MTD) has become a new paradigm of defensive mechanism that frequently changes the state of the target system to confuse the attacker. This frequent change is costly and leads to a trade-off between misleading the attacker and disrupting the quality of service. Optimizing the MTD activation frequency is necessary to develop this defense mechanism when facing realistic, multi-step attack scenarios. Attack modeling formalisms based on DAG are prominently used to specify these scenarios. Our contribution is a new DAG-based formalism for MTDs and its translation into a Price Timed Markov Decision Process to find the best activation frequencies against the attacker's time/cost-optimal strategies. For the first time, MTD activation frequencies are analyzed in a state-of-the-art DAG-based representation. Moreover, this is the first paper that considers the specificity of MTDs in the automatic analysis of attack modeling formalisms. Finally, we present some experimental results using Uppaal Stratego to demonstrate its applicability and relevance.
• Uniform Reliability of Self-Join-Free Conjunctive Queries
  
  • Amarilli Antoine
  • Kimelfeld Benny
  Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2022. The reliability of a Boolean Conjunctive Query (CQ) over a tuple-independent probabilistic database is the probability that the CQ is satisfied when the tuples of the database are sampled one by one, independently, with their associated probability. For queries without self-joins (repeated relation symbols), the data complexity of this problem is fully characterized by a known dichotomy: reliability can be computed in polynomial time for hierarchical queries, and is #P-hard for non-hierarchical queries. Inspired by this dichotomy, we investigate a fundamental counting problem for CQs without self-joins: how many sets of facts from the input database satisfy the query? This is equivalent to the uniform case of the query reliability problem, where the probability of every tuple is required to be 1/2. Of course, for hierarchical queries, uniform reliability is solvable in polynomial time, like the reliability problem. We show that being hierarchical is also necessary for this tractability (under conventional complexity assumptions). In fact, we establish a generalization of the dichotomy that covers every restricted case of reliability in which the probabilities of tuples are determined by their relation. (10.46298/lmcs-18(4:3)2022)
  DOI : 10.46298/lmcs-18(4:3)2022
• Some Rainbow Problems in Graphs Have Complexity Equivalent to Satisfiability Problems
  
  • Hudry Olivier
  • Lobstein Antoine
  International Transactions in Operational Research, Wiley, 2022, 29 (3), pp.1547-1572. In a vertex-coloured graph, a set of vertices S is said to be a rainbow set if every colour in the graph appears exactly once in S. We investigate the complexities of various problems dealing with domination in vertex-coloured graphs (existence of rainbow dominating sets, of rainbow locating-dominating sets, of rainbow identifying sets), including when we ask for a unique solution: we show equivalence between these complexities and those of the well-studied Boolean satisfiability problems. (10.1111/itor.12847)
  DOI : 10.1111/itor.12847