https://wiki.simons.berkeley.edu/ 2026-08-08T20:11:28+00:00 https://wiki.simons.berkeley.edu/ https://wiki.simons.berkeley.edu/lib/exe/fetch.php?media=wiki:dokuwiki.svg text/html 2025-12-22T23:45:33+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=mc23:list-of-open-problems&rev=1766447133&do=diff List of open problems For instructions on how to submit your open problem, see Submission Instructions. * See also the [PDF version] of the list of open problems. NP-Hardness of Meta-Complexity of Average-Case Complexity Submitted by Hanlin Ren on 28/January/2023. Description. Many meta-complexity problems are known to be $\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\sf DNF$$\rm MCSP$$\mathsf{NP}$$f:\{0, 1\}^n \to \{0, 1\}$$s$$s$$f$$s$$F$$\Pr_{x\gets \{0, 1\}^n}[F(x) = f(x)] \le 0… text/html 2025-12-22T23:45:33+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=mc23:start&rev=1766447133&do=diff Meta-Complexity, Spring 2023 * List of open problems * Reading groups * AutoMetaLearning * Bounded Arithmetic * Crypto * Interest groups * Quantum Interest Group * Student seminar * Meta-Complexity Seminar * Informal evenings Regular schedule * Music nights: Tuesdays, 6:30pm * text/html 2025-12-22T23:45:33+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=mc23:submission-instructions&rev=1766447133&do=diff Template for the submission of open problems Write your open problem description and related work using the template file PROBLEM-Sample.tex. You can insert your references in the file your-references.bib. You can compile the PROBLEM-Sample.tex file locally (in your computer or on Overleaf).$p$$p = 2$