Logo - springer
Slogan - springer

Mathematics - Applications | Boolean Function Complexity - Advances and Frontiers

Boolean Function Complexity

Advances and Frontiers

Series: Algorithms and Combinatorics, Vol. 27

Jukna, Stasys

2012, XVI, 620 p.

Available Formats:
eBook
Information

Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.

You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.

After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.

 
$59.99

(net) price for USA

ISBN 978-3-642-24508-4

digitally watermarked, no DRM

Included Format: PDF

download immediately after purchase


learn more about Springer eBooks

add to marked items

Hardcover
Information

Hardcover version

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.

 
$84.95

(net) price for USA

ISBN 978-3-642-24507-7

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days


add to marked items

Softcover
Information

Softcover (also known as softback) version.

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.

 
$84.95

(net) price for USA

ISBN 978-3-642-43144-9

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days


add to marked items

  • This is the first book covering the happening in circuit complexity during the last 20 years
  • Includes non-standard topics, like graph complexity or circuits with arbitrary gates
  • Includes about 40 open problems as potential research topics for students ​

Boolean 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.

Content Level » Graduate

Keywords » Boolean functions - circuit complexity - communication complexity - lower bounds

Related subjects » Applications - Theoretical Computer Science

Table of contents / Sample pages 

Part 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.

Popular Content within this publication 

 

Articles

Read this Book on Springerlink

Services for this book

New Book Alert

Get alerted on new Springer publications in the subject area of Information and Communication, Circuits.