Events

Title: Fault Tolerant Routing and High Dimensional Expanders

Abstract: We will go over some recent results about fault tolerant routing from Bafna, Minzer, Vyas. Two parallel series of works from the last few years from Bafna, Lifshitz, Minzer, Vyas as well as Dikstein, Dinur, Lubotzky has led to size efficient PCPs by using high dimensional expanders. We will comment on the context for these works, and briefly go over some high level ideas. Then, we will talk about an application to fault tolerant rounding. The goal in this problem is to design a sparse network supporting efficient fault tolerant interactions between all pairs of nodes. Using the size efficient PCP construction, Bafna and Minzer gave a construction of constant degree networks with efficient protocols that tolerate a constant fraction of adversarial edge faults.

Title:Oriented graded Möbius algebras

Abstract:The graded Möbius algebra B(M) of a matroid M contains much combinatorial information about the flats of M. Its algebraic properties were instrumental in the proof of the Dowling—Wilson top-heavy conjecture. We will introduce a skew-commutative analogue OB(M) associated to every oriented matroid M, and discuss its algebraic structure. This is part of ongoing work joint with Yu Li.

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

Title:Worst-case instances of the stable set problem of graphs for the Lovász–Schrijver SDP hierarchy

Abstract:(Based on joint work with Levent Tunçel.)

In this talk, we discuss semidefinite relaxations of the stable set problem of graphs generated by the lift-and-project operator LS_+ (due to Lovász and Schrijver), and present some of our recent progress on this front. In particular, we show that for every positive integer k, the smallest graph with LS_+-rank k contains exactly 3k vertices. This result is sharp and settles a conjecture posed by Lipták and Tunçel from 2003.

The talk will be accessible to a general audience, and does not assume any prior knowledge of lift-and-project methods.

Title:Quasisymmetric Harmonics in Superspace

Abstract: The harmonics of quasisymmetric polynomials in superspace are the  orthogonal complement of the ideal generated by quasisymmetric polynomials without constant term. In this talk, I will discuss the harmonics and present the first basis of this space, which is indexed by a specific family of nested forests.

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

Title:The omega-Condition Number: Applications to Preconditioning and Low Rank Generalized Jacobian Updating

Abstract: Preconditioning is essential in iterative methods for solving linear systems. It is also the implicit objective in updating approximations of Jacobians in optimization methods, e.g.,~in quasi-Newton methods. We study a nonclassic matrix condition number, the omega-condition number}, omega for short. omega is the ratio of: the arithmetic and geometric means of the singular values, rather than the largest and smallest for the classical kappa-condition number. The simple functions in omega allow one to exploit  first order optimality conditions. We use this fact to derive explicit formulae for (i) omega-optimal low rank updating of generalized Jacobians arising in the context of nonsmooth Newton methods; and (ii) omega-optimal preconditioners of special structure for  iterative methods for linear systems. In the latter context, we analyze the benefits of omega for (a) improving the clustering of eigenvalues; (b) reducing the number of iterations; and (c) estimating the actual condition of a linear system. Moreover we show strong theoretical connections between the omega-optimal preconditioners and incomplete Cholesky factorizations, and highlight the misleading effects arising from the inverse invariance of kappa. Our results confirm the efficacy of using the omega-condition number compared to the kappa-condition number.

(Joint work with: Woosuk L. Jung, David Torregrosa-Belen.)

Title:Sizes of witnesses in covtree

Abstract: Here is a purely combinatorial problem that arose in causal set theory.  Let {P_1, ... , P_k} be distinct unlabelled posets all with n elements.  Suppose there is a poset Q such that {P_1, ... , P_k} is exactly the set of downsets of Q of size n up to isomorphism. Given n and k can we give a tight upper bound on the minimum size of such a Q? As with newspaper headlines, the answer to the question is no, at least for the moment, but I'll explain what we do know.  Joint work with Jette Gutzeit, Kimia Shaban, and Stav Zalel.

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

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.

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

Abstract: 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: Circuit partitions of finitary binary matroids

Abstract: 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ó.