Algorithms for Circuits and Circuits for Algorithms

Show full item record

Please use this identifier to cite or link to this item:

Title: Algorithms for Circuits and Circuits for Algorithms
Author: Williams, Ryan
Abstract: Connections have been recently developed between the existence of non-trivial circuitanalysis algorithms and proofs of circuit size lower bounds. Algorithms that can check whether a given circuit from some class satisfies a simple property (such as computing the all-zeroes function) can be used to prove limitations on that circuit class, provided the algorithms run slightly faster than exhaustive search. More precisely, a non-trivial SAT algorithm for a circuit class can be used to find functions computable in nondeterministic exponential time that cannot be computed by that circuit class. Informally, this connection can be interpreted as saying "good algorithms for circuits imply there are no good circuits for some algorithms." This talk will explore the ideas behind this theme and the potential for further progress.
Description: Presented on November 11, 2011 in Klaus 1116 Runtime: 53:10 minutes
Type: Lecture
Date: 2011-11-11
Contributor: Georgia Institute of Technology. Algorithms, Randomness and Complexity Center
Almaden Research Center (IBM Research)
Georgia Institute of Technology. School of Mathematics
Georgia Institute of Technology. School of Computer Science
Relation: ARC Theory Day
Publisher: Georgia Institute of Technology
Subject: Circuit-analysis algorithms

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View Description
williams.mp4 144.3Mb MPEG-4 video View/ Open Download Video
williams_streaming.html 926bytes HTML View/ Open Streaming Video

This item appears in the following Collection(s)

Show full item record