東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Some Results in Low-Depth Circuit Co...

Li, Yuan.

FindBook

Google Book

Amazon

博客來

Some Results in Low-Depth Circuit Complexity.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Some Results in Low-Depth Circuit Complexity./
作者:	Li, Yuan.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2017,
面頁冊數:	191 p.
附註:	Source: Dissertation Abstracts International, Volume: 79-02(E), Section: B.
Contained By:	Dissertation Abstracts International79-02B(E).
標題:	Computer science. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10601673
ISBN:	9780355234022

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

Some Results in Low-Depth Circuit Complexity. - Ann Arbor : ProQuest Dissertations & Theses, 2017 - 191 p.

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

Thesis (Ph.D.)--The University of Chicago, 2017.

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.

ISBN: 9780355234022Subjects--Topical Terms:

523869
Computer science.

Some Results in Low-Depth Circuit Complexity.
LDR:05377nmm a2200397 4500 001 2156140
005 20180517123956.5
008 190424s2017 ||||||||||||||||| ||eng d
020 $a 9780355234022
035 $a (MiAaPQ)AAI10601673
035 $a (MiAaPQ)uchicago:13897
035 $a AAI10601673
040 $a MiAaPQ $c MiAaPQ
100 1 $a Li, Yuan. $3 1682511
245 1 0 $a Some Results in Low-Depth Circuit Complexity.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2017
300 $a 191 p.
500 $a Source: Dissertation Abstracts International, Volume: 79-02(E), Section: B.
500 $a Advisers: Andrew Drucker; Janos Simon.
502 $a Thesis (Ph.D.)--The University of Chicago, 2017.
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.
590 $a School code: 0330.
650 4 $a Computer science. $3 523869
650 4 $a Mathematics. $3 515831
690 $a 0984
690 $a 0405
710 2 $a The University of Chicago. $b Computer Science. $3 1674744
773 0 $t Dissertation Abstracts International $g 79-02B(E).
790 $a 0330
791 $a Ph.D.
792 $a 2017
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10601673