Seminar

Title: Interpolating between the characteristic and matching polynomials of a graph

Abstract:

The characteristic polynomial Φ(X, t) of a graph X has two obvious combinatorial connections.

Title: Robust discrete optimization and network flows (paper by Bertsimas and Sim)

Title: Graphs and Unitals

Title: Robust Solutions of Optimization Problems Affected by Uncertain Probabilities (paper by Ben-Tal A et al )

There are 3 short talks this week.

Title: Quantum Collision-Finding in Non-Uniform Random Functions

Abstract: Proving the security of a scheme against a quantum adversary often makes the strong assumption of modelling the hash function as uniformly random. In this work, we study the generic security of non-uniform random functions, specifically those with min-entropy k. This has applications to the quantum security of the Fujisaki-Okamoto transformation, as well as allowing for more relaxed security assumptions. We discuss previous results and sketch a proof for an asymptotic upper and lower bound of 2^k/3 quantum queries. 

Title: Generating Functions: Theory, Algorithms, and Applications

Abstract:

Generating functions are an invaluable tool in many areas of discrete mathematics and beyond.

Title: Erdos-Hajnal meets Gyarfas-Sumner

Abstract:

The Gyarfas-Sumner conjecture says that every graph with huge (enough) chromatic number and bounded clique number contains any given forest as an induced subgraph. (And non-forests do not have this property.)

Title: Knots and their (embedded) graphs

Abstract: 

There is a classical and well-known way to describe an alternating knot or link as a plane graph, known as its Tait graph.

Title: LWE Part 2: A quantum discrete Gaussian sampler.

Abstract: In this talk we will describe how a (quantum) Gaussian sampler could be constructed if we had access to a solver of a decoding problem.

Title: Tractable Approximations to Robust Conic Optimization Problems (paper by D. Bertsimas, M. Sim)

Abstract: We review the paper listed in the title of this talk. In the paper, Bertsimas and Sim propose a relaxed robust counterpart for general conic optimization problems