Time: Wednesday, 19 February 2020, 2:0pm
Venue: Dept. of CSE, Room No. 109, 01st Floor, New CSE/CC Bldg.
Abstract:
A connected graph G, on two or more vertices, is matching covered if each edge belongs to some perfect matching. A subgraph H of G is conformal if G−V(H) has a perfect matching. For problems pertaining to perfect matchings of a graph G — such as those arising from the perfect matching polytope PMP(G) — one may restrict attention to matching covered graphs. Several of these problems may be stated in terms of conformal subgraphs of a graph. I will discuss 5 such problems each of which pertains to characterizing a class of graphs; these graph classes are described below. (By ‘characterize’, I mean: obtain an NP or a co - NP characterization, and ideally, show that the corresponding decision problem is in P.)
The first two graph classes arise from the perfect matching polytope PMP(G).
1. Birkhoff–von Neumann graphs: A graph G is Birkhoff–von Neumann if PMP(G) may be described solely by non-negativity and degree constraints.
2. PM-compact graphs: A graph G is PM-compact if the combinatorial diameter of PMP(G) equals 1.
The next two graph classes are inspired by a theorem of Lovász (1983): Every non-bipartite matching covered graph either “contains” K_4 or “contains” the triangular prism C_6 .
3. C_6 -free graphs: A graph G is C_6 -free if it does not “contain” C_6 .
4. K_4 -free graphs: A graph G is K 4 -free if it does not “contain” K_4 .
The last graph class, and arguably the most important one (among these 5), was defined by physicists Fisher, Kasteleyn, and Temperley (1960s) in order to solve the “dimer problem”.
5. Pfaffian graphs: A graph G is Pfaffian if it admits a “Pfaffian orientation”.
During this talk, I will discuss these 5 graph classes, and will explain their connections with conformal subgraphs. Thereafter, I will summarize my contributions (so far) towards characterizing these graph classes; these results are listed below.
In a joint work with Carvalho, Wang and Lin (https://arxiv.org/abs/1807.07339), we provided a complete description of graphs that are Birkhoff–von Neumann as well as PM-compact. The corresponding decision problem is in P.
In a joint work with Lucchesi, Carvalho and Murty (https://epubs.siam.org/doi/ abs/10.1137/17M1138704), we showed that the problem of deciding whether a graph is C_6 -free is equivalent to that of deciding whether a graph is Birkhoff–von Neumann.
In a joint work with Murty (https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.21882), we provided a complete description of planar K 4 -free graphs as well as planar C_6 -free graphs. The corresponding decision problems are in P.
Finally, I will briefly mention my conjectures relating K_4 -free graphs to Pfaffian graphs.
Speaker's Profile:
Nishad Kothari, as a researcher, studies mathematical objects called Graphs, and specializes in the study of Perfect Matchings (aka, Matching Theory). In this sense, he is a structural graph theorist whose work has connections with complexity theory, polyhedral combinatorics as well as statistical mechanics.
After completing his Bachelor's degree in Computer Science (CS) from BIT Mesra (Ranchi),he went on to obtain his Master's degree in CS from Georgia Tech (Atlanta, USA). It was during his time at Georgia Tech that he discovered his interest in the theoretical aspects of CS. Consequently, he took a few courses from the School of Mathematics, and was introduced to Graph Theory by Robin Thomas. This memorable encounter with the subject ultimately led him to pursue his PhD in Combinatorics and Optimization (C&O) at the Faculty of Mathematics at the University of Waterloo (Canada) under the supervision of Joseph Cheriyan and U. S. R. Murty. During his time at C&O Waterloo, not only did Professor Murty train him in Matching Theory, but he also ignited his enthusiasm for the subject.
Since completing his PhD in 2016, Nishad has held postdoc positions at C&O Waterloo and at the Faculty of Mathematics at the University of Vienna (Austria). Currently, he is a postdoc at the Institute of Computing at the University of Campinas (Brazil), and his principal collaborators are Marcelo H. de Carvalho and Claudio L. Lucchesi. He has a diverse network of coauthors who live in Brazil, Canada, China, New Zealand and USA.
Nishad, as an educator, is especially passionate about teaching courses in Combinatorics (aka, Discrete Mathematics), and is also interested in lecturing about related subjects in theoretical CS and mathematics. During his time at C&O Waterloo, he taught introductory courses in both Combinatorics and Optimization..
Organization:
University of Campinas
Host:
Prof.Ajit Diwan
User:
Department Calendar
Time:
11:30am
Send Reminder:
Yes - 46 hours 6 minutes before start
Description:
Speaker: Dr. Blaise Genest
Time: Friday, 21 February 2020, 11:30am
Venue: Department of Computer Science and Engineering, Room No. 109, 01st Floor, New CSE/CC Building
Abstract:
In this talk, we describe several ways to foster trust in AI tools. Indeed, the most prominent current AI tools (Neural Networks, Reinforcement learning) are in the same time very efficient, but also very complex to be understood by humans. And these tools fail sometimes, with potentially catastrophic outcomes. Recently, the new paradigm of explainable AI has emerged. While explainable AI is necessary, it is also not sufficient for complete trust: what if we are not convinced by the explanations? Or what if we are wrongly convinced by it? Also, humans cannot check every split-second decisions taken by AI tools. In order to complement explainable AI, we advocate for advances in Formal Methods and AI to provide guarantees about their behaviors. In this talk, we will particularly focus on guarantees we can bring when Learning a stochastic system. More precisely, we study several simple algorithm to learn Discrete Time Markov Chains (frequency estimation and Laplace smoothing) and provide statistical PAC guarantees over global behavior (reachability probabilities…) of the learnt model wrt the original system.
Speaker Profile:
Blaise Genest is a former student of ENS Cachan/Paris-Saclay (Mathematics and Computer Science, 1999-2003). He received his Ph.D. in Computer Science from University Paris 7, France (2004). He is a CNRS senior researcher with IRISA, Rennes, France. He spent 3 years in Singapore in 2010-2012, working with NUS. He is working at the interface of Formal Methods and AI. He organized the 2nd International Workshop on FM and AI in Rennes in 2019, which attracted around 50 researchers from 11 countries. The 3rd workshop FMAI’2020 will take place at Imperial College.