Yu Zhao

Generalizations and Applications of Hypercontractivity and Small-Set Expansion Degree Type: Ph.D. in Computer Science
Advisor(s): Ryan O'Donnell
Graduated: August 2021

Abstract:

Hypercontractive inequalities and small-set expansion are two fundamental topics closely related to each other and play important roles in many fields, including hardness of approximation, probability theory, social choice theory, information theory, and cryptography. 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 [KMS18]. A similar property has also been shown on Johnson graphs [KMMS18]. These results can be seen as an improved version of small-set expansion on pseudorandom sets. We prove the pseudorandom-set expansion result on general product probability spaces, with a very clean and short proof. A key step in the proof involves a new hypercontractive-style inequality.
• 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. In addition, we calculate the optimal communication for the reverse binary erasure channel case by studying properties of extreme points in its hypercontractivity region. 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 kind of "one-block decoupling" with better parameters than the classical results. We use decoupling and hypercontractivity to show tight tail bounds of low-degree Boolean functions and tight versions of several theorems from [DFKO07].
• A probability distribution over {-1, 1}ⁿ is k-wise uniform if its marginal distribution on every subset of k coordinates is the uniform distribution. These 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. In particular, 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)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Hypercontractivity, Expander Graphs, Fourier Analysis, Boolean Functions, Hardness of Approximation, Communication Complexity, Information Theory, Decoupling, Query Complexity, Property Testing, Distribution Testing