Document Open Access Logo

Hardness Against Linear Branching Programs and More

Authors Eshan Chattopadhyay , Jyun-Jie Liao

PDF
Thumbnail PDF

File

LIPIcs.CCC.2023.9.pdf
  • Filesize: 0.91 MB
  • 27 pages

Document Identifiers

Author Details

Eshan Chattopadhyay
  • Cornell University, Ithaca, NY, USA
Jyun-Jie Liao
  • Cornell University, Ithaca, NY, USA

Funding

Supported by NSF CAREER award 2045576.

Acknowledgements

We thank Jason Gaitonde for collaboration during initial stages of this project. We thank anonymous reviewers for helpful comments.

Cite As Get BibTex

Eshan Chattopadhyay and Jyun-Jie Liao. Hardness Against Linear Branching Programs and More. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 9:1-9:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CCC.2023.9

Abstract

In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is a branching program where each node is allowed to make 𝔽₂-linear queries, and is read-once in the sense that the queries on each path is linearly independent. As their main result, they constructed an explicit function with average-case complexity 2^{n/3-o(n)} against a slightly restricted model, which they call strongly read-once linear branching programs. The main tool in their lower bound result is a new type of extractor, called directional affine extractors, that they introduced.
Our main result is an explicit function with 2^{n-o(n)} average-case complexity against the strongly read-once linear branching program model, which is almost optimal. This result is based on a new connection from this problem to sumset extractors, which is a randomness extractor model introduced by Chattopadhyay and Li (STOC '16) as a generalization of many other well-studied models including two-source extractors, affine extractors and small-space extractors. With this new connection, our lower bound naturally follows from a recent construction of sumset extractors by Chattopadhyay and Liao (STOC '22). In addition, we show that directional affine extractors imply sumset extractors in a restricted setting. We observe that such restricted sumset sources are enough to derive lower bounds, and obtain an arguably more modular proof of the lower bound by Gryaznov, Pudlák and Talebanfard.
We also initiate a study of pseudorandomness against linear branching programs. Our main result here is a hitting set generator construction against regular linear branching programs with constant width. We derive this result based on a connection to Kakeya sets over finite fields.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Expander graphs and randomness extractors
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • linear branching programs
  • circuit lower bound
  • sumset extractors
  • hitting sets

Metrics

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

Related Versions

