ECCC-Report TR22-102https://eccc.weizmann.ac.il/report/2022/102Comments and Revisions published for TR22-102en-usFri, 15 Jul 2022 10:11:28 +0300
Paper TR22-102
| Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness |
Xiuhan Wang,
Venkatesan Guruswami,
Xin Lyu
https://eccc.weizmann.ac.il/report/2022/102In 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 or list-decoding capacity, and constructing rigid matrices, reduce to the range avoidance problem of log-depth circuits, and by a further recent reduction [Ren, Santhanam, and Wang, ECCC 2022] to $NC^0_4$ circuits where each output depends on at most $4$ input bits.
On the algorithmic side, we show that range avoidance for $NC^0_2$ circuits can be solved in polynomial time. We identify a general condition relating to correlation with low-degree parities that implies that any almost pairwise independent set has some string that avoids the range of every circuit in the class. We apply this to $NC^0$ circuits, and to small width CNF/DNF and general De Morgan formulae (via a connection to approximate-degree), yielding non-trivial small hitting sets for range avoidance in these cases.Fri, 15 Jul 2022 10:11:28 +0300https://eccc.weizmann.ac.il/report/2022/102