[Colloquium] Reminder: Tsang/MS Presentation/Nov 6, 2017

[Margaret Jaffey via Colloquium]

Please note the revised date for Hing Yin (Joseph) Tsang's MS
Presentation. It will now be held on Monday, November 6th.

------------------------------------------------------------------------------
Date:  Monday, November 6, 2017

Time:  3:30 PM

Place:  Eckhart 207

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 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-2}\|\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 a new 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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=