國立虎尾科技大學 |

Some Results in Low-Depth Circuit Complexity.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Some Results in Low-Depth Circuit Complexity./
Author:	Li, Yuan.
Description:	1 online resource (191 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 79-02(E), Section: B.
Contained By:	Dissertation Abstracts International79-02B(E).
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9780355234022

Some Results in Low-Depth Circuit Complexity.
Li, Yuan.

Some Results in Low-Depth Circuit Complexity. - 1 online resource (191 pages)

Source: Dissertation Abstracts International, Volume: 79-02(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

Circuit complexity is a branch of computational complexity theory in which we study complexity measures including size and depth, where the computation models are circuits instead of Turing machines. Little is known for general circuits, while there are nontrivial results in some restricted circuit models. This dissertation consists of three contributions related to low-depth circuit complexity.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355234022Subjects--Topical Terms:

573171
Computer science.
Index Terms--Genre/Form:

554714
Electronic books.

Some Results in Low-Depth Circuit Complexity.
LDR:05708ntm a2200445Ki 4500 001 910501
005 20180517123956.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355234022
035 $a (MiAaPQ)AAI10601673
035 $a (MiAaPQ)uchicago:13897
035 $a AAI10601673
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Li, Yuan. $3 1073991
245 1 0 $a Some Results in Low-Depth Circuit Complexity.
264 0 $c 2017
300 $a 1 online resource (191 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 79-02(E), Section: B.
500 $a Advisers: Andrew Drucker; Janos Simon.
502 $a Thesis (Ph.D.) $c The University of Chicago $d 2017.
504 $a Includes bibliographical references
520 $a Circuit complexity is a branch of computational complexity theory in which we study complexity measures including size and depth, where the computation models are circuits instead of Turing machines. Little is known for general circuits, while there are nontrivial results in some restricted circuit models. This dissertation consists of three contributions related to low-depth circuit complexity.
520 $a The first contribution answers the following question: what is the minimum depth required to compute good codes by linear-size circuits? Good codes have both constant code rate and constant relative distance, and size of the circuit is defined to be the number of wires instead of gates since the fan-in is unbounded. We prove the answer is theta(alpha(n)), where alpha( n) is the inverse Ackermann function. The lower bound applies to unrestricted circuits, and the proof is a graph-theoretic argument relying on a lemma by Raz and Shpilka (2003), and a connection between good codes and densely regular graphs by Gal et al. (2013). The upper bound is inspired by the recursive construction of superconcentrators; we prove a similar recursion exists. The upper bound tightens the previous result O(log*n) by Gal et al..
520 $a In the algebraic setting over large field, we show a close connection between superconcentrators and good codes. For example, we prove any superconcentrator with n inputs and n + theta(n) outputs 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 the potential application of the above "superconcentrator codes" in Network Coding.
520 $a The second contribution is about conservative circuits and routing networks. Our original motivation is to study the circuit complexity of the (cyclic) Shift operator, which takes n+log n input bits and outputs n bits. We propose the definition of Expansive Routing Family (ERF) networks based on some entropy property satisfied by the Shift operator, with the aim to extend lower bounds from conservative circuits to a more general model which allows arbitrary preprocessing and a final layer of postprocessing. However, it turns out there exist small-size ERF networks. For depth 2 and 3, we obtain tight bounds theta ( n(log n/ log log n)2) and theta(n log log n) respectively; for depth d ≥ 4, we prove lower bound O d (lambdad(n) · n).
520 $a 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 networks for given specific demands. Towards this challenge, we significantly generalize the Pippenger-Yao lower bound for shifts based on Shannon entropy, which can be applied to any multirequests; and for constant depth d, we construct size-O ( dn1+1/d ) routing network realizing all shifts, where the size is optimal up to a constant factor.
520 $a 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 G 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 Subgraphave(P) under the Erdos-Renyi random graphs. Let us define C col(P) and Cave( P) analogously to C(P).
520 $a For the average-case version, we give a characterization of Cave(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 Ccol(P) = O ( tw(P)/ log tw(P) ) , where tw(P) denotes the tree width of P. The lower bound is obtained in the average case, and is tight up to a logarithmic factor.
520 $a 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 (worstcase, uncolored) one. This suggests that new techniques may be required to solve the worstcase uncolored version.
520 $a The first two contributions are joint work with Andrew Drucker, and the third contribution is joint with Alexander Razborov and Benjamin Rossman.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Mathematics. $3 527692
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0405
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a The University of Chicago. $b Computer Science. $3 845504
773 0 $t Dissertation Abstracts International $g 79-02B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10601673 $z click for full text (PQDT)