#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Friday, December 16, 2022 — 3:30 PM EST

**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.

Tuesday, December 13, 2022 — 3:30 PM EST

**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.

Monday, December 12, 2022 — 3:00 PM EST

**Title:** When all holes have the same length

Speaker: | Cléophée Robin |

Affiliation: | University of Waterloo |

Location: | MC 6029 |

**Abstract:** A *hole* is an induced cycle of length at least 4. For an integer k ≥ 4, we denote by Ck, the class of graphs where every hole has length k. We have defined a new class of graphs named *blowup of ℓ-templates* whose all holes have length 2ℓ + 1. Using earlier results on other related classes of graphs, we did obtain the following structural theorem :

Monday, December 12, 2022 — 11:30 AM EST

**Title:** Cameron-Liebler Sets in Permutation Groups

Speaker: | Venkata Raghu Tej Pantangi |

Affiliation: | University of Regina |

Location: | Contact Sabrina Lato for Zoom link |

**Abstract:** Let $G \leq S_{n}$ be a transitive permutation group. Given $i,j \in [n]$, by $x_{i\to j}$, denote the characteristic function of the set $\{g \in G\ :\ g(i)=j\}$. A Cameron-Liebler set (CL set) in $G$ is a set which is represented by a Boolean function in the linear span of $\{x_{i\to j} \ :\ (i,j)\in [n]^2\}$. These are analogous to Boolean degree 1 functions on the hypercube and to Cameron-Liebler line classes in $PG(3,q)$. Sets of the form $\{g\ : g(i)\in X\}$ and $\{g\ : \ i \in g(X)\}$ (for $i \in [n]$ and $X \subset [n]$) are canonically occurring examples of CL sets. A result of Ellis et.al, shows that all CL sets in the $S_{n}$ are canonnical. In this talk, we will demonstrate many examples with ``exotic'' CL sets. Of special interest is an exotic CL set in $PSL(2,q)$ (with $q \equiv 3 \pmod{4}$), a 2-transitive group, just like $S_{n}$. The talk is based on ongoing joint work with Jozefien D'haeseleer and Karen Meagher.

Friday, December 9, 2022 — 3:30 PM EST

**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.

Friday, December 9, 2022 — 12:00 PM EST

**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 2, 2022 — 12:00 PM EST

**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.

Thursday, December 1, 2022 — 1:00 PM EST

**Title:** Algebraicity of solutions of functional equations with one catalytic variable

Speaker: | Sergey Yurkevich |

Affiliation: | University Paris-Saclay |

Location: | MC 5479 or contact Olya Mandelshtam for Zoom link |

**Abstract:** Abstract: Numerous combinatorial enumeration problems reduce to the study of functional equations which can be solved by a uniform method introduced by Bousquet-Mélou and Jehanne in 2006. In my talk, I will first briefly explain this result and its proof. Then I will present a new generalization of it to the case of systems of functional equations with one catalytic variable. The method is constructive and yields an algorithm for computing the minimal polynomials of interest.

Monday, November 28, 2022 — 3:00 PM EST

**Title:** *k-*Connectedness and *k*-Factors in the Semi-Random Graph Process

Speaker: | Hidde Koerts |

Affiliation: | University of Waterloo |

Location: | MC 6029 |

**Abstract:** The semi-random graph process is a single player graph game where the player is initially presented an edgeless graph with n vertices. In each round, the player is offered a vertex u uniformly at random and subsequently chooses a second vertex v deterministically according to some strategy, and adds edge uv to the graph. The objective for the player is then to ensure that the graph fulfils some specified property as fast as possible.

Monday, November 28, 2022 — 11:30 AM EST

**Title:** A recursive spectral bound for independence

Speaker: | Bogdan Nica |

Affiliation: | Indiana University-Purdue University Indianapolis |

Location: | Contact Sabrina Lato for Zoom link |

**Abstract:** We discuss an upper bound for the independence number of a graph, in the spirit of the well-known Hoffman bound. Our bound involves the largest Laplacian eigenvalue of the graph; more surprisingly, it also involves the independence number of a certain induced graph. We illustrate the bound on several examples.

Friday, November 25, 2022 — 3:30 PM EST

**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, November 25, 2022 — 12:00 PM EST

Title: Greedy algorithm for stochastic matching is a 2-approximatio

Speaker: | Ian DeHaan |

Affiliation: | University of Waterloo |

Location: | MC 6029 or contact Rian Neogi for Zoom link |

Abstract: We will discuss the greedy algorithm for the stochastic matching problem. In this problem, we are given an undirected graph where each edge is assigned a probability p_e in [0, 1] and each vertex is assigned a patience t_v in Z+. We begin each step by probing an edge e which is not adjacent to any edges in our matching. The probe will succeed with probability p_e, and if it does, we add e to our matching. Otherwise, we may not probe e again. We also may not probe edges adjacent to a vertex v more than t_v times. The goal is to maximize the number of edges we add to our matching.

Thursday, November 24, 2022 — 1:00 PM EST

**Title:** Asymptotics of the Euler characteristic of Kontsevich's commutative graph complex

Speaker: | Michael Borinsky |

Affiliation: | ETH, Zurich |

Location: | MC 5479 or contact Olya Mandelshtam for Zoom link |

**Abstract: **I will present results on the asymptotic growth rate of the Euler characteristic of Kontsevich's commutative graph complex. By a work of Chan-Galatius-Payne, these results imply the same asymptotic growth rate for the top-weight Euler characteristic of M_g, the moduli

space of curves, and establish the existence of large amounts of unexplained cohomology in this space. This asymptotic growth rate

