Tata Institute of Fundamental Research
Algebraic and Logical Approaches to Circuit Complexity
Seminar
Speaker:
Dr. Howard Straubing (Boston College
Computer Science Department
21 Campanella Way, Room 571
Chestnut Hill, MA 02467
United States of America)
Organiser:
Arkadev Chattopadhyay
Date:
Tuesday, 1 Oct 2013, 16:00 to 17:00
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
One of the outstanding open questions in computational complexity concerns the power of circuits that include modular counting gates along with the usual AND and OR gates. More precisely, the class ACC consists of languages recognized by constant-‐depth polynomial-‐size families of circuits with unbounded fan-‐in AND, OR and MOD-q gates for a fixed modulus q; the question is whether ACC is strictly contained in NC1. At present this is known only for prime power moduli, a result proved in the mid 1980’s.
There are some very striking connections between this question and problems and techniques originating in both finite model theory and the algebraic theory of finite automata. This talk is an overview of these connections along with the efforts, some by now quite old, some much more recent, to exploit them in addressing the status ofACC.
| Speaker: | Dr. Howard Straubing (Boston College Computer Science Department 21 Campanella Way, Room 571 Chestnut Hill, MA 02467 United States of America) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Tuesday, 1 Oct 2013, 16:00 to 17:00 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
One of the outstanding open questions in computational complexity concerns the power of circuits that include modular counting gates along with the usual AND and OR gates. More precisely, the class ACC consists of languages recognized by constant-‐depth polynomial-‐size families of circuits with unbounded fan-‐in AND, OR and MOD-q gates for a fixed modulus q; the question is whether ACC is strictly contained in NC1. At present this is known only for prime power moduli, a result proved in the mid 1980’s.
There are some very striking connections between this question and problems and techniques originating in both finite model theory and the algebraic theory of finite automata. This talk is an overview of these connections along with the efforts, some by now quite old, some much more recent, to exploit them in addressing the status ofACC.
There are some very striking connections between this question and problems and techniques originating in both finite model theory and the algebraic theory of finite automata. This talk is an overview of these connections along with the efforts, some by now quite old, some much more recent, to exploit them in addressing the status ofACC.