The Complexity of Boolean Functions

Presents a large number of research results on the complexity of Boolean functions in non-uniform computation models. It has a direct relevance to practical problems in the computer aided design of digital circuits.

**Tag(s):**
Theory of Computation

**Publication date**: 01 Jan 1991

**ISBN-10**:
0471915556

**ISBN-13**:
n/a

**Paperback**:
470 pages

**Views**: 15,122

The Complexity of Boolean Functions

Presents a large number of research results on the complexity of Boolean functions in non-uniform computation models. It has a direct relevance to practical problems in the computer aided design of digital circuits.

Book Synopsis:

Research on the complexity of Boolean functions in non-uniform computation models is now part of one of the most interesting and important areas in theoretical computer science. It has a direct relevance to practical problems in the computer aided design of digital circuits.

In this book Professor Dr. Wegener presents a large number of recent research results for the first time. Initially he deals with the well known computation models (circuits and formulae), and he goes on to special types of circuits, parallel computers, and branching programs. Basic results are included as well as the most recent research results.

Intended Audience:

The Complexity of Boolean Functions assumes a basic knowledge of computer science and mathematics. It deals with both efficient algorithms and lower bounds. At the end of each chapter there are exercises with varying levels of difficulty to help students using the book.

Research on the complexity of Boolean functions in non-uniform computation models is now part of one of the most interesting and important areas in theoretical computer science. It has a direct relevance to practical problems in the computer aided design of digital circuits.

In this book Professor Dr. Wegener presents a large number of recent research results for the first time. Initially he deals with the well known computation models (circuits and formulae), and he goes on to special types of circuits, parallel computers, and branching programs. Basic results are included as well as the most recent research results.

Intended Audience:

The Complexity of Boolean Functions assumes a basic knowledge of computer science and mathematics. It deals with both efficient algorithms and lower bounds. At the end of each chapter there are exercises with varying levels of difficulty to help students using the book.

Tweet

About The Author(s)

No information is available for this author.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors