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.
