In this document, most readers should be easily introduced to the challengesoffered to a designer, an implementer and a user when using electronic voting.Some of these challenges are receiving an answer in the second part of thedocument where we introduce and describe several distinct scientific resultsobtained during our years as PhD student covering essentially the years 2009 to2011 included. All these results are aimed towards either better understandingthe issues of electronic voting or solving them. Nonetheless, a reader might beinterested in picking one of these contributions to use for his own electronicvoting system while leaving the rest. That is, the different chapters of thesecond part of the document are able to stand on their own most of the timeand could be used without the others which leads us to introduce each of themseparately.After concluding in the third part, we provide a certain amount of appendicesthat were not thoroughly discussed within the second part of the documentbut that might be of interest to the reader. These appendices are made ofvarious researches, collaborations and analyzes that we performed during thosesame years and which are related to electronic voting. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Billions of dollars of loss are caused every year by fraudulent credit card transactions. The design of efficient fraud detection algorithms is key for reducing these losses, and more and more algorithms rely on advanced machine learning techniques to assist fraud investigators. The design of fraud detection algorithms is however particularly challenging due to the non-stationary distribution of the data, the highly unbalanced classes distributions and the availability of few transactions labeled by fraud investigators. At the same time public data are scarcely available for confidentiality issues, leaving unanswered many questions about what is the best strategy. In this thesis we aim to provide some answers by focusing on crucial issues such as: i) why and how undersampling is useful in the presence of class imbalance (i.e. frauds are a small percentage of the transactions), ii) how to deal with unbalanced and evolving data streams (non-stationarity due to fraud evolution and change of spending behavior), iii) how to assess performances in a way which is relevant for detection and iv) how to use feedbacks provided by investigators on the fraud alerts generated. Finally, we design and assess a prototype of a Fraud Detection System able to meet real-world working conditions and that is able to integrate investigators’ feedback to generate accurate alerts. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The study of Stochastic Local Search (SLS) algorithms is becoming more pivotal these days, due to their vast number of applications in decision making. Prior to the implementation of algorithmic knowledge for decision making, many decisions were made based on manual calculation, on the fly, or even based on guts feeling. Nowadays, such an approach is more rarely seen, especially when the decisions that need to be made are high-risk, cost intensive, or time-consuming. The increasingly often used SLS algorithms are one of the options available to assist the decision making process these days.The work discussed in this thesis concerns the study of SLS algorithms for solving the Quadratic Assignment Problem (QAP), a prominent combinatorial optimization problem, which until today is very hard to solve. Our interest is to study the behavior and performance of SLS algorithms for solving QAP instances of different characteristics, such as size, sparsity, and structure. In this study, we have also proposed new variants of SLS algorithms, inspired by existing, well-performing SLS algorithms for solving the QAP. The new variants of SLS algorithms are then further extended for solving the bi-objective QAP (bQAP).One main focus in this study is to see how the performance of algorithms scales with instance size. We have considered instances that are much larger than the ones usually used in the studies of algorithms for solving the QAP. By understanding how the algorithms perform when the instance size changes, we might be able to solve other problems effectively by considering the similarity in their characteristics to the ones of the QAP, or by seeing common trends in the relative performance of the various available SLS methods. For single objective QAP instances we found that the structure and size of instances do have a significant impact on the performance of SLS algorithms. For example, comparisons between Tabu Search (TS) and Simulated Annealing (SA) on instances with randomly generated matrices show that the overall performance of TS is better than SA, irrespective the size of instances considered. The results on a class of structured instances however show that TS performs well on small-sized instances, while on the larger ones, SA shows better results. In another experiment, Hierarchical Iterated Local Search (HILS) has shown very good results compared to several Iterated Local Search (ILS) variants. This experiment was done on a class of structured instances of size from 100 to 500. An extensive experiment on a class of structured instances of size 30 to 300 using tuned parameter settings shows that population based algorithms perform very well on most of the instance classes considered. SA however, shows very good performance especially on large-sized instances with low sparsity level. For the bQAP, the correlation between the flow matrices does have a strong effect that determines the performance of algorithms for solving them. Hybrid Simulated Annealing (HSA) clearly outperforms Hybrid Iterative Improvement (HII). When compared to Multi Objective Ant Colony Optimization (MOACO) and Strength Pareto Evolutionary Algorithm 2 (SPEA2), HSA shows very good performance, where HSA outperforms MOACO and SPEA2, especially on instances of large size, thus, offering a better scaling behavior. Based the results obtained in this study, it is possible to come up with a general idea on the suitability of SLS algorithms for solving instances with a certain characteristic. Given an unknown QAP instance, one can guess the most suitable algorithm for solving it depending on the type, size, and sparsity of the instance, while for a bQAP instance the most suitable algorithm can be guessed based on its size and correlation between the flow matrices. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

