Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Xiuhan Wang:

TR22-102 | 15th July 2022
Venkatesan Guruswami, Xin Lyu, Xiuhan Wang

Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness

In the range avoidance problem, the input is a multi-output Boolean circuit with more outputs than inputs, and the goal is to find a string outside its range (which is guaranteed to exist). We show that well-known explicit construction questions such as finding binary linear codes achieving the Gilbert-Varshamov bound ... more >>>

ISSN 1433-8092 | Imprint