[Colloquium] Reminder: Tsang/MS Presentation/Nov 6, 2017
Margaret Jaffey via Colloquium
colloquium at mailman.cs.uchicago.edu
Fri Nov 3 09:34:15 CDT 2017
This is a reminder about Hing Yin (Joseph) Tsang's MS Presentation on
Monday.
------------------------------------------------------------------------------
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 advisors are Prof. Laszlo Babai and Prof. Andy Drucker
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
More information about the Colloquium
mailing list