[Colloquium] Reminder: Li/MS Presentation/Feb 17, 2014

[Margaret Jaffey]

This is a reminder about Yuan's MS Presentation this afternoon.

------------------------------------------------------------------------------
Date:  Monday, February 17, 2014

Time:  2:30 PM

Place:  Ryerson 276

M.S. Candidate:  Yuan Li

M.S. Paper Title: Some results in circuit complexity

Abstract:
The thesis consists of three parts. The first part investigates the
AC^0 complexity of Subgraph Isomorphism Problem, that is, detecting
whether an $n$-vertex input graph contains a $P$-subgraph for some
fixed $P$. For the average-case complexity, i.e., the input is a
distribution on random graphs at the threshold and small error is
allowed, we are able to explicitly characterize the minimal AC^0 size
up to quadratic. For the worst-case complexity, if $P$ is a colored
graph (each vertex has a different color, and the input graph is also
colored, of course), we prove a $n^{\Omega(\tw(P) / \log \tw(P))}$
lower bound, which nearly matches the upper bound $n^{\tw(P) + O(1)}$
due to Alon, Yuster and Zwick \cite{AYZ95}.

The second part proves tight lower bounds of the immunity of MOD
function and its negation. For a Boolean function $f :\{0,1\}^n \to
\{0,1\}$, its immunity over field $F_p$ is defined as the minimal
degree of a nontrivial polynomial $g(x) \in F_p[x_1, \ldots, x_n]$
such that $g(x) = 0$ for all $x$ with $f(x) = 0$. Improving the
previous results, we prove: when $p, q$ are coprime, the immunity of
$\neg \mathrm{MOD}_q$ is exactly $\lfloor (n+q-1)/q \rfloor$; and the
immunity of $\mathrm{MOD}_q$ is lower bounded by $\lceil n/2 \rceil$.
We observe the following connection between immunity and circuit lower
bound: if Boolean function $f$ has immunity over $F_p$ at least $n/2 -
o(\sqrt{n})$ and $|1_f| = \Omega(2^n)$, then $f$ requires exponential
size AC^0[p] (=AC^0 with $\mathrm{MOD}_p$ gates) to compute.

The third part is a complete characterization of $k$ robust immune
symmetric Boolean functions for any $k$, over any field, where a
Boolean function $f: \{0,1\}^n \to \{0,1\}$ is $k$ robust immune if
the immunity of $f$ and $1-f$ is always lower bounded by $k$ no matter
how you change the values of $f(x)$ with $k \le |x| \le n - k$.

The first part is joint with Alexander Razborov and Benjamin Rossman,
and the second part is joint with Chris Beck.

Yuan's advisor is Prof. Alexander Razborov

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

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=