BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/409
DTSTAMP:20230914T125923Z
SUMMARY:Algebraic and Logical Approaches to Circuit Complexity
DESCRIPTION:Speaker: Dr. Howard Straubing (Boston College\nComputer Science
  Department\n21 Campanella Way\, Room 571\nChestnut Hill\, MA 02467\nUnite
 d States of America)\n\nAbstract: \nOne of the outstanding open questions 
 in computational complexity concerns the power of circuits that include mo
 dular counting gates along with the usual AND and OR gates. More precisely
 \, the class ACC consists of languages recognized by constant-­‐depth p
 olynomial-­‐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 m
 oduli\, a result proved in the mid 1980’s.\n\nThere are some very striki
 ng connections between this question and problems and techniques originati
 ng in both finite model theory and the algebraic theory of finite automata
 . This talk is an overview of these connections along with the efforts\, s
 ome by now quite old\, some much more recent\, to exploit them in addressi
 ng the status ofACC.\n
URL:https://www.tcs.tifr.res.in/web/events/409
DTSTART;TZID=Asia/Kolkata:20131001T160000
DTEND;TZID=Asia/Kolkata:20131001T170000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR