Tata Institute of Fundamental Research
A peek into Meta-Complexity
Project Presentation
Speaker:
Varun Ramanathan
Organiser:
Ramprasad Saptharishi
Date:
Wednesday, 19 Jan 2022, 11:00 to 12:00
Venue:
Via Zoom
(Scan to add to calendar)
Abstract:
Meta-complexity refers to the study of complexity of problems that are themselves about computational complexity. The canonical meta-complexity problem in the Boolean world is MCSP (Minimum Circuit Size Problem). A recent result by Ilango has shone some light on when one can get an efficient Search-to-Decision reduction for MFSP, a variant of MCSP for formulas instead of circuits. We studied their result in hopes of importing it to similar problems in the algebraic world. On the way, we simplified a lemma from their paper and also observed a surprising behaviour of random Boolean formulas; these will be the contents of this project seminar.
| Speaker: | Varun Ramanathan |
| Organiser: | Ramprasad Saptharishi |
| Date: | Wednesday, 19 Jan 2022, 11:00 to 12:00 |
| Venue: | Via Zoom |
(Scan to add to calendar)
Abstract:
Meta-complexity refers to the study of complexity of problems that are themselves about computational complexity. The canonical meta-complexity problem in the Boolean world is MCSP (Minimum Circuit Size Problem). A recent result by Ilango has shone some light on when one can get an efficient Search-to-Decision reduction for MFSP, a variant of MCSP for formulas instead of circuits. We studied their result in hopes of importing it to similar problems in the algebraic world. On the way, we simplified a lemma from their paper and also observed a surprising behaviour of random Boolean formulas; these will be the contents of this project seminar.