Rutgers Discrete Mathematics Seminar

Title: The Erdos-Hajnal Conjecture, Structured Non-Linear Graph-Based Hashing and B-Matching Anonymization via Perfect Matchings Counting

Speaker: Krzysztof Choromanski, Google Research

Date: Monday, October 5, 2015 2:00 pm

Location: Hill center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ


The goal of this talk is to show three new combinatorial techniques that led to some recent advances in discrete mathematics and computer science in general. The first one regards the celebrated open conjecture of Erdos and Hajnal from 1989 stating that families of graphs not having some given graph H as an induced subgraph contain polynomial-size cliques/stable sets (in the undirected setting) or transitive subsets (in the directed setting). Recent techniques that I will be talking about in this part of the talk provided the proof of the conjecture for new infinite classes of graphs. Furthermore, they gave tight asymptotics for the Erdos-Hajnal coefficients for many classes of prime tournaments as well as the proof of the weaker version of the conjecture for trees on at most six vertices and all but one tournament on at most six vertices. Structured non-linear graph-based hashing is motivated by applications in neural networks, where matrices of linear projections are constrained to have a specific structured form. This drastically reduces the size of the model and speeds up computations. I will show how the properties of the underlying graph encoding correlations between entries of these matrices (such as its chromatic number) imply the quality of the entire non-linear hashing mechanism. Furthermore, I will explain how general structured matrices that very recently attracted researchers.