Computer Science Thesis Proposal

Friday, May 3, 2019 - 2:00pm to 3:00pm

Location:

8102 Gates Hillman Centers

Speaker:

YU ZHAO, Ph.D. Student https://www.cs.cmu.edu/~yuzhao1/

Generations and Applications of Hypercontractivity and Small-Set Expansion

The hypercontractivity inequalities and the small-set expansion are two fundamental topics very related to each other and play important roles in every elds and several recent breakthroughs in theoretical computer science. This thesis proposal is focused on generalizations and applications of hypercontractivity and small-set expansion such as (i) pseudorandom-set expansion, (ii) communication distillation, (iii) decouping, and (iv) property testing on k-wise uniformity. For each of these problems, we try to propose new algorithms, improve complexity measures or give better bounds.

Thesis Committee:
Ryan O'Donnell (Chair)
Venkatesan Guruswami
Anupam Gupta
Rocco Servedio (Columbia University)

Copy of Proposal Summary
 

For More Information, Contact:

Keywords:

Thesis Proposal