Events

Abstract: I will go over the recent paper by Sahil Singla proving Matroid Secretary Conjecture.

Abstract: I will introduce a family of commuting derivations on the ring of symmetric polynomials. Using this family I will then define an apparently-novel family of symmetric functions that is vertical-strip LLT positive and relates directly to the Theta operators of D'Adderio–Iraci–Vanden Wyngaerd. Finally I'll discuss some consequences for the "higher order" Macdonald positivity conjecture of Dołęga. This is joint work with Jim Haglund.

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

Abstract: For positive integers $s$ and $n$, let $f_{s}(n)$ denote the maximum $k$ such that every $n$-vertex $K_{s+1}$-free graph contains an induced $K_s$-free subgraph with $k$ vertices. These are the Erd\H{o}s-Rogers functions, introduced by Erd\H{o}s and Rogers in 1962, and are generalizations of Ramsey numbers.

In this talk we survey recent progress, culminating with the recent result of Morris, Saharasbudhe which finally determines the order of magnitude of the Erd\H{o}s-Rogers functions.

Joint work with Rob Morris and Julian Saharasbudhe.

Abstract: In this talk, I will go over the construction that shows a lower bound of d/log(d) for the prophet inequality, where the feasible set is the intersection of d matroids. This talk is based on the paper "A Nearly Tight Lower Bound for Matroid Intersection Prophet Inequalities" by Dimitris Fotakis, Charalampos Platanos, Thanos Tolias.

Abstract: Let T be a tree with bipartition class sizes t_1>=t_2. Motivated by two simple lower bound constructions, Burr conjectured that the Ramsey number of T, denoted by R(T), is exactly max{t_1+2t_2,2t_1}-1. While this conjecture turns out to be false, all known counterexamples have large maximum degrees. In a joint work with Richard Montgomery and Matías Pavez-Signé, we show that there exists a constant c>0, such that Burr's conjecture does hold if T has maximum degree at most c(t_1+t_2). In particular, this determines the exact Ramsey numbers of a large family of trees. In this talk, I will go over some background on tree embeddings, and give an overview of our proof. 

Abstract: Equipped with the knowledge of quantum information, we present how to use quantum states to build a quantum algorithm. While classical circuits represent how one makes algorithms using the bits 0 and 1, quantum circuits represent how one makes algorithms using qubits $\ket{\alpha} = \alpha_0 \ket{0} + \alpha_1\ket{1}$. In this presentation, we will introduce the definition and presentation of quantum gates. Starting with 1-qubit gates and expanding to n-qubit gates. We also present the standard gates such as the Pauli Gates, CNOT, CCNOT, SWAP, etc. Then we proceed to see the effects and interactions of these gates along with some measurements.

Abstract: Tiling enumerations problems have fascinating connections with many other combinatorial problems involving perfect matchings, lattice paths, and determinants. In this talk, I will briefly survey some of the classical results and methods in this area. Then, I will present a new result enumerating lozenge tilings of a triangular region. Interestingly, the formula, reminiscent of the famous Kasteleyn formula counting domino tilings of the rectangle, contains roots of unity and does not obviously output an integer.

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

Abstract: Quantum money is one of the earliest ideas in quantum cryptography: a banknote is represented by a quantum state that cannot simply be copied. Wiesner’s original proposal required the bank to verify every transaction, motivating the notion of public-key quantum money, where anyone can verify a banknote while only the bank can create new ones.

In this talk, I will trace the story of quantum money from Wiesner’s scheme, through the hidden-subspace construction of Aaronson and Christiano, to Zhandry’s recent construction from abelian group actions. I will discuss why previous proposals were either broken or relied on non-standard assumptions, and then present recent work showing that Zhandry’s construction can be based, in the generic group-action model, on the standard group-action discrete logarithm assumption. I will conclude with the main idea behind the security proof.

Abstract: It is well known that the maximum cut size of a graph is at least half its number of edges. But how small can this difference be? Using random hyperplane rounding, a technique from semidefinite optimization, Balla, Janzer, and Sudakov obtained a lower bound on this difference in terms of the vector chromatic number, recovering known extremal bounds for $C_r$-free graphs. I will present their argument and show that the constant in their vector-chromatic bound is optimal by constructing a random sphere graph.

Abstract: Quantum Key Distribution (QKD) uses the laws of Quantum Mechanics to allow two parties to produce a shared secret key only known to them without it's security relying on the computational hardness. In this presentation, we will introduce the QKD protocol BB84, and present how it is secure against various attacks. We will also discuss two major phases in BB84: the information reconciliation phase between keys of sender and receiver via error correcting codes and the privacy amplification phase where two communicating parties distill highly secret shared key from a larger body of a shared key, which is only partially secret. Finally, we will give a brief overview of Muckle-based hybrid authenticated key exchange (AKE) protocols.