BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1182
DTSTAMP:20230921T105045Z
SUMMARY:A peek into Meta-Complexity
DESCRIPTION:Speaker: Varun Ramanathan\n\nAbstract: \nMeta-complexity refers
to the study of complexity of problems that are themselves about computat
ional complexity. The canonical meta-complexity problem in the Boolean wor
ld is MCSP (Minimum Circuit Size Problem). A recent result by Ilango has s
hone some light on when one can get an efficient Search-to-Decision reduct
ion for MFSP\, a variant of MCSP for formulas instead of circuits. We stud
ied their result in hopes of importing it to similar problems in the algeb
raic world. On the way\, we simplified a lemma from their paper and also o
bserved a surprising behaviour of random Boolean formulas\; these will be
the contents of this project seminar.\n
URL:https://www.tcs.tifr.res.in/web/events/1182
DTSTART;TZID=Asia/Kolkata:20220119T110000
DTEND;TZID=Asia/Kolkata:20220119T120000
LOCATION:Via Zoom
END:VEVENT
END:VCALENDAR