Events

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.