Filename Size Access Description License


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.


Additional Details


Download Full History