[Colloquium] Tsang/MS Presentation/Nov 3, 2017

[Margaret Jaffey via Colloquium]

This is an announcement of Hing Yin Tsang's MS Presentation.

------------------------------------------------------------------------------
Date:  Friday, November 3, 2017

Time:  3:30 PM

Place:  Ryerson 277

M.S. Candidate:  Hing Yin Tsang

M.S. Paper Title: Polynomial representation, Fourier transform and
complexity of Boolean functions

Abstract:
We study the Log-rank Conjecture for XOR functions and the Sensitivity
Conjecture by exploiting structure of the Fourier transform and
polynomial representations of Boolean functions.

For the Log-rank Conjecture for XOR functions, we show that the it is
true for functions with small spectral norm or low $\F_2$-degree. More
precisely, we prove the following two bounds.

1. $CC(f(x \xor y)) = O(\|\hat{f}\|_1 \cdot \log\|\hat{f}\|_0)$, and

2. $CC(f(x \xor y)) = O(2^{d/2}\log^{d-1}\|\hat{f}\|_0), where $d =
\deg_{\F_2} (f)$.



For the Sensitivity Conjecture, we obtain a pair of conjectures with
the property that (i). each of them is a consequence of the
Sensitivity Conjecture, (ii). neither one of them is known to imply
the Sensitivity Conjecture and (iii) both of them together imply the
Sensitivity Conjecture. We also obtain new a sufficient condition for
the Sensitivity Conjecture based on a graph that we called the
\emph{monomial graph} associated with the Boolean function.
Specifically, we show that in order to prove the Sensitivity
Conjecture, it suffices to show that for all Boolean functions $f$,
the number of monotone paths from $0^n$ to some level $\ell =
\Omega(n)$ in its monomial graph is at most $s(f)^O(\ell)$. On the
other hand, we show that for all Boolean functions $f$,

1. the number of monotone paths from $0^n$ to level $\ell$ in its
monomial graph is at most $2^{\ell^2/2}(s(f))^\ell$;

2. the number of degree-$\ell$ monomials in its $\R$-representation is
at most $(4e)^\ell \cdot s(f)^{\ell \cdot \min\{s(f), \ell\}}$.

Hing Yin's advisor is Prof. Laszlo Babai

Login to the Computer Science Department website for details:
 https://www.cs.uchicago.edu/phd/ms_announcements#hytsang

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=