References

  1. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289-304, 1992. Google Scholar
  2. Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson. Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors. J. ACM, 57(4):20:1-20:52, 2010. URL: https://doi.org/10.1145/1734213.1734214.
  3. Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff. Pseudorandomness for width-2 branching programs. Theory of Computing, 9(1):283-293, 2013. Google Scholar
  4. Andrej Bogdanov, William M Hoza, Gautam Prakriya, and Edward Pyne. Hitting sets for regular branching programs. In 37th Computational Complexity Conference (CCC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. Google Scholar
  5. Andrej Bogdanov, Periklis A. Papakonstantinou, and Andrew Wan. Pseudorandomness for read-once formulas. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pages 240-246, 2011. URL: https://doi.org/10.1109/FOCS.2011.57.
  6. Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. SIAM Journal on Computing, 43(3):973-986, 2014. Google Scholar
  7. Eshan Chattopadhyay, Jesse Goodman, and Jyun-Jie Liao. Affine extractors for almost logarithmic entropy. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 622-633, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00067.
  8. Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman. The space complexity of sampling. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. Google Scholar
  9. Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal. Improved pseudorandomness for unordered branching programs through local monotonicity. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 363-375, 2018. Google Scholar
  10. Eshan Chattopadhyay and Xin Li. Extractors for sumset sources. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 299-311, 2016. URL: https://doi.org/10.1145/2897518.2897643.
  11. Eshan Chattopadhyay and Xin Li. Non-malleable codes and extractors for small-depth circuits, and affine functions. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1171-1184, 2017. Google Scholar
  12. Eshan Chattopadhyay and Xin Li. Non-malleable codes, extractors and secret sharing for interleaved tampering and composition of tampering. In Theory of Cryptography - 18th International Conference, TCC 2020, volume 12552 of Lecture Notes in Computer Science, pages 584-613, 2020. URL: https://doi.org/10.1007/978-3-030-64381-2_21.
  13. Eshan Chattopadhyay and Jyun-Jie Liao. Extractors for sum of two sources. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1584-1597, 2022. URL: https://doi.org/10.1145/3519935.3519963.
  14. Eshan Chattopadhyay and David Zuckerman. New extractors for interleaved sources. In 31st Conference on Computational Complexity, CCC 2016, volume 50 of LIPIcs, pages 7:1-7:28, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.7.
  15. Kuan Cheng and William M Hoza. Hitting sets give two-sided derandomization of small space. In 35th Computational Complexity Conference (CCC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  16. Mahdi Cheraghchi and Venkatesan Guruswami. Non-malleable coding against bit-wise and split-state tampering. In Theory of Cryptography Conference, pages 440-464. Springer, 2014. Google Scholar
  17. Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230-261, 1988. URL: https://doi.org/10.1137/0217015.
  18. Gil Cohen. Local correlation breakers and applications to three-source extractors and mergers. SIAM J. Comput., 45(4):1297-1338, 2016. URL: https://doi.org/10.1137/15M1029837.
  19. Gil Cohen and Igor Shinkar. The complexity of DNF of parities. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016, pages 47-58, 2016. URL: https://doi.org/10.1145/2840728.2840734.
  20. Evgeny Demenkov and Alexander S. Kulikov. An elementary proof of a 3n - o(n) lower bound on the circuit complexity of affine dispersers. In Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, volume 6907 of Lecture Notes in Computer Science, pages 256-265, 2011. URL: https://doi.org/10.1007/978-3-642-22993-0_25.
  21. Yevgeniy Dodis, Xin Li, Trevor D. Wooley, and David Zuckerman. Privacy amplification and non-malleable extractors via character sums. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pages 668-677, 2011. URL: https://doi.org/10.1109/FOCS.2011.67.
  22. Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam D. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput., 38(1):97-139, 2008. URL: https://doi.org/10.1137/060651380.
  23. Yevgeniy Dodis and Daniel Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pages 601-610, 2009. URL: https://doi.org/10.1145/1536414.1536496.
  24. Jordan S Ellenberg, Richard Oberlin, and Terence Tao. The kakeya set and maximal conjectures for algebraic varieties over finite fields. Mathematika, 56(1):1-25, 2010. Google Scholar
  25. Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov. A better-than-3n lower bound for the circuit complexity of an explicit function. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 89-98, 2016. URL: https://doi.org/10.1109/FOCS.2016.19.
  26. Michael A. Forbes and Venkatesan Guruswami. Dimension expanders via rank condensers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, volume 40 of LIPIcs, pages 800-814, 2015. Google Scholar
  27. Michael A. Forbes and Zander Kelley. Pseudorandom generators for read-once branching programs, in any order. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 946-955, 2018. URL: https://doi.org/10.1109/FOCS.2018.00093.
  28. Uma Girish, Avishay Tal, and Kewen Wu. Fourier growth of parity decision trees. arXiv preprint, 2021. URL: https://arxiv.org/abs/2103.11604.
  29. Svyatoslav Gryaznov, Pavel Pudlák, and Navid Talebanfard. Linear branching programs and directional affine extractors. In 37th Computational Complexity Conference, CCC 2022, volume 234 of LIPIcs, pages 4:1-4:16, 2022. URL: https://doi.org/10.4230/LIPIcs.CCC.2022.4.
  30. Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM, 56(4):20:1-20:34, 2009. URL: https://doi.org/10.1145/1538902.1538904.
  31. John Hastad. Almost optimal lower bounds for small depth circuits. Adv. Comput. Res., 5:143-170, 1989. Google Scholar
  32. Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of protocols for xor functions. SIAM Journal on Computing, 47(1):208-217, 2018. Google Scholar
  33. Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random generation from one-way functions (extended abstracts). In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC 1989, pages 12-24, 1989. URL: https://doi.org/10.1145/73007.73009.
  34. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-24508-4.
  35. Jesse Kamp, Anup Rao, Salil P. Vadhan, and David Zuckerman. Deterministic extractors for small-space sources. J. Comput. Syst. Sci., 77(1):191-220, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.014.
  36. Swastik Kopparty, Vsevolod F Lev, Shubhangi Saraf, and Madhu Sudan. Kakeya-type sets in finite vector spaces. Journal of Algebraic Combinatorics, 34(3):337-355, 2011. Google Scholar
  37. Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM J. Comput., 22(6):1331-1348, 1993. URL: https://doi.org/10.1137/0222080.
  38. Chin Ho Lee, Edward Pyne, and Salil P. Vadhan. Fourier growth of regular branching programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, volume 245 of LIPIcs, pages 2:1-2:21, 2022. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.2.
  39. Chin Ho Lee and Emanuele Viola. Some limitations of the sum of small-bias distributions. Theory of Computing, 13(1):1-23, 2017. Google Scholar
  40. Jiatu Li and Tianqi Yang. 3.1n - o(n) circuit lower bounds for explicit functions. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1180-1193, 2022. URL: https://doi.org/10.1145/3519935.3519976.
  41. Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 168-177, 2016. URL: https://doi.org/10.1109/FOCS.2016.26.
  42. Xin Li. Two source extractors for asymptotically optimal entropy, and (many) more. CoRR, abs/2303.06802, 2023. URL: https://doi.org/10.48550/arXiv.2303.06802.
  43. Xin Li and Yan Zhong. Explicit directional affine extractors and improved hardness for linear branching programs. CoRR, abs/2304.11495, 2023. URL: https://doi.org/10.48550/arXiv.2304.11495.
  44. Ueli M. Maurer and Stefan Wolf. Privacy amplification secure against active adversaries. In Advances in Cryptology - CRYPTO '97, 17th Annual International Cryptology Conference, volume 1294 of Lecture Notes in Computer Science, pages 307-321, 1997. URL: https://doi.org/10.1007/BFb0052244.
  45. 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.
  46. Noam Nisan. Pseudorandom generators for space-bounded computation. Comb., 12(4):449-461, 1992. URL: https://doi.org/10.1007/BF01305237.
  47. Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  48. Ran Raz. Extractors with weak random seeds. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC 2005, pages 11-20, 2005. URL: https://doi.org/10.1145/1060590.1060593.
  49. Omer Reingold, Thomas Steinke, and Salil Vadhan. Pseudorandomness for regular branching programs via fourier analysis. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 655-670. Springer, 2013. Google Scholar
  50. 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, 2017. Google Scholar
  51. Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 658-667. IEEE, 2013. Google Scholar
  52. Yoav Tzur. Notions of weak pseudorandomness and gf (2n)-polynomials. Master’s thesis, Weizmann Institute of Science, 2009. Google Scholar
  53. Salil P. Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1-336, 2012. URL: https://doi.org/10.1561/0400000010.
  54. Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles (preliminary version). In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 1-10, 1985. URL: https://doi.org/10.1109/SFCS.1985.49.
  55. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput., 3(1):103-128, 2007. URL: https://doi.org/10.4086/toc.2007.v003a006.
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact