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

Monday, December 12, 2022 11:30 am - 11:30 am EST (GMT -05:00)

Algebraic Graph Theory Seminar - Venkata Raghu Tej Pantangi

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.

Monday, December 12, 2022 3:00 pm - 3:00 pm EST (GMT -05:00)

Graphs and Matroid Seminar - Cléophée Robin

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 :

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.