À¶Ý®ÊÓƵ

Title:ÌýExcluding claws in binary matroids

´¡²ú²õ³Ù°ù²¹³¦³Ù:ÌýA simple binary matroid is claw-free if no rank-3 flats are independent. We discuss an exact structure theorem for such matroids and sketch its proof. This is joint work with Peter Nelson.

Title:ÌýMorphisms of complex Hadamard matrices

Abstract:

Let M be a matrix with complex entries of unit norm. A well-known theorem of Hadamard bounds the magnitude of the determinant of M as a function of its dimension, and M is a complex Hadamard matrix if M meets Hadamard's bound with equality.

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:ÌýImplementing cryptography at scale 

Abstract:ÌýMany cryptographic primitives have rough edges which make them difficult to use properly (by both experts and non-experts).

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

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.

There are 3 short talks this week.

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

´¡²ú²õ³Ù°ù²¹³¦³Ù:Ìý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: 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:ÌýRobust Solutions of Optimization Problems Affected by Uncertain Probabilities (paper by Ben-Tal A et alÌý)

Title: Graphs and Unitals