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:
Thursday, July 28, 2022 1:00 pm - 1:00 pm EDT (GMT -04:00)

Algebraic Combinatorics Seminar - Jinyoung Park

Title: Thresholds

Speaker: Jinyoung Park
Affiliation: Standford University
Location: Please contact Logan Crew for the Zoom link

Abstract: Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will present recent progress on this topic. Based on joint work with Huy Tuan Pham.

Friday, July 29, 2022 1:00 pm - 1:00 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - Rian Neogi

Title: Stochastic Load Balancing on Unrelated Machines

Speaker: Rian Neogi
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for Zoom link

Abstract: We will take a look at the stochastic load balancing problem. The goal is to assign tasks to machines, so that the maximum amount of time taken by any machine to complete all its assigned tasks is minimized. The stochastic twist to this problem is that now the time required to complete each task is a random variable sampled from some known distribution. For the stochastic version, we need to minimize the maximum time taken by any machine in expectation. We will look at a constant factor approximation algorithm for this problem that appeared in a recent paper by Gupta, Kumar, Nagarajan and Shen.

Friday, July 29, 2022 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Amy Wiebe

Title: Non-realizability of polytopes via linear programming

Speaker: Amy Wiebe
Affiliation: UBC Okanagan
Location: MC 5501 or contact Melissa Cambridge for Zoom link

Abstract: A classical question in polytope theory is whether an abstract polytope can be realized as a concrete convex object. Beyond dimension 3, there seems to be no concise answer to this question in general. In specific instances, answering the question in the negative is often done via “final polynomials” introduced by Bokowski and Sturmfels. This method involves finding a polynomial which, based on the structure of a polytope if realizable, must be simultaneously zero and positive, a clear contradiction.

Monday, August 29, 2022 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory Seminar - Yufei Zhao

Title: Equiangular lines and eigenvalue multiplicities

Speaker: Yufei Zhao
Affiliation: Massachusetts Institute of Technology
Location: please contact Sabrina Lato for Zoom link

Abstract: Solving a longstanding problem on equiangular lines, we determine, for each given fixed angle and in all sufficiently large dimensions, the maximum number of lines pairwise separated by the given angle.

Friday, September 9, 2022 1:00 pm - 1:00 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - Nathan Benedetto

Title: Conditional Value-at-Risk

Speaker: Nathan Benedetto
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for the Zoom link

Abstract: The mean and variance of a probability distribution may not reflect what one wants from a scenario involving uncertainty.In particular, such measures fall short of expressing risk in a way suitable for financial and similar applications.

Monday, September 12, 2022 8:00 pm - 8:00 pm EDT (GMT -04:00)

Algebraic Graph Theory Seminar - Qianqian Yang

Title: On sesqui-regular graphs with fixed smallest eigenvalue

Speaker: Qianqian Yang
Affiliation: Shanghai University
Location: Contact Sabrina Lato for Zoom link

Abstract: Let λ ≥ 2 be an integer. For strongly regular graphs with parameters (v, k, a, c) and fixed smallest eigenvalue −λ, Neumaier gave two bounds on c by using algebraic property of strongly regular graphs. Subsequently, we studied a new class of regular graphs called sesqui-regular graphs, which contains strongly regular graphs as a subclass, and proved that for a given sesqui-regular graph with parameters (v, k, c) and smallest eigenvalue −λ, if k is very large, then either c ≤ λ² (λ − 1) or v − k − 1 ≤ (λ−1)²/4 + 1. This is joint work with Jack Koolen, Brhane Gebremichel and Jae Young Yang

Friday, September 16, 2022 1:00 pm - 1:00 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - David Kalichman

Title: Stochastic Probing with Applications

Speaker: David Kalichman
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for Zoom link

Abstract:  We will explore a stochastic probing problem. Given a set of elements which have weights and independent probabilities of being "active," the goal is to construct a subset of active elements of maximum weight. To form such a set, we must "probe" elements sequentially to determine whether they are active.

Friday, September 16, 2022 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Lap Chi Lau

Title: Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues

Speaker: Lap Chi Lau
Affiliation: University of Waterloo
Location: MC 5501

Abstract:

The classical Cheeger's inequality relates the edge conductance $\phi$ of a graph and the second smallest eigenvalue $\lambda_2$ of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality $\psi^2 / \log |V| \lesssim \lambda_2^* \lesssim \psi$ connecting the vertex expansion $\psi$ of a graph $G=(V,E)$ and the maximum reweighted second smallest eigenvalue $\lambda_2^*$ of the Laplacian matrix. In this work, we first improve their result to $\psi^2 / \log d \lesssim \lambda_2^* \lesssim \psi$ where $d$ is the maximum degree in $G$, which is optimal assuming the small-set expansion conjecture. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti. 

Monday, September 19, 2022 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory Seminar - Qianqian Yang

Title: Essential Covers of the Cube by Hyperplanes

Speaker: Igor Araujo
Affiliation: University of Illinois Urbana-Champaign
Location: contact Sabrina Lato for Zoom link

Abstract:  An essential cover of the vertices of the n-cube $\{0,1\}^n$ by hyperplanes is a minimal covering where no hyperplane is redundant, and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with $\lceil \frac{n}{2} \rceil + 1$ hyperplanes and showed that $\Omega(\sqrt{n})$ hyperplanes are required.