Orateur : Martin Cooper, l’IRIT
Titre : Hybrid tractable classes
Résumé : The CSP (constraint satisfaction problem) is a generic problem over finite domains in which each constraint is a relation and a list of variables (its scope). Given the NP-completeness of the CSP, it is natural is to look for restrictions of the problem that allow polynomial-time solving. The two classical approaches consist in studying restrictions either on the language of relations or on the hypergraph defined by the constraint scopes. After 30 years of effort, dichotomies have been established for these two approaches. A third avenue consists in defining classes of CSP instances by forbidding patterns (generic sub-problems). This hybrid approach has led to the discovery of several new polynomial classes. I will present the state of the art in the characterization of forbidden patterns that define polynomial classes.
Orateur : Mahsa Shirmohammadi (LIS AMU, new MCF)
Titre : On Rationality of Nonnegative Matrix Factorization
Résumé : Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative n×m matrix M into a product of a nonnegative n×d matrix W and a nonnegative d×m matrix H. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether a rational matrix M always has an NMF of minimal inner dimension d whose factors W and H are also rational. We answer this question negatively, by exhibiting a matrix for which W and H require irrational entries.
In this talk, we further exhibit a connection between Cohen and Rothblum’s question with a question posed by Paz, in his seminal 1971 textbook. The latter question asks, given a probabilistic automaton (PA) with rational transition probabilities, does there always exist a minimal equivalent PA that also has rational transition probabilities? The PA and its minimal equivalent PA accept all finite words with equal probabilities. We use the established connection to answer Paz’s question negatively, thus falsifying a positive answer claimed in 1974.
(This talk is based on two papers in ICALP 2016 and SODA 2017.)
Orateur : Victor Chepoi (LIS AMU)
Titre : Tout réseau hyperbolique a un coeur (ou « hyperbolicité pour tous »)
Résumé : In the first part of the talk, we will introduce Gromov hyperbolicity and recall several characterizations of delta-hyperbolic geodesic metric spaces and graphs.
In the second part, we investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network G admits a core, thus answering in the positive a conjecture by Jonckheere, Lou, Bonahon, and Baryshnikov, Internet Mathematics, 7 (2011) which is based on the experimental observation by Narayan and Saniee, Physical Review E, 84 (2011) that real-world networks with small hyperbolicity have a core congestion. Namely, we prove that for every subset X of n vertices of a graph G with delta-thin geodesic triangles there exists a vertex m of G such that the ball B(m,4delta) of radius 4delta centered at m intercepts at least one half of the total flow between all pairs of vertices of X, where the flow between two vertices x,y of X is carried by geodesic (or quasi-geodesic) (x,y)-paths. We show that the point m can be constructed in the following way: take a median point m* of X (a point minimizing the sum of distances to the points of X) in the injective hull of G and then a closest to m* point in G. In the third part of the talk, (and if the time will permit), we will describe a simple factor 8 approximation algorithm for optimal hyperbolicity of an n-vertex graph in optimal O(n^2) time (assuming that the input is the distance matrix of the graph).
The talk is based on the papers
[1] V. Chepoi, F. Dragan, and Y. Vaxès, Core congestion is inherent in hyperbolic networks, SODA 2017, <http://arxiv.org/abs/1605.03059> .
[2] J. Chalopin, V. Chepoi, F. Dragan, G. Ducoffe, A. Mohammed, and Y. Vaxès, <https://arxiv.org/abs/1803.06324> Fast approximation and exact computation of negative curvature parameters of graphs, SoCG 2018, <https://arxiv.org/abs/1803.06324>.