All reports by Author Yizhi Huang:

__
TR23-072
| 18th May 2023
__

Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren#### Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms

__
TR23-046
| 13th April 2023
__

Yizhi Huang, Rahul Ilango, Hanlin Ren#### NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren

The *range avoidance problem*, denoted as $\mathcal{C}$-$\rm Avoid$, asks to find a non-output of a given $\mathcal{C}$-circuit $C:\{0,1\}^n\to\{0,1\}^\ell$ with stretch $\ell>n$. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit ... more >>>

Yizhi Huang, Rahul Ilango, Hanlin Ren

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 >>>