東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Computational complexity: Counting, ...

Kulkarni, Raghav.

Linked to FindBook

Google Book

Amazon

博客來

Computational complexity: Counting, evasiveness, and isolation.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Computational complexity: Counting, evasiveness, and isolation./
Author:	Kulkarni, Raghav.
Description:	110 p.
Notes:	Source: Dissertation Abstracts International, Volume: 71-10, Section: B, page: 6228.
Contained By:	Dissertation Abstracts International71-10B.
Subject:	Applied Mathematics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3419659
ISBN:	9781124197722

Computational complexity: Counting, evasiveness, and isolation.
Kulkarni, Raghav.

Computational complexity: Counting, evasiveness, and isolation. - 110 p.

Source: Dissertation Abstracts International, Volume: 71-10, Section: B, page: 6228.

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

We present results in three areas of Computational Complexity Theory: (1) Complexity of Counting, (2) Decision Tree Complexity, and (3) Space Complexity.

ISBN: 9781124197722Subjects--Topical Terms:

1669109
Applied Mathematics.

Computational complexity: Counting, evasiveness, and isolation.
LDR:02536nam 2200373 4500 001 1395995
005 20110527105442.5
008 130515s2010 ||||||||||||||||| ||eng d
020 $a 9781124197722
035 $a (UMI)AAI3419659
035 $a AAI3419659
040 $a UMI $c UMI
100 1 $a Kulkarni, Raghav. $3 1674743
245 1 0 $a Computational complexity: Counting, evasiveness, and isolation.
300 $a 110 p.
500 $a Source: Dissertation Abstracts International, Volume: 71-10, Section: B, page: 6228.
500 $a Advisers: Janos Simon; Alexander Razborov.
502 $a Thesis (Ph.D.)--The University of Chicago, 2010.
520 $a We present results in three areas of Computational Complexity Theory: (1) Complexity of Counting, (2) Decision Tree Complexity, and (3) Space Complexity.
520 $a A recurrent theme is to exploit the connections of computational models to areas of mathematics including Algebraic Topology, Analytic Number Theory, and Group Theory.
520 $a In the first part, we study the complexity of computing the Determinant and the Permanent of a matrix modulo a constant power of 2. We also study the complexity of counting and modular counting of Spanning Trees and Perfect Matchings in general as well as in planar graphs. We use tools from Algebraic Topology to get a surprising upper bound on the complexity of counting spanning trees in planar graphs modulo a constant power of 2.
520 $a In the second part, we study the decision tree complexity of monotone graph properties. Building on a topological approach of Kahn, Saks, and Sturtevant, we solve new special cases of the Evasiveness Conjecture: a notorious problem that has been open for nearly four decades. We make connections to Analytic Number Theory by constructing new group actions suitable for the topological approach.
520 $a In the third part, we study questions related to Space Complexity of computing a perfect matching in planar graphs and link the study of similar questions in planar graphs to relations between complexity classes like NL and &oplus;L.
590 $a School code: 0330.
650 4 $a Applied Mathematics. $3 1669109
650 4 $a Computer Science. $3 626642
690 $a 0364
690 $a 0984
710 2 $a The University of Chicago. $b Computer Science. $3 1674744
773 0 $t Dissertation Abstracts International $g 71-10B.
790 1 0 $a Simon, Janos, $e advisor
790 1 0 $a Razborov, Alexander, $e advisor
790 1 0 $a Simon, Janos $e committee member
790 1 0 $a Razborov, Alexander $e committee member
790 1 0 $a Babai, Laszlo $e committee member
790 $a 0330
791 $a Ph.D.
792 $a 2010
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3419659