Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with algorithmic method:
TR22-048 | 4th April 2022
Hanlin Ren, Rahul Santhanam, Zhikun Wang

On the Range Avoidance Problem for Circuits

We consider the range avoidance problem (called Avoid): given the description of a circuit $C:\{0, 1\}^n \to \{0, 1\}^\ell$ (where $\ell > n$), find a string $y\in\{0, 1\}^\ell$ that is not in the range of $C$. This problem is complete for the class APEPP that corresponds to explicit constructions of ... more >>>

TR22-183 | 19th December 2022
Lijie Chen

New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method

In this paper, we obtain several new results on lower bounds and derandomization for ACC^0 circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity):

1. We prove that any polynomial-time Merlin-Arthur proof system with an ACC^0 verifier (denoted by ... more >>>

ISSN 1433-8092 | Imprint