[Colloquium] Reminder - Hing Yin Tsang Candidacy Exam/May 31, 2024

[Megan Woodward via Colloquium]

This is an announcement of Hing Yin Tsang's Candidacy Exam.
===============================================
Candidate: Hing Yin Tsang

Date: Friday, May 31, 2024

Time:  3 pm CT

Location: JCL 390

Title: Induced subgraphs of Cayley graphs and beyond

Abstract: It was known since the early 90s that the following two statements are equivalent:
1. The decision tree complexity is polynomial related to the sensitivity for any Boolean function.
2. Any induced subgraph on more than half of the vertices of the $n$-dimensional Boolean hypercube has maximum degree at least $n^c$ for some constant $c > 0$.

The first statement was known as the Sensitivity Conjecture and it remained open until Hao Hunag proved the second statement in 2019 with the optimal constant $c = 1/2$ using a beautiful spectral argument. Huang's Theorem initiated a line of work on studying similar properties for induced subgraphs of graphs other than the Boolean hypercubes.

In this talk, we will discuss the follow up works on Huang's result. In particular, we will discuss extension of Huang's Theorem to other graphs including abelian Cayley graphs, and show examples of non-abelian Cayley graphs that have induced 1-regular subgraph on more than half of the vertices.

Advisors: Aaron Potechin

Committee Members: Madhur Tulsiani, Aaron Potechin, and Janos Simon











-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240531/2102c6a8/attachment-0001.html>