Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with range avoidance problem:
TR22-120 | 24th August 2022
Jan Krajicek

On the existence of strong proof complexity generators

Revisions: 1 , Comments: 1

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:
\item There exist a p-time function $g$ extending each input by one bit such that its ... more >>>

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

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

ISSN 1433-8092 | Imprint