Document Open Access Logo

Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness

Authors Venkatesan Guruswami, Xin Lyu, Xiuhan Wang

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2022.20.pdf
  • Filesize: 0.84 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Pseudorandomness
  • Explicit constructions
  • Low-depth circuits
  • Boolean function analysis
  • Hitting sets

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Venkatesan Guruswami, Xin Lyu, and Xiuhan Wang. Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.20

Author Details

Venkatesan Guruswami
  • University of California Berkeley, CA, USA
Xin Lyu
  • University of California Berkeley, CA, USA
Xiuhan Wang
  • Tsinghua University, Beijing, China

Funding

  • Guruswami, Venkatesan: Research supported in part by NSF CCF-2210823 and a Simons Investigator Award.

Acknowledgements

We thank anonymous reviewers for helpful comments and suggestions.

References

  1. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567-583, 1986. URL: https://doi.org/10.1016/0196-6774(86)90019-2.
  2. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple construction of almost k-wise independent random variables. Random Struct. Algorithms, 3(3):289-304, 1992. URL: https://doi.org/10.1002/rsa.3240030308.
  3. Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal. Rigid matrices from rectangular pcps or: Hard claims have complex proofs. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 858-869. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00084.
  4. Mark Bun and Justin Thaler. The large-error approximate degree of ac^0. Theory Comput., 17:1-46, 2021. URL: https://theoryofcomputing.org/articles/v017a007/.
  5. Ronald de Wolf. A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions. CoRR, 2008. URL: https://doi.org/10.48550/ARXIV.0802.1816.
  6. Peter Elias. List decoding for noisy channels, 1957. Google Scholar
  7. Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Trans. Inf. Theory, 54(1):135-150, 2008. Google Scholar
  8. Venkatesan Guruswami and Atri Rudra. Better binary list decodable codes via multilevel concatenation. IEEE Trans. Inf. Theory, 55(1):19-26, 2009. Google Scholar
  9. R. W. Hamming. Error detecting and error correcting codes. The Bell System Technical Journal, 29(2):147-160, 1950. URL: https://doi.org/10.1002/j.1538-7305.1950.tb00463.x.
  10. Johan Håstad. On the correlation of parity and small-depth circuits. SIAM J. Comput., 43(5):1699-1708, 2014. URL: https://doi.org/10.1137/120897432.
  11. Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos H. Papadimitriou. Total functions in the polynomial hierarchy. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 44:1-44:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.44.
  12. Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2^õ(n^{1/3}). J. Comput. Syst. Sci., 68(2):303-318, 2004. URL: https://doi.org/10.1016/j.jcss.2003.07.007.
  13. Oliver Korten. The hardest explicit construction. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 433-444. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00051.
  14. Xin Lyu. Improved pseudorandom generators for AC⁰ circuits. Electron. Colloquium Comput. Complex., TR22-021, 2022. URL: http://arxiv.org/abs/TR22-021.
  15. Elchanan Mossel, Amir Shpilka, and Luca Trevisan. On epsilon-biased generators in nc^0. Random Struct. Algorithms, 29(1):56-81, 2006. URL: https://doi.org/10.1002/rsa.20112.
  16. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838-856, 1993. URL: https://doi.org/10.1137/0222053.
  17. Mihai Patrascu. Succincter. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 305-313. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.83.
  18. Alexander A Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. URL: https://doi.org/10.1006/jcss.1997.1494.
  19. Alexander A. Razborov and Alexander A. Sherstov. The sign-rank of ac^0. SIAM J. Comput., 39(5):1833-1855, 2010. URL: https://doi.org/10.1137/080744037.
  20. Ben Reichardt. Reflections for quantum query algorithms. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 560-569. SIAM, 2011. URL: https://doi.org/10.1137/1.9781611973082.44.
  21. Hanlin Ren, Rahul Santhanam, and Zhikun Wang. On the range avoidance problem for circuits. Electron. Colloquium Comput. Complex., 2022. URL: https://eccc.weizmann.ac.il/report/2022/048.
  22. John E. Savage. The complexity of computing. Wiley New York, 1976. Google Scholar
  23. Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 238-251, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3055399.3055408.
  24. Avishay Tal. Formula lower bounds via the quantum method. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1256-1268. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055472.
  25. Luca Trevisan and Tongke Xue. A derandomized switching lemma and an improved derandomization of AC0. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 242-247. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/CCC.2013.32.
  26. Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In Jozef Gruska, editor, Mathematical Foundations of Computer Science 1977, 6th Symposium, Tatranska Lomnica, Czechoslovakia, September 5-9, 1977, Proceedings, volume 53 of Lecture Notes in Computer Science, pages 162-176. Springer, 1977. URL: https://doi.org/10.1007/3-540-08353-7_135.
  27. Emanuele Viola. The complexity of distributions. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 202-211. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.27.
  28. Emanuele Viola. Sampling lower bounds: Boolean average-case and permutations. SIAM J. Comput., 49(1):119-137, 2020. URL: https://doi.org/10.1137/18M1198405.
  29. Ryan Williams. Nonuniform acc circuit lower bounds. J. ACM, 61(1), January 2014. URL: https://doi.org/10.1145/2559903.
  30. John M Wozencraft. List decoding. Quarterly Progress Report, 48:90-95, 1958. Google Scholar
  31. Huacheng Yu. Nearly optimal static las vegas succinct dictionary. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1389-1401. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384274.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact