[Colloquium] Li/Dissertation Defense/Jun 20, 2017

[Margaret Jaffey via Colloquium]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Yuan Li

Date:  Tuesday, June 20, 2017

Time:  2:00 PM

Place:  Ryerson 277

Title: Some Results in Low-Depth Circuit Complexity

Abstract:
Circuit complexity is a branch of computational complexity theory in
which we study complexity measures including size and depth, where the
computation model is circuit instead of Turing machine. This
dissertation consists of three contributions related to low-depth
circuit complexity.

The first contribution answers the following question: what is the
minimum depth required to compute good codes in linear size (= number
of wires), where good codes have constant rate and constant relative
distance? We prove the answer is Θ(α(n)), where α(n) is
the inverse Ackermann function. The lower bound applies to
unrestricted circuits, and the proof is a graph-theoretic argument
relying on known techniques. The upper bound is inspired by the
construction of superconcentrators, which tightens the previous result
O(log^*n) by Gál et al. In the algebraic setting over large field, we
show a close connection between superconcentrators and good codes,
that is, any superconcentrator with n inputs and cn outputs, c>1,
computes a good code, by replacing each vertex with an addition gate
and assigning the coefficient for each edge uniformly at random. We
also show its potential application in Network Coding.

The second contribution is about conservative circuits and routing
networks. We propose the definition of the Expansive Routing Family
(ERF) networks based on some entropy property satisfied by the cyclic
Shift operator {0,1}^{n+logn}->{0,1}^n, aiming to extend lower bounds
from conservative circuits to a more general model which allows
arbitrary preprocessing and a final layer of postprocessing. It turns
out there exist small-size ERF networks. For depth 2 and 3, we obtain
tight bounds Θ(n(logn/loglogn)^2) and Θ(nloglogn)
respectively; for depth d>3, we prove lower bound
Ω_d(nλ_d(n)). We propose the research challenge to develop a
powerful and broadly-applicable set of techniques for both upper
bounding and lower bounding the wire complexity of routing network for
given specific demands. Towards this challenge, we significantly
generalize the Pippenger-Yao lower bound for shifts based on the
concept of entropy; for fixed d, we construct depth-d
size-O(dn^{1+1/d}) routing networks realizing all shifts, where the
size is optimal up to a constant factor.

The third contribution is about the AC0 complexity of subgraph
isomorphism. Let Subgraph(P) denote the problem of deciding whether a
given n-vertex graph contains a subgraph isomorphic to P. Let C(P)
denotes smallest possible exponent C(P) for which Subgraph(P)
possesses bounded-depth circuits of size n^{C(P)+o(1)}. Motivated by
the previous research in the area, we also consider its colorful
version, and the average-case version Subgraph_ave(P) under the
Erdos-Renyi random graphs. Let us define C_col(P) and C_ave(P)
analogously to C(P). For the average-case version, we give a
characterization of C_ave(P) in purely combinatorial terms up to a
multiplicative factor of 2. The lower bound closely follows Rossman's
techniques. For the worst-case colored version, we prove C_col(P)
coincides with treewidth up to a logarithmic factor. We also prove
some structural results suggesting that the colorful version of the
subgraph isomorphism problem is much better structured and
well-behaved than the standard (worst-case, uncolored) one.

The first two contributions are joint work with Andrew Drucker, and
the third contribution is joint with Alexander Razborov and Benjamin
Rossman.

Yuan's advisor is Prof. Janos Simon

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=