Jan Krajicek

The working conjecture from K'04 that there is a proof complexity generator hard for all

proof systems can be equivalently formulated (for p-time generators) without a reference to proof complexity notions

as follows:

\begin{itemize}

\item There exist a p-time function $g$ extending each input by one bit such that its ...
more >>>

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