Two-player zero-sum games of infinite duration and their quantitative versions are used in verification to model the interaction between a controller (Eve) and its environment (Adam). The question usually addressed is that of the existence (and computability) of a strategy for Eve that can maximize her payoff against any strategy of Adam: a winning strategy. It is often assumed that Eve always knows the exact state of the game, that is, she has full observation. In this dissertation, we are interested in two variations of quantitative games. First, we study a different kind of strategy for Eve. More specifically, we consider strategies that minimize her regret: the difference between her actual payoff and the payoff she could have achieved if she had known the strategy of Adam in advance. Second, we study the effect of relaxing the full observation assumption on the complexity of computing winning strategies for Eve. Regarding regret-minimizing strategies, we give algorithms to compute the strategies of Eve that ensure minimal regret against three classes of adversaries: (i) unrestricted, (ii) limited to positional strategies, or (iii) limited to word strategies. These results apply for quantitative games defined with the classical payoff functions Inf, Sup, LimInf, LimSup, mean payoff, and discounted sum. For partial-observation games, we continue the study of energy and mean- payoff games started in 2010 by Degorre et al. We complement their decidability result for a particular problem related to energy games (the Fixed Initial Credit Problem) by giving tight complexity bounds for it. Also, we show that mean-payoff games are undecidable for all versions of the mean-payoff function. Motivated by the latter negative result, we define and study several decidable sub-classes of mean-payoff games. Finally we extend the newly introduced window mean-payoff objectives to the partial observation setting. We show that they are conservative approximations of partial-observation mean-payoff games and we classify them according to whether they are decidable. Furthermore, we give a symbolic algorithm to solve them. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The interdisciplinary field of systems biology has evolved rapidly over the last few years. Different disciplines have contributed to the development of both its experimental and theoretical branches.Although computational biology has been an increasing activity in computer science for more than a two decades, it has been only in the past few years that optimization models have been increasingly developed and analyzed by researchers whose primary background is Operations Research(OR). This dissertation aims at contributing to the field of computational biology by applying mathematical programming to certain problems in molecular biology.Specifically, we address three problems in the domain of Genome Wide Association Studies}:(i) the Pure Parsimony Haplotyping Under uncertatind Data Problem that consists in finding the minimum number of haplotypes necessary to explain a given set of genotypes containing possible reading errors; (ii) the Parsimonious Loss Of Heterozygosity Problem that consists of partitioning suspected polymorphisms from a set of individuals into a minimum number of deletion areas; (iii) and the Multiple Individuals Polymorphic Alu Insertion Recognition Problem that consists of finding the set of locations in the genome where ALU sequences are inserted in some individual(s).All three problems are NP-hard combinatorial optimization problems. Therefore, we analyse their combinatorial structure and we propose an exact approach to solution for each of them. The proposed models are efficient, accurate, compact, polynomial-sized and usable in all those cases for which the parsimony criterion is well suited for estimation. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Reactive systems are computer systems that maintain continuous interaction with the environment in which they operate. Such systems are nowadays part of our daily life: think about common yet critical applications like engine control units in automotive, aircraft autopilots, medical aided- devices, or micro-controllers in mass production. Clearly, any flaw in such critical systems can have catastrophic consequences. However, they exhibit several characteristics, like resource limitation constraints, real-time responsiveness, concurrency that make them difficult to implement correctly. To ensure the design of reactive systems that are dependable, safe, and efficient, researchers and industrials have advocated the use of so-called formal methods, that rely on mathematical models to express precisely and analyze the behaviors of these systems.Automata theory provides a fundamental notion such as languages of program executions for which membership, emptiness, inclusion, and equivalence problems allow us to specify and verify properties of reactive systems. However, these Boolean notions yield the correctness of the system against a given property that sometimes, falls short of being satisfactory answers when the performances are prone to errors. As a consequence, a common engineering approach is not just to verify that a system satisfies a property, but whether it does so within a degree of quality and robustness.This thesis investigates the expressibility, recognition, and robustness of quantitative properties for program executions.• Firstly, we provide a survey on languages definable by regular automata with Presburger definable constraints on letter occurrences for which we provide descriptive complexity. Inspired by this model, we introduce an expression formalism that mixes formula and automata to define quantitative languages \ie function from words to integers. These expressions use Presburger arithmetic to combine values given by regular automata weighted by integers. We show that quantitative versions of the classical decision problems such as emptiness, universality, inclusion, and equivalence are computable. Then we investigate the extension of our expressions with a ''Kleene star'' style operator. This allows us to iterate an expression over smaller fragments of the input word, and to combine the results by taking their iterated sum. The decision problems quickly turn out to be not computable, but we introduce a new subclass based on a structural restriction for which algorithmic procedures exist.• Secondly, we consider a notion of robustness that places a distance on words, thus defining neighborhoods of program executions. A language is said to be robust if the membership satisfiability cannot differ for two ''close'' words, and that leads to robust versions of all the classical decision problems. Our contribution is to study robustness verification problems in the context of weighted transducers with different measures (sum, mean-payoff, and discounted sum). Here, the value associated by the transducer to rewrite a word into another denotes the cost of the noise that this rewriting induce. For each measure, we provide algorithms that determine whether a language is robust up to a given threshold of error and we solve the synthesis of the robust kernel for the sum measure. Furthermore, we provide case studies including modeling human control failures and approximate recognition of type-1 diabetes using robust detection of blood sugar level swings.• Finally, we observe that algorithms for structural patterns recognition of automata often share similar techniques. So, we introduce a generic logic to express structural properties of automata with outputs in some monoid, in particular, the set of predicates talking about the output values is parametric. Then, we consider three particular automata models (regular automata, transducers, and automata weighted by integers) and instantiate the generic logic for each of them. We give tight complexity results for the three logics with respect to the pattern recognition problem. We study the expressiveness of our logics by expressing classical structural patterns characterizing for instance unambiguity and polynomial ambiguity in the case of regular automata, determinizability, and finite-valuedness in the case of transducers and automata weighted by integers. As a consequence of our complexity results, we directly obtain that these classical properties can be decided in logarithmic space. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse rassemble trois travaux sur la complexité d'information et sur la complexité en requête quantique. Ces domaines d'études ont pour points communs les outils mathématiques pour étudier ces complexités, c'est-à-dire les problèmes d'optimisation.Les deux premiers travaux concernent le domaine de la complexité en requête quantique, en généralisant l'important résultat suivant: dans l'article cite{LMRSS11}, leurs auteurs parviennent à caractériser la complexité en requête quantique, à l'aide de la méthode par adversaire, un programme semi-définie positif introduit par A. Ambainis dans cite{Ambainis2000}. Cependant, cette caractérisation est restreinte aux modèles à temps discret, avec une erreur bornée. Ainsi, le premier travail consiste à généraliser leur résultat aux modèles à temps continu, tandis que le second travail est une démarche, non aboutie, pour caractériser la complexité en requête quantique dans le cas exact et pour erreur non bornée.Dans ce premier travail, pour caractériser la complexité en requête quantique aux modèles à temps discret, nous adaptons la démonstration des modèles à temps discret, en construisant un algorithme en requête adiabatique universel. Le principe de cet algorithme repose sur le théorème adiabatique cite{Born1928}, ainsi qu'une solution optimale du dual de la méthode par adversaire. À noter que l'analyse du temps d'exécution de notre algorithme adiabatique est basée sur preuve qui ne nécessite pas d'écart dans le spectre de l'Hamiltonien.Dans le second travail, on souhaite caractériser la complexité en requête quantique pour une erreur non bornée ou nulle. Pour cela on reprend et améliore la méthode par adversaire, avec une approche de la mécanique lagrangienne, dans laquelle on construit un Lagrangien indiquant le nombre de requêtes nécessaires pour se déplacer dans l'espace des phases, ainsi on peut définir l'``action en requête''. Or ce lagrangien s'exprime sous la forme d'un programme semi-defini, son étude classique via les équations d'Euler-Lagrange nécessite l'utilisation du théorème de l'enveloppe, un puissant outils d'économathématiques. Le dernier travail, plus éloigné, concerne la complexité en information (et par extension la complexité en communication) pour simuler des corrélations non-locales. Ou plus précisement la quantitié d'information (selon Shannon) que doive s'échanger deux parties pour obtenir ses corrélations. Dans ce but, nous définissons une nouvelle complexité, denommée la zero information complexity IC_0, via le modèle sans communication. Cette complexité a l'avantage de s'exprimer sous la forme d'une optimization convexe. Pour les corrélations CHSH, on résout le problème d'optimisation pour le cas à une seule direction où nous retrouvons un résultat connu. Pour le scénario à deux directions, on met numériquement en évidence la validité de cette borne, et on résout une forme relaxée de IC_0 qui est un nouveau résultat. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes.

Ce manuscrit d'Habilitation à diriger des recherches décrit mes travaux de recherche récents en théorie des graphes et en théorie des jeux combinatoires. Une première partie est consacrée à l'étude de paramètres de graphes en s'intéressant particulièrement aux contraintes structurelles qui permettent d'améliorer les bornes connues. Dans cette partie, nous traitons notamment la paire-domination, la domination indépendante mais aussi les partitions en cographes et les colorations quasi propres. Une deuxième partie traite de la domination de puissance, une forme itérative de la domination au sujet de laquelle nous proposons un début de synthèse des résultats existants. Enfin, une troisème partie parle de jeux. Nous y traitons d'abord le travail réalisé sur quelques conjectures portant sur un jeu de domino, puis au sujet des jeux en version misère. Nous y parlons enfin du jeu de domination, qui est à l'interface entre le paramètre de graphe et le jeu combinatoire.

Cette HDR présente mes travaux récents en combinatoire (énumérative et algébrique) autour du groupe symétrique, et répartis sur trois axes principaux : les co-quasi-invariants polynomiaux, les matrices à signes alternants et les tableaux boisés.