License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.9
URN: urn:nbn:de:0030-drops-182794
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18279/
Chattopadhyay, Eshan ;
Liao, Jyun-Jie
Hardness Against Linear Branching Programs and More
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.
BibTeX - Entry
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2023.9,
author = {Chattopadhyay, Eshan and Liao, Jyun-Jie},
title = {{Hardness Against Linear Branching Programs and More}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {9:1--9:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-282-2},
ISSN = {1868-8969},
year = {2023},
volume = {264},
editor = {Ta-Shma, Amnon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18279},
URN = {urn:nbn:de:0030-drops-182794},
doi = {10.4230/LIPIcs.CCC.2023.9},
annote = {Keywords: linear branching programs, circuit lower bound, sumset extractors, hitting sets}
}
|
Keywords: |
|
linear branching programs, circuit lower bound, sumset extractors, hitting sets |
|
Collection: |
|
38th Computational Complexity Conference (CCC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
10.07.2023 |
