000 02644nam a22005055i 4500
001 978-3-642-24508-4
003 DE-He213
005 20140220083303.0
007 cr nn 008mamaa
008 120104s2012 gw | s |||| 0|eng d
020 _a9783642245084
_9978-3-642-24508-4
024 7 _a10.1007/978-3-642-24508-4
_2doi
050 4 _aQ350-390
050 4 _aQA10.4
072 7 _aPBW
_2bicssc
072 7 _aMAT003000
_2bisacsh
082 0 4 _a519
_223
100 1 _aJukna, Stasys.
_eauthor.
245 1 0 _aBoolean Function Complexity
_h[electronic resource] :
_bAdvances and Frontiers /
_cby Stasys Jukna.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c2012.
300 _aXV, 617p. 70 illus.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aAlgorithms and Combinatorics,
_x0937-5511 ;
_v27
505 0 _aPart I Basics -- Part II Communication Complexity -- Part III Circuit Complexity -- Part IV Bounded Depth Circuits -- Part V Branching Programs -- Part VI Fragments of Proof Complexity -- A Epilog -- B Mathematical Background -- References -- Index.
520 _aBoolean circuit complexity is the combinatorics of computer science and involves many intriguing problems that are easy to state and explain, even for the layman. This book is a comprehensive  description of basic lower bound arguments, covering many of the gems of this “complexity Waterloo” that have been discovered over the past several decades, right up to results from the last year or two. Many open problems, marked as Research Problems, are mentioned along the way. The problems are mainly of combinatorial flavor but their solutions could have great consequences in circuit complexity and computer science. The book will be of interest to graduate students and researchers in the fields of computer science and discrete mathematics.
650 0 _aMathematics.
650 0 _aInformation theory.
650 0 _aComputer science.
650 0 _aCombinatorics.
650 1 4 _aMathematics.
650 2 4 _aInformation and Communication, Circuits.
650 2 4 _aTheory of Computation.
650 2 4 _aCombinatorics.
650 2 4 _aMathematics of Computing.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783642245077
830 0 _aAlgorithms and Combinatorics,
_x0937-5511 ;
_v27
856 4 0 _uhttp://dx.doi.org/10.1007/978-3-642-24508-4
912 _aZDB-2-SMA
999 _c102293
_d102293