Computer Science Thesis Oral

Thursday, August 26, 2021 - 9:00am to 11:00am

Location:

Virtual Presentation - ET Remote Access - Zoom

Speaker:

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

Generalizations and Applications of Hypercontractivity and Small-Set Expansion

Hypercontractive inequalities and small-set expansion are two fundamental topics closely related to each other and play important roles in many fields. This thesis studies generalizations and applications of hypercontractivity and small-set expansion in the following areas:

  • The recent breakthrough proof of the 2-to-2 games conjecture was completed by showing a pseudorandom-set expansion result on Grassmann graphs. We prove the pseudorandom-set expansion result on general product probability spaces, with a very clean and short proof.
  • ┬áThe communication-assisted agreement distillation problem is about two parties with noisy private randomness trying to extract a common random string via communication. We give the optimal upper bound on the amount of communication necessary for achieving constant success probability for this problem. The proof technique is highly related to the equivalence of hypercontractivity and small-set expansion.
  • "Decoupling" refers to the idea of analyzing a complicated random sum involving dependent random variables by comparing it to a simpler random sum where some independence is introduced between the variables. We present a new decoupling method and combine it with hypercontractivity to show tight tail bounds of low-degree Boolean functions and tight versions of several theorems from [DFKO07].
  • k-wise uniform distributions have the property that all low-degree Fourier coefficients of their density functions are equal to zero. Motivated by this, we use hypercontractive inequalities to study the properties of low-degree Fourier weights of Boolean function. We show better bounds for the Closeness and Testing problems of k-wise uniformity.

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

Zoom Participation. See announcement.

For More Information, Contact:

Keywords:

Thesis Oral