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