Computation Theory
and Neural Systems

CNS 188a
Winter 2006

Course Outline

A key to our success in engineering is the development of mathematical abstractions that enable efficient and robust design processes. While our design methodologies keep improving, our ability to analyze and understand the world around us is still a major challenge. Specifically, a key challenge in Biology is the lack of mathematical abstractions for representing systems' properties and behavior. Two intriguing biological systems that will serve as motivation for this course are gene regulation circuits (implementing the control mechanism of a cell) and neural circuits (implementing the brain).

The course will start by studying an abstraction developed over the past 300 years for reasoning about logic and circuits, namely, Boolean algebra. We will then study the capabilities and limitations of a number of computational models and methods that are inspired by or related to biological systems. Specific topics include:

  • Boolean algebra as an axiomatic system.
  • Boolean functions and their representations using Boolean formulas and spectral methods.
  • Implementing Boolean functions with circuits of AON (AND, OR, NOT) gates and LT (Linear Threshold) gates.
  • Analyzing the complexity (size and depth) of circuits.
  • Relations (as opposed to functions) and their implementation in circuits.
  • Feedback and convergence in LT circuits