It is a long-standing open problem whether the Minimum Circuit Size Problem ($\mathrm{MCSP}$) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.

In this work, we prove NP-hardness of approximating meta-complexity with ... more >>>

A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. Avoid) and the remote point problem (abbrev. RPP). The upper and lower bounds for these meta problems provide a unified ... more >>>

We study connections between two fundamental questions from computer science theory. (1) Is witness encryption in the sense of Garg et al. (2013) possible for NP? That is, given an instance $x$ of an NP-complete language $L$, can one encrypt a secret message with security contingent on the ability to ... more >>>