The potential of quantum algorithms for solving optimization problems has been explored since the early days of quantum computing. This course introduces some of the key ideas and algorithms developed in this context, along with their fundamental limitations. Depending on the available time, topics covered may include: quantum optimization algorithms inspired by physics (adiabatic algorithms, variational algorithms, QAOA, quantum annealing, etc.), quantum algorithms for convex optimization (acceleration of first- and second-order methods, oracular problems, etc.), applications to combinatorial optimization (graph problems, quadratic binary optimization, etc.).[-]

The potential of quantum algorithms for solving optimization problems has been explored since the early days of quantum computing. This course introduces some of the key ideas and algorithms developed in this context, along with their fundamental limitations. Depending on the available time, topics covered may include: quantum optimization algorithms inspired by physics (adiabatic algorithms, variational algorithms, QAOA, quantum annealing, etc.), quantum algorithms for convex optimization (acceleration of first- and second-order methods, oracular problems, etc.), applications to combinatorial optimization (graph problems, quadratic binary optimization, etc.).[-]

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.[-]

Many of us use smartphones and rely on tools like auto-complete and spelling auto-correct to make using these devices more pleasant, but building these tools presents a challenge. On the one hand, the machine-learning algorithms used to provide these features require data to learn from, but on the other hand, who among us is willing to send a carbon copy of all our text messages to device manufacturers to provide that data? 'Local differential privacy' and related concepts have emerged as the gold standard model in which to analyze tradeoffs between losses in utility and privacy for solutions to such problems. In this talk, we give a new state-of-the-art algorithm for estimating histograms of user data, making use of projective geometry over finite fields coupled with a reconstruction algorithm based on dynamic programming.
This talk is based on joint work with Vitaly Feldman (Apple), Huy Le Nguyen (Northeastern), and Kunal Talwar (Apple).[-]

Si l'hypothèse P $\neq$ NP a pour conséquence que les problèmes NP-difficiles ne sont pas résolubles en temps polynomial, l'obtention de résultats négatifs plus précis nécessite le recours à des hypothèses plus fortes. Dans cet exposé, nous présenterons certains résultats négatifs (bornes inférieures de complexité) obtenus à partir des hypothèses ETH (exponential time hypothesis) et SETH (strong exponential time hypothesis). Il y sera question de SAT, de graphes, de complexité (classique et parfois paramétrée), de problèmes difficiles mais aussi de problèmes polynomiaux.[-]

Matrices whose coefficients are univariate polynomials over a field are a basic mathematical object which arises at the core of fundamental algorithms in computer algebra: sparse or structured linear system solving, rational approximation or interpolation, division with remainder for bivariate polynomials, etc. After presenting this context, we will give an overview of recent progress on efficient computations with such matrices. Next, we will show how these results have been exploited to improve complexity bounds for a selection of problems which, interestingly, do not necessarily involve polynomial matrices a priori: computing the characteristic polynomial of a scalar matrix, performing modular composition of univariate polynomials, changing the monomial order for multivariate Gröbner bases.[-]

A central concept in graph theory is the notion of tree decompositions - these are decompositions that allow us to split a graph up into "nice" pieces by "small" cuts. It is possible to solve many algorithmic problems on graphs by decomposing the graph into "nice" pieces, finding a solution in each of the pieces, and then gluing these solutions together to form a solution to the entire graph. Examples of this approach include algorithms for deciding whether a given input graph is planar, the $k$-Disjoint paths algorithm of Robertson and Seymour, as well as many algorithms on graphs of bounded tree-width. In this talk we will look at a way to compare two tree decompositions of the same graph and decide which of the two is "better". It turns out that for every cut size $k$, every graph $G$ has a tree decomposition with (approximately) this cut size, such that this tree-decomposition is "better than" every other tree-decomposition of the same graph with cut size at most $k$. We will discuss some consequences of this result, as well as possible improvements and research directions.[-]