“Euclidean Graph Embeddings in R^k: Polynomial Cases and Symmetry”

Business Building, Room 903, Beirut campus

The lecture will be given by Professor Leo Liberti from LIX Ecole Polytechnique, France.

Abstract:
The graph embedding problem consists of finding an embedding x:V->R^K of a simple weighted undirected graph G=(V,E,d) such that: for each edge {u,v} we have ||x(u) - x(v)|| = d(u,v).

Although the problem in general requires a search in continuous space, we restrict attention to a subclass of instances for which there is a vertex order that allows for a discrete search. This subclass is still NP-hard. Here is a strange occurrence, which we noticed in 2005: every instance yields a number of solutions that is a power of two. Five years since, we managed to prove that this conjecture holds with probability 1. Using the same theoretical set-up, we also exhibit some sufficient conditions for which the problem is in P. Interestingly, all tested protein graphs satisfy these conditions, thus providing an important application to this problem.

Short biography of Dr. Liberti:
Dr. Liberti is an associate professor at LIX Ecole Polytechnique since 2009. He holds a Ph.D. in optimization from the Imperial College, London. His research interests cover mathematical programming, global and combinatorial optimization, complex industrial systems, and bioinformatics. Dr. Liberti is the head of the “System Modelling and Optimization (SYSMO)” group at LIX. His research team consists of around 15 researchers. He also holds a Microsoft-CNRS Chair for Optimization and Sustainable Development, and he is the vice-president of the department. Dr. Liberti is editor-in-chief of the Springer 4OR international journal, and he is an associate editor for Discrete Applied Mathematics, Journal of Global Optimization, and International Transactions in Operational Research. More details can be found on this page.

Event organizer: LAU’s School of Arts and Sciences – Department of Computer Science and Mathematics