follows from new generating functions for the edge-alternating sum of graphs without odd automorphisms. I will give an overview on this

interaction between topology and combinatorics and illustrate the combinatorial and analytical tools that were needed to obtain these

generating functions.

Monday, November 21, 2022 — 6:00 PM EST

**Title:** Exact Zarankiewicz numbers through linear hypergraphs

Speaker: | Daniel Horsley |

Affiliation: | Monash University |

Location: | Contact Sabrina Lato for Zoom link |

**Abstract:** The \emph{Zarankiewicz number} $Z_{2,2}(m,n)$ is usually defined as the maximum number of edges in a bipartite graph with parts of sizes $m$ and $n$ that has no $K_{2,2}$ subgraph. An equivalent definition is that $Z_{2,2}(m,n)$ is the greatest total degree of a linear hypergraph with $m$ vertices and $n$ edges. A hypergraph is \emph{linear} if each pair of vertices appear together in at most one edge. The equivalence of the two definitions can be seen by considering the bipartite incidence graph of the linear hypergraph.

Friday, November 18, 2022 — 3:30 PM EST

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 18, 2022 — 12:00 PM EST

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.

Thursday, November 17, 2022 — 1:00 PM EST

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.

Monday, November 14, 2022 — 3:00 PM EST

Title: The Hat Guessing Number of Graphs

Speaker: | Jeremy Chizewer |

Affiliation: | University of Waterloo |

Location: | MC 6029 |

Abstract: The hat guessing number *HG(G)* of a graph *G* on *n* vertices is defined in terms of the following game: *n* players are placed on the *n* vertices of *G*, each wearing a hat whose color is arbitrarily chosen from a set of *q* possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. The hat guessing number *HG(G)* is the largest integer *q* such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of *q* possible colors.

Monday, November 14, 2022 — 11:30 AM EST

Title: Graphs, curvature, and local discrepancy

Speaker: | Paul Horn |

Affiliation: | University of Denver |

Location: | contact Sabrina Lato for Zoom link |

Abstract: Spectral graph theory, the use of eigenvalues to study graphs, gives an important window into many properties of graphs. One of the reasons for this is that the eigenvalues can be used to certify the `pseudo-randomness' of the edge set of a graph. In recent years, several notions of discrete curvature have been introduced that gives a 'local' way (depending on the neighborhood structure of vertices) to study some of the same properties that eigenvalues can capture.

Friday, November 11, 2022 — 3:30 PM EST

**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.

Friday, November 11, 2022 — 12:00 PM EST

Title: Stochastic Minimum Norm Combinatorial Optimization

Speaker: | Sharat Ibrahimpur |

Affiliation: | |

Location: | MC 6029 or contact Rian Neogi for Zoom link |

Abstract: In this work, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector. The goal is to find a solution that minimizes the expected norm of the induced cost vector, for a given monotone, symmetric norm. We give a framework for designing approximation algorithms for stochastic minimum-norm optimization and apply it to give approximation algorithms for stochastic minimum-norm versions of load balancing and spanning tree problems.

Thursday, November 10, 2022 — 1:00 PM EST

**Title**: Recursions and Proofs in Coxeter-Catalan combinatorics

Speaker: | Theo Douvropoulos |

Affiliations: | U Mass Amherst |

Location: | MC 5479 or contact Olya Mandelshtam for Zoom link |

**Abstract:** The collection of parking functions under a natural Sn-action (which has Catalan-many orbits) has been a central object in Algebraic Combinatorics since the work of Haiman more than 30 years ago. One of the lines of research spawned around it was towards defining and studying analogous objects for real and complex reflection groups W; the main candidates are known as the W-non-nesting and W-non-crossing parking functions.

Monday, November 7, 2022 — 11:00 AM EST

**Title:** Cayley graphs, association schemes and state transfer

Speaker: | Soffía Árnadóttir |

Affiliation: | Technical University of Denmark |

Location: | contact Sabrina Lato for Zoom link |

**Abstract: **The aim of this talk is to give some examples of how association schemes can be used as a tool to study certain properties of Cayley graphs. In particular, they contribute to our long-term goal of characterizing perfect state transfer in Cayley graphs. The talk is based on the following paper https://arxiv.org/abs/2204.09802.

Friday, November 4, 2022 — 3:30 PM EDT

**Title:** Sylvester, Gallai, and their complex relatives

Speaker: | Jim Geelen |

Affiliation: | University of Waterloo |

Location: | MC 5501 or contact Melissa Cambridge for Zoom link |

**Abstract:** Given any finite set of points in the real plane, not all collinear, there is a line in the plane that contains exactly two of them. This pretty result was conjectured by Sylvester in 1893 and proved by Gallai in 1944. We will present an extension of the result to higher dimensional complex spaces and discuss some related conjectures. This is joint work with Matthew Kroeker.

Friday, November 4, 2022 — 12:00 PM EDT

**Title**: Approximation Algorithms for Stochastic Knapsack

Speaker: | David Aleman |

Affiliation: | University of Waterloo |

Location: | MC 6029 or contact Rian Ne |

**Abstract**: The classical Knapsack problem takes as input a set of items with some fixed nonnegative values and weights. The goal is to compute a subset of items of maximum total value, subject to the constraint that the total weight of these elements is at most a given limit. In this talk we review a paper by Gupta, Krishnaswamy, Molinaro and Ravi, in which the following stochastic variation of this problem is considered: the value and weight of each item are correlated random variables with known, arbitrary distributions.

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Office of Indigenous Relations.