Events

Title: Intersections of graphs and χ-boundedness: characterizing χ-guarding graph classes

Abstract: For two graphs G1, G2, their intersection is given by only keeping the vertices and edges that appear in both. This graph operation is closely related to various intersection graph classes, such as the intersection graphs of axis-aligned rectangles. We are interested in the interplay between the graph intersection operation and χ-boundedness. A graph class C  is χ-bounded if there exists a function providing an upper bound for the chromatic number of each graph in the class based on the graph’s clique number.

Title: Tight bounds for reconstructing graphs from distance queries

Abstract: Suppose you are given the vertex set of a graph and you want to discover the edge set. An oracle can tell you, given two vertices, what the distance is between these vertices in the graph. (For example, in a computer network, this would represent the minimum number of communication links needed to send a message from one computer to another.) Based on the answer, you may select the next query. The (labelled) graph is reconstructed when there is a single edge set compatible with the answers. How many queries are needed, in the worst case? The question becomes interesting for bounded degree graphs. We provide tight bounds for various classes of graphs, improving both the lower and upper bound, in both the randomized and deterministic setting. 

Title: The spectra of lift and factored lifts of graphs or digraphs

Abstract: In this talk, we first explain the path we took from defining polynomial matrices to a generalization of voltage graphs that we call combined voltage graphs. Moreover, we give a general definition of a matrix associated with a combined voltage graph, which allows us to provide a new method for computing the eigenvalues and eigenspaces of such graphs. 

Title: NC algorithm to find perfect matching in planar graphs

Abstract: Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution. 

Location:  MC 5479

There will be a social starting at 1:00 pm.

This seminar will consist of 3 short talks by undergraduate students. There will be a coffee break at 1:30 pm.

Title: Nonnegative Matrix Factorization in non-standard settings, for fun

Abstract: This abstract is broken into 6 points.

1. What is NMF: NMF is to find two elementwise nonnegative low-rank matrices W and H such that M ≈ WH for a given elementwise nonnegative matrix M.

2. NMF is commonly done in the Euclidean distance.

3. I argue that Euclidean distance is "not good", and a ray-to-ray distance is better.

4. Under L2-normalization onto the unit sphere, we arrive at the cosine angle distance, which motivates the use of manifold optimization techniques.

5. Under L1-normalization onto the simplex, we arrive at the so-called Aitchison geometry, which contains funny algebra.

6. Why do these: for curiosity and fun. For application, these non-standard NMF can "remove cloud" from satellite images.

Title: Quartic quantum speedups for planted inference

Abstract: Consider the following task ("noisy 4XOR"), arising in CSPs, optimization, and cryptography.  There is a 'secret' Boolean vector x in {-1,+1}^n.  One gets m randomly chosen pairs (S, b), where S is a set of 4 coordinates from [n] and b is x^S := prod_{i in S} x_i with probability 1-eps, and -x^S with probability eps.  Can you tell the difference between the cases eps = 0.1 and eps = 0.5? 

Location: MC 5479

There will be a social starting at 1:00 pm.

Title: Control over the Kerov-Kirillov-Reshetikhin bijection with respect to the nesting structure on rigged configurations

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.

Abstract: The talk will discuss controlling the Kerov-Kirillov-Reshetikhin (KKR) bijection between semistandard tableaux and rigged configurations with a particular emphasis on the standard case. We introduce theorems and techniques to control the shape of the first rigged partition. We also introduce an operation on a standard tableau which induces a very small, very controlled change in the riggings of the corresponding rigged configuration. Despite how specific this operation seems, it can be used to manipulate all the riggings on the first rigged partition of a rigged configuration. It can also be used to give an alternate method to Kuniba et al. in order to "unwrap" the natural nesting structure on rigged configurations. The connection to the multi colour box ball system is discussed.