À¶Ý®ÊÓƵ

°Õ¾±³Ù±ô±ð:ÌýThere are no good infinite families of toric codes

´¡²ú²õ³Ù°ù²¹³¦³Ù:Ìý: In this talk we'll give an overview of what toric codes are and what it means for a code to be "good". We'll explain why it is impossible to construct an infinite family of good toric codes, answering a question of Soprunov and Soprunova. This is joint work with Sean Monahan, Matt Satriano, Karen Situ, and Zheng Xie.Ìý

°Õ¾±³Ù±ô±ð:ÌýDeterministic Algorithms and Faster Algorithms for Submodular Maximization subject to a Matroid Constraint

´¡²ú²õ³Ù°ù²¹³¦³Ù:ÌýMaximization of submodular functions under various constraints is a fundamental problem that has been studied extensively.

In this talk I will discuss submodular functions and interesting research questions in the field.

I will present several new techniques that lead to both deterministic algorithms and faster randomized algorithms for maximizing submodular functions.

In particular, for monotone submodular functions subject to a matroid constraint we design a deterministic non-oblivious local search algorithm that has an approximation guarantee of 1 - 1/e - \eps (for any \eps > 0), vastly improving over the previous state-of-the-art 0.5008-approximation.

For general (non-monotone) submodular functions we introduce a new tool, that we refer to as the extended multilinear extension, designed to derandomize submodular maximization algorithms that are based on the successful ``solve fractionally and then round'' approach.

Short bio: Niv Buchbinder is a professor in the department of Statistics and Operations Research at Tel Aviv university.ÌýHe received his Ph.D. in Computer Science from the Technion, Israel in 2008, and then spent two years as a post-doctoral researcher at Microsoft Research, New England, MA. His primary research interests are algorithms for combinatorial optimization problems in offline and online settings.

Title:ÌýApproximating Distances on Undirected Graphs

´¡²ú²õ³Ù°ù²¹³¦³Ù:ÌýThe shortest path metric on undirected graphs is a fundamental quantity with deep connections to combinatorics and structural graph theory. Tools built around such approximations are playing increasingly important role in efficient optimization algorithms and data structures. This talk will introduce such approximations starting from the breadth first search tree, and build upon them to discuss distance oracles and oblivious routings.

Title: Multivariate Limit Theorems and Algebraic Generating Functions

Abstract: The field of analytic combinatorics in several variables

(ACSV) is dedicated to the creation of effective techniques to study the large-scale behaviour of combinatorial objects. This talk provides results for two areas of ACSV: limit theorems and asymptotics of algebraic generating functions. First, I will describe an automated approach to proving local central limit theorems and its applications to a variety of examples. Included in these examples will be a family of permutations with restricted cycles, integer compositions with tracked summands and n-colour compositions with tracked summands. The second half of the talk will survey techniques for analyzing multivariate algebraic generating functions, going into detail specifically for the process of embedding an algebraic generating function into a sub-series of a rational function of more variables. For both parts of the talk, SageMath code which automates the methods discussed will be demonstrated for various examples.

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

Kai Choi

Title:Alice in Quadraticspanningforestidentityspace

´¡²ú²õ³Ù°ù²¹³¦³Ù:ÌýQuantum field theorists study Feynman periods, which are obtained by integrating expressions related to the spanning tree polynomials of graphs known as Feynman diagrams. But if you are like me and know nothing about physics, the good news is that doing quantum field theory often leads one to play with combinatorial objects. In particular, if one wishes to efficiently compute Feynman periods, they would likely be faced with unanswered questions about set partitions, determinantal identities, spaces of polynomials, and the all-minors matrix-tree theorem, many of which are quite accessible. I will present these questions and their relevant background in the context of my work on spaces of quadratic spanning forest identities, supervised by Dr. Karen Yeats.

Peiran Tao

Title:Alice in Quadraticspanningforestidentityspace

´¡²ú²õ³Ù°ù²¹³¦³Ù:ÌýIt is a classical theorem that the diagonal of any bivariate rational power series is algebraic; that is, it satisfies a polynomial equation. We will discuss an algorithm that efficiently computes this polynomial.

Given a rational generating function F(z_1,...,z_d) we are interested in the asymptotic behaviour of its coefficient sequence in a specified direction (r_1,...,r_d). Although this problem is difficult in general, when d=2 and when some conditions are satisfied, there is a known algorithm that resolves it. We will explain the basics of analytic combinatorics in several variables and show how this algorithm operates.

Stephanie Penner

Title: Combinatorial Exploration: Counting Chord Diagrams

Abstract: It can often be tricky to find a combinatorial specification of a counting sequence for a given set of objects. A recently developed framework called "Combinatorial Exploration" aims to automate the process of finding combinatorial specifications. It has successfully been used to find specifications for several new permutation classes and looks promising for several other objects. In this talk, I will briefly explain how Combinatorial Exploration works, and how I am using it to automate finding specifications for families chord diagrams.

Title:ÌýCircuit partitions of finitary binary matroids

´¡²ú²õ³Ù°ù²¹³¦³Ù:ÌýNash-Williams showed in 1960 that a (possibly infinite) graph can be expressed as a union of edge-disjoint cycles if and only if it has no odd cut. Recently, Joó extended this result to directed graphs, showing that a directed graph can be expressed as a union of edge-disjoint directed cycles if and only if every cut contains the same number of edges in each direction. We extend these results to finitary binary matroids. This is joint work with Attila Joó.

°Õ¾±³Ù±ô±ð:ÌýThe Landscape of Quantum Computing

´¡²ú²õ³Ù°ù²¹³¦³Ù:ÌýQuantum computers will be able to break all the cryptography we have relied on for the last 4 decades, but when will they have this power? In this talk I will give a high-level overview of where quantum computing technologies are today, the path they will need to take, and what kind of discoveries could help or hinder progress in quantum computing.

Title:Ìý: Optimal Item Pricing in Online Combinatorial Auctions

Abstract:ÌýI will present a paper by Correa, Cristi, Fielbaum, Pollner, and Weinberg. The paper studies the online combinatorial auction problem when buyers are interested in sets of size at most d. They show that there exist item prices such that the posted price mechanism under these prices results in an allocation that is (d+1)-approximate with respect to the offline benchmark. They show the existence of these prices through a novel use of Brouwer's fixed point theorem.

Title:Learning quantum states

´¡²ú²õ³Ù°ù²¹³¦³Ù:ÌýSuppose we are given a sequence of quantum registers initialized to theÌýsame quantum state rho, and would like to learn the state rho. That is,Ìýwe would like to design an algorithm that produces a classicalÌýdescription of an approximation to the state. How many copies of rho dowe need to be able to produce a suitable approximation? This talk willÌýbe a gentle introduction to the problem and related results.

Ìý

Title:Automated Sequence Asymptotics

Abstract:Computing with any sort of object requires a way of encoding it on a computer, which poses a problem in enumerative combinatorics where the objects of interest are (infinite) combinatorial sequences. Thankfully, the generating function of a combinatorial sequence often satisfies natural algebraic/differential/functional equations, which can then be viewed as data structures for the sequence. In this talk we survey methods to take a sequence encoded by such data structures and automatically determine asymptotic behaviour using techniques from the field of analytic combinatorics. We also discuss methods to automatically characterize the asymptotic behaviour of multivariate sequences using analytic combinatorics in several variables (ACSV). The focus of each topic will be rigorous algorithms that have already been implemented in computer algebra systems and can be easily used by anyone.

Ìý