In our research we aim to understand the power and limitations of efficient algorithms. To this end, we design and analyse algorithms, and set impossibility results (completeness results or, when possible, unconditional lower bounds). We also study the relevant combinatorial structures.<\/p>\n\n\n\n
Various models of computation can be considered to allow different features in the algorithms (eg, sequential vs parallel, synchronous vs asynchronous, deterministic vs probabilistic). Various complexity measures can be considered to quantify efficiency, such as time, space, communications.<\/p>\n\n\n\n
Among the several fields of mathematics at the heart of this research, our team focuses on algebra and combinatorics. Both of these areas are a source of algorithmic problems which play key roles in the architecture of complexity theory (eg, the complexity of computing matrix permanents or graph colourings). Both areas also provide mathematical tools which are essential to proving theorems in complexity theory (eg, advanced linear algebra and graph theory for de-randomization or the study of approximation and parameterized algorithms). <\/p>\n\n\n\n
Graph theory and graph algorithms, combinatorics, biomolecular computing models, discrete and algebraic algorithms, disc and sphere packings, complexity theory.<\/p>\n\n\n\n
Our research deals with structural properties of graphs, which can then be used in order to design new algorithmic tools (e.g.: polynomial exact or approximation algorithms, parameterized or moderately exponential algorithms). Among other graph problems, we focus on the chromatic number, the independence number, or the maximum clique number of a graph.<\/p>\n\n\n\n
Contacts:<\/strong> \u00c9douard <\/a>BONNET<\/a>, Carl FEGHALI<\/a>, Jean-Florent RAYMOND<\/a>, \u00c9ric THIERRY<\/a>, Stephan THOMASS\u00c9<\/a>, Nicolas TROTIGNON<\/a>, R\u00e9mi WATRIGANT<\/a><\/p>\n\n\n\n We study different logics for talking about properties on graphs. We investigate several reasoning tasks like model checking (does a given graph satisfy a given property?) and satisfiability problem (is there a graph satisfying a given property?). Contacts:<\/strong> \u00c9douard <\/a>BONNET<\/a>, Fran\u00e7ois SCHWARZENTRUBER<\/a>, Stephan THOMASS\u00c9<\/a><\/p>\n\n\n\n We study an algebraic analogue of the P versus NP problem based on the computation model of arithmetic circuits. These circuits are made of addition and multiplication gates (instead of boolean gates in boolean circuits) and therefore compute polynomials. We also work on arithmetic circuit reconstruction and in particular on tensor decomposition. This task can be viewed as an algebraic analogue of computational learning.<\/p>\n\n\n\n Contacts:<\/strong> Pascal KOIRAN<\/a>, Natacha PORTIER<\/a><\/p>\n\n\n\n We are looking in the archives for old open problems that no one can solve but us.<\/p>\n\n\n\n Contact:<\/strong> Daria PCHELINA<\/a>, Micha\u00ebl RAO<\/a><\/p>\n\n\n\n Our goal is to design biomolecules with computation capacities. Our approach is two-fold:<\/p>\n\n\n\n Contact:<\/strong> Daria PCHELINA<\/a>, Nicolas SCHABANEL<\/a><\/p>\n\n\n\n <\/p>\n\n\n\n <\/p>\n\n\n\n <\/p>\n\n\n\n <\/p>\n","protected":false},"excerpt":{"rendered":" In our research we aim to understand the power and limitations of efficient algorithms. To this end, we design and analyse algorithms, and set impossibility results (completeness results or, when possible, unconditional lower bounds). We also study the relevant combinatorial structures. Various models of computation can be considered to allow different features in the algorithms … Continue reading “MC2 Team \u2013 \u00c9quipe MC2”<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-22","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/pages\/22","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/comments?post=22"}],"version-history":[{"count":36,"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/pages\/22\/revisions"}],"predecessor-version":[{"id":158,"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/pages\/22\/revisions\/158"}],"wp:attachment":[{"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/media?parent=22"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Interactions between graphs and logic<\/h5>\n\n\n\n
We focus on modal logic for reasoning about knowledge in multi-agent systems (e.g. does agent A know that agent B does not know that the area is safe?), where graphs are Kripke structures.
We also design logics for reasoning about graph neural networks (GNNs), in order to verify the behavior of GNNs (e.g. does some trained GNN classify as toxic any molecule satisfying a given property?).<\/p>\n\n\n\nAlgebraic complexity<\/h5>\n\n\n\n
Combinatorics, discrete structures & symbolic dynamics<\/h5>\n\n\n\n
Biomolecular computation models: theory and experiments<\/h5>\n\n\n\n
\n