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, November 11, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Linda Cook

Title: Forbidding some induced cycles in a graph

Speaker: Linda Cook
Affiliation: Institute for Basic Science, South Korea
Location: MC 5501 or contact Melissa Cambridge for Zoom link

Abstract:  We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain lengths in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002, Conforti, Cornuéjols, Kapoor, and Vušković provided a structural description of the class of even-hole-free graphs.

Thursday, November 17, 2022 1:00 pm - 1:00 pm EST (GMT -05:00)

Algebraic Graph Theory Seminar - Josip Smolcic

Title: Algorithms for Analytic Combinatorics in Several Variables

Speaker: Josip Smolcic
Affiliation: University of Waterloo
Location: MC 5479

Abstract: In this presentation we will see how to apply the theory of complex analysis to study multivariate generating series by looking at several examples. Specifically, given a rational bivariate generating function G(x, y)/H(x, y) with coefficients f_{i, j} the objective is algorithmically determine asymptotic formulas to approximate f_{rn, sn} as n goes to infinity, for fixed positive integers r and s.

Friday, November 18, 2022 12:00 pm - 12:00 pm EST (GMT -05:00)

Combinatorial Optimization Reading Group - Madison Van Dyk

Title: Approximation algorithms for stochastic orienteering  

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

Abstract: This week we revisit the stochastic orienteering problem in which we are given a metric graph where each node has a deterministic reward and a random size. The goal is to adaptively decide on which nodes to visit to maximize the expected reward, while not exceeding the budget B on the distance plus the size of jobs processed.

Friday, November 18, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Vera Traub

Title: Approximating Weighted Connectivity Augmentation below Factor 2

Speaker: Vera Traub
Affiliation: Research Institute for Discrete Mathematics, University of Bonn
Location: MC 5501 or contact Melissa Cambridge for Zoom link

Abstract:  The Weighted Connectivity Augmentation Problem (WCAP) asks to increase the edge-connectivity of a graph in the cheapest possible way by adding edges from a given set. It is one of the most elementary network design problems for which no better-than-2 approximation algorithm has been known, whereas 2-approximations can be easily obtained through a variety of well-known techniques.

Friday, November 25, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Stefan Weltge

Title: Integer programs with bounded subdeterminants and two nonzeros per row

Speaker: Stefan Weltge
Affiliation: Technical University of Munich
Location: MC 5501 or contact Eva Lee for Zoom link

Abstract: Determining the complexity of integer linear programs with integer coefficient matrices whose subdeterminants are bounded by a constant is currently a very actively discussed question in the field. In this talk, I will present a strongly polynomial-time algorithm for such integer programs with the further requirement that every constraint contains at most two variables. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k = 0 (bipartite graphs) and for k = 1.

This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky, which recently appeared at FOCS this year.

Friday, December 2, 2022 12:00 pm - 12:00 pm EST (GMT -05:00)

Combinatorial Optimization Reading Group - Jacob Skitsko

Title: Boosted Sampling

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

Abstract: We will discuss the boosted sampling technique introduced by Gupta et al. which approximates the stochastic version of problems by using nice approximation algorithms for the deterministic version of the problem. We will focus on rooted stochastic Steiner trees as an example, though other problems are covered by this approach (such as vertex cover and facility location). The problem is given to us in two stages: in the first stage we may choose some elements at a cheaper cost, and in the second stage our actual requirements are revealed to us, and we can buy remaining needed elements at a more expensive cost (where costs get scaled by some factor in the second stage). We will see that if our problem is sub-additive, and we have an alpha-approximation algorithm for the deterministic version of our problem with a beta-strict cost-sharing function then we can get an (alpha + beta)-approximation for the stochastic version of our problem. We also discuss related problems, for example the (not sub-additive!) unrooted stochastic Steiner tree problem.

Friday, December 9, 2022 12:00 pm - 12:00 pm EST (GMT -05:00)

Combinatorial Optimization Reading Group - David Aleman

Title: Approximation algorithm for stochastic k-TSP

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

Abstract: The input of the deterministic k-TSP problem consists of a metric complete graph with root p in which the nodes are assigned a fixed non-negative reward. The objective is to construct a p-rooted path of minimum length that collects total reward at least k. In this talk we will explore a stochastic variant of this problem in which the rewards assigned to the nodes are independent random variables, and the objective is to derive a policy that minimizes the expected length of a p-rooted path that collects total reward at least k. We will discuss approximation algorithms for this problem proposed in a paper by Ene, Nagarajan and Saket, and a paper by Jiang, Li, Liu and Singla.

Friday, December 9, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Vijay Bhattiprolu

Titile: Global geometric reductions for some bottleneck questions in hardness of approximation

Speaker: Vijay Bhattiprolu
Affiliation: University of Waterloo
Location: MC 5501 or contact Eva Lee for Zoom link

Abstract: I will describe the classical "local gadget reduction" paradigm for proving hardness of approximation results and then list some important optimization problems that resist all such attacks. With a focus on problems that can be cast as quadratic maximization over convex sets, I will describe some successes in bypassing the aforementioned bottleneck using ideas from geometry. Time permitting I will also describe some compelling new frontiers where answering some questions in convex geometry could be the path forward.

Tuesday, December 13, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

IQC MATH CS Seminar - Mario Szegedy

Title: Generating k EPR-pairs from an n-party resource state

Speaker: Mario Szegedy
Affiliation: Rutgers University
Location: QNC 0101 or contact Eva Lee for Zoom lin

Abstract: Motivated by quantum network applications over classical channels, we initiate the study of n-party resource states from which LOCC protocols can create EPR-pairs between any k disjoint pairs of parties.

Friday, December 16, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Daniel Panario

Title: Probabilistic root finding in code-based cryptography

Speaker: Daniel Panario
Affiliation: School of Mathematics and Statistics, Carleton University
Location: MC 5501 or contact Eva Lee for Zoom link

Abstract: Factorization of polynomials over finite fields, and the particular subproblem of finding roots of polynomials, have many applications in diverse areas such as computer algebra, cryptography and coding theory, among many others. In practice, fast factorization algorithms are probabilistic.