Events

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.

Title: Oddities in the pursuit of self-duality

Abstract: Certain important cones in conic optimization are self-dual, e.g., the positive semidefinite matrices and the nonnegative orthant. In this talk we will address the problem of determining which convex cones are self-dual in a broad sense, which allows changing the underlying inner product if necessary. We will describe some recent progress on this question for polyhedral cones and discuss some unexpected connections. In particular, we will show a curious result connecting self-dual polyhedral cones and extreme rays of doubly nonnegative matrices. We will also discuss how semidefinite programming can be used to search for self-dual polyhedral cones. Time allowing, we will describe new results on the related problem of determining the automorphisms of certain cones of interest.

This talk is based on joint works with João Gouveia and Masaru Ito.

Title: Lecture hall graphs and the Askey scheme

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

Abstract: We establish, for every family of orthogonal polynomials in the Askey scheme and the q-Askey scheme, a combinatorial model for mixed moments and coefficients in terms of paths on the lecture hall lattice. This generalizes to all families of orthogonal polynomials in the Askey scheme previous results of Corteel and Kim for the little q-Jacobi polynomials. This is joint work with Sylvie Corteel, Bhargavi Jonnadula, and Jon Keating.

Title: Everything is possible: constructing convex sets with prescribed facial dimensions, efficiently

Abstract: Given any finite set of nonnegative integers, there exists a closed convex set whose facial dimension signature coincides with this set of integers, that is, the dimensions of its nonempty faces comprise exactly this set of integers. In this work, we show that such sets can be realised as solution sets of systems of finitely many convex quadratic inequalities, and hence are representable via second-order cone programming problems, and are, in particular, spectrahedral.

There will be a social starting at 1:00pm

Title: Notation of Total Dual Integrality for Semidefinite Programming

Speaker: Mehrdad Sohrabi

Abstract:

Total dual integrality (TDI) plays a crucial role in integer programming and polyhedral combinatorics, with applications in network flows, matching, and more. Semidefinite programming is an instance of conic optimization that generalizes linear programming. In this talk, we will discuss the notion of total dual integrality for semidefinite programming, first introduced by M. K. Carli Silva and L. Tuncel. We will also present the new results we obtained during this semester.

Title: Formal Method for Verifying the Security Cryptosystems

Speaker: Zhisu Wang

Abstract:

CryptoVerif is a security protocol verifier producing proofs presented as sequences of games, like those manually written by cryptographers. We introduce the basic syntax of CryptoVerif with an example of proving a simple primitive. Then we show the attempts to apply this tool on more complex cryptographic protocols.

Title: Measures of Robustness and Efficiency of Convex Optimization Algorithms

Speaker: Jessica Ding

Abstract:

Interior point method solvers have proven to be an effective tool for solving linear and non-linear convex optimization problems. In this talk I will introduce some measures of robustness and efficiency of convex optimization algorithms as well as intuition behind them. We will learn about the property of ill-poisedness and how it influences the efficiency and correctness of solvers. I will also show some of the results from the experiments we ran over the term.

Ramsey numbers and configurations of finite polar spaces

Abstract: This talk is on some joint work with Anurag Bishnoi and Ferdinand Ihringer, about a simple observation on how Ramsey theory relates to certain induced subgraphs of collinearity graphs arising from finite polar spaces; the natural geometries for the finite simple groups of classical Lie type

A combinatorial proof of an identity involving Eulerian numbers

Abstract:In 2009, Brenti and Welker studied the Veronese construction for formal  power series which was motivated by the corresponding construction for  graded algebras. As a corollary of their algebraic computations, they  discovered an identity for the coefficients of the Eulerian polynomials.  The authors asked for a combinatorial proof of this identity given that  all of its ingredients are enumerative in nature. In this talk I will present one such combinatorial proof. I will gladly do a pre-seminar with the motivation and preliminaries for the talk!