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

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.