Title: URA Presentations
| Speakers: | Michael Xu, Yundi Duan, Thomas Snow |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract: A series of presentations by a group of Spring 2023 Undergraduate Research Assistants. The topics of each presentation are detailed below.
Colourings and List Colourings - Michael Xu
Normal colorings have been studied for decades due to its simplicity. However, a completely different scenario happens if we give constraints to which color to use, named list coloring. In this talk, we will go through how list coloring differs from normal coloring, and some basics of list colorings.
Online Matchings Under Edge Arrivals - Thomas Snow
A brief introduction to online algorithms in the context of matchings under adversarial edge arrivals, specifically with respect to bipartite graphs of maximum degree. We introduce the different type of algorithms for this problem and give bounds on their performance, including a framework of randomized algorithms developed by Niv Buchbinder, Danny Segev, and Yevgeny Tkach. Moreover, we analyze the relationship between these algorithms in the case of bipartite graphs of maximum degree.
On analyzing the grid-search algorithm to approximate the maximum of a homogeneous polynomials over the standard simplex - Yundi Duan
Finding the maximum/minimum of a homogeneous polynomial over the standard simplex is known to be NP-hard — the maximum stable set problem can be reduced to a quadratic optimization problem over the simplex due to Motzkin and Straus (1965). However, it has been shown that there is a polynomial-time approximation scheme for the problem due to Klerk, Laurent, and Parrilo using the grid search algorithm (2006). By their analysis, we know that we can approximate the answer within a factor of C_d*(1+epsilon) using a grid of size r, where C_d is a constant that only depends on d, the degree of the polynomial (2015). However, the upperbound for C_d given in the current approach is at least in an order of Omega(d^d). Inspired by a similar problem over the unit sphere, we conjecture that the upper bound for C_d can be reduced to an order of 2^O(d). We will present some partial results toward this goal.