2026-07-23T13:53:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17142 2024-03-06T10:59:04Z ddc:004 open_access

Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness Guruswami, Venkatesan Lyu, Xin Wang, Xiuhan Pseudorandomness Explicit constructions Low-depth circuits Boolean function analysis Hitting sets 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Venkatesan Guruswami and Xin Lyu and Xiuhan Wang 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.20 urn:nbn:de:0030-drops-171428 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.20 eng https://creativecommons.org/licenses/by/4.0/legalcode