BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1426
DTSTAMP:20240516T083228Z
SUMMARY:The connection between circuit complexity and first-order logic
DESCRIPTION:Speaker: Pranshu Gaba (TIFR)\n\nAbstract: \nDescriptive complex
ity is a branch of computational complexity where complexity classes are d
escribed using forms of logic\, giving machine-independent characterizatio
ns of the complexity classes. In this talk\, we look at an important resul
t in descriptive complexity:[BIS88\, Theorem 8.1] A class of structures is
in DLOGTIME-uniform AC0 if and only if the class is definable in first-or
der logic with numerical predicates.Here\, DLOGTIME is the class of langua
ges accepted by a deterministic random-access Turing machine in logarithmi
c time.A language is said to be in DLOGTIME-uniform AC0 if it can be recog
nized by a family of constant-depth\, polynomial-size circuits with AND an
d OR gates\, where the circuits can be constructed by a DLOGTIME machine.
The proof involves showing that if a language is in DLOGTIME\, then it is
definable in first-order logic with numerical predicates.Reference:[BIS88]
David A. Mix-Barrington\, Neil Immerman\, and Howard Straubing. 1990. On
uniformity within NC1. J. Comput. Syst. Sci. 41\, 3 (Dec. 1990)\, 274–30
6. https://doi.org/10.1016/0022-0000(90)90022-D\n
URL:https://www.tcs.tifr.res.in/web/events/1426
DTSTART;TZID=Asia/Kolkata:20240517T113000
DTEND;TZID=Asia/Kolkata:20240517T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR