Events

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Friday, July 17, 2020 1:30 pm - 1:30 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - Nishad Kothari

Title: Two unsolved problems: Birkhoff--von Neumann graphs and PM-compact graphs

Speaker: Nishad Kothari
Affiliation: CSE Department, Indian Institute of Technology Madras
Zoom: Contact Sharat Ibrahimpur

Abstract:

A well-studied object in combinatorial optimization is the {\it perfect matching polytope} $\mathcal{PMP}(G)$ of a graph $G$ --- the convex hull of the incidence vectors of all perfect matchings of $G$. A graph $G$ is {\it Birkhoff--von Neumann} if $\mathcal{PMP}(G)$ is characterized solely by non-negativity and degree constraints, and $G$ is {\it PM-compact} if the combinatorial diameter of $\mathcal{PMP}(G)$ equals one.

Friday, July 17, 2020 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Shachar Lovett

Title: Point Location and Active Learning - Learning Halfspaces Almost Optimally

Speaker: Shachar Lovett
Affiliation: UC San Diego
Zoom: Please email Emma Watson

Abstract:

The point location problem is a central problem in computational geometry. It asks, given a known partition of R^d by n hyperplanes, and an unknown input point, to find the cell in the partition to which the input point belongs. The access to the input is via linear queries. A linear query is specified by an hyperplane, and the result of the query is which side of the hyperplane the input point lies in.

Monday, July 20, 2020 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory Seminar - Karen Meagher

Title: Group Theory and the Erd\H{o}s-Ko-Rado (EKR) Theorem

Speaker: Karen Meagher
Affiliation: University of Regina
Zoom: Contact Soffia Arnadottir

Abstract: 

Group theory can be a key tool in sovling problems in combinatorics; it can provide a clean and effective proofs, and it can give deeper understanding of why certain combinatorial results hold. My research has focused on the famous Erd\H{o}s-Ko-Rado (EKR) theorem.

Thursday, July 23, 2020 2:30 pm - 2:30 pm EDT (GMT -04:00)

Algebraic Combinatorics Seminar - Marcel Golz

Title: Chord diagrams, colours, and QED

Speaker: Marcel Golz
Affiliation: University of Waterloo
Zoom: Contact Karen Yeats

Abstract:

Feynman graphs in quantum electrodynamics are essentially chord diagrams with photon edges taking the role of chords attached to lines or cycles given by electron edges. The associated Feynman integrals involve traces of Dirac gamma matrices whose computation leads to large sums of scalar Feynman integrals (cf. the earlier talk by O. Schnetz).

Friday, July 24, 2020 1:30 pm - 1:30 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - Sharat Ibrahimpur

Title: A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case

Speaker: Sharat Ibrahimpur
Affiliation: University of Waterloo
Zoom: Contact Sharat Ibrahimpur

Abstract:

Given a connected undirected graph G on n vertices, and non-negative edge costs c, the 2ECM problem is that of finding a 2-edge connected spanning multisubgraph of G of minimum cost. The natural linear program (LP) for 2ECM, which coincides with the subtour LP for the Traveling Salesman Problem on the metric closure of G, gives a lower bound on the optimal cost.

Friday, July 24, 2020 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Hamza Fawzi

Title: Semidefinite programming representations for separable states

Speaker: Hamza Fawzi
Affiliation: University of Cambridge
Zoom: Please email Emma Watson

Abstract:

The set of separable (i.e., non-entangled) bipartite states is a convex set that plays a fundamental role in quantum information theory. The problem of optimizing a linear function on the set of separable states is closely related to polynomial optimization on the sphere. After recalling the sum-of-squares hierarchy for this problem, I will show bounds on the rate of convergence of this SDP hierarchy; and prove that the set of separable states has no SDP representation of finite size.

Monday, July 27, 2020 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory Seminar - Chris Godsil

Title: Continuous Quantum Walks on Graphs

Speaker: Chris Godsil
Affiliation: University of Waterloo
Zoom: Contact Soffia Arnadottir

Abstract:

A quantum walk is a (rather imperfect analog) of a random walk on a graph. They can be viewed as gadgets that might play a role in quantum computers, and have been used to produce algorithms that outperform corresponding classical procedures.

Thursday, July 30, 2020 2:30 pm - 2:30 pm EDT (GMT -04:00)

Algebraic Combinatorics Seminar - Gilyoung Cheong

Title: P\'olya enumeration theorems in algebraic geometry

Speaker: Gilyoung Cheong
Affiliation: University of Michigan
Zoom: Contact Karen Yeats

Abstract:

We will start by comparing Macdonald's formula of the generating function for the symmetric powers of a compact complex manifold and Grothendieck's formula of the zeta series of a projective variety over a finite field, an explicit version of Dwork's rationality result.

Friday, July 31, 2020 1:30 pm - 1:30 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - Haripriya Pulyassary

Title: Weighted Maximum Multicommodity Flows over time

Speaker: Haripriya Pulyassary
Affiliation: University of Waterloo
Zoom: Contact Sharat Ibrahimpur

Abstract:

In various applications, flow does not travel instantaneously through a network, and the amount of flow traveling on an edge may vary over time. This temporal dimension is not captured by the classic static network flow models but can be modeled using flows over time. 

Friday, July 31, 2020 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Jim Luedtke

Title: Data-Driven Sample-Average Approximation for Stochastic Optimization with Covariate Information

Speaker: Jim Luedtke
Affiliation: University of Wisconsin-Madison
Zoom: Please email Emma Watson

Abstract:

We consider optimization models for decision-making in which parameters within the optimization model are uncertain, but predictions of these parameters can be made using available covariate information.  We consider a data-driven setting in which we have observations of the uncertain parameters together with concurrently-observed covariates.  Given a new covariate observation, the goal is to choose a decision that minimizes the expected cost conditioned on this observation.  We investigate a data-driven framework in which the outputs from a machine learning prediction model are directly used to define a stochastic programming sample average approximation (SAA).