Description
Karl Wimmer
Low influence Boolean functions over slices of the Boolean hypercube depend on few coordinates
One of the classic results in analysis of Boolean functions is a result of Friedgut that states that Boolean functions over the hypercube of low influence are essentially determined by few coordinates, called juntas. While this result has also been extended to product distributions in various settings, very little is known in the case of nonproduct distributions.
We generalize Friedgut's junta theorem to slices of the Boolean hypercube; a slice of the Boolean hypercube is the set of strings in the Boolean hypercube with fixed Hamming weight. As in Friedgut's original proof, we use Fourier analysis and hypercontractivity. To set the stage for the use of Fourier analysis in this setting, we apply techniques from the representation theory of the symmetric group.
This talk assumes no background in representation theory.
Prahladh Harsha
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
In this result, we proved improved inapproximability results for hypergraph coloring. In particular, we prove quasi-NP-hardness of the following problems on n-vertex hypergraphs:
* Coloring a 2-colorable 8-uniform hypergraph with 2^{2^{\sqrt{log log n}} colors.
* Coloring a 4-colorable 4-uniform hypergraph with 2^{2^{\sqrt{log log n}} colors
* Coloring a 3-colorable 3-uniform hypergraph with (log n)^{1/log loglog n} colors
In each of these cases, the hardness results obtained are (at least) exponentially stronger than what was previously known. In fact, prior to this result, polylog n colors was the strongest quantitative bound on the number of colors ruled out.
These results are obtained using the low-degree polynomial code (aka, the “short code” of Barak et. al. [FOCS 2012]) and the techniques pro- posed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.
In this talk, I'll illustrate the main ideas to incorporate the low-degree long code towards inapproximability especially in the context of coloring results.
All scheduled dates:
Upcoming
No Upcoming activities yet