Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness
| Autor: | Guruswami, Venkatesan, Lyu, Xin, Wang, Xiuhan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| DOI: | 10.4230/lipics.approx/random.2022.20 |
| Popis: | 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 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, FOCS 2022] to NC⁰₄ circuits where each output depends on at most 4 input bits. On the algorithmic side, we show that range avoidance for NC⁰₂ 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⁰ 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. LIPIcs, Vol. 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), pages 20:1-20:21 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|