Gryaznov, Svyatoslav ;
Pudlák, Pavel ;
Talebanfard, Navid
Linear Branching Programs and Directional Affine Extractors
Abstract
A natural model of readonce linear branching programs is a branching program where queries are 𝔽₂ linear forms, and along each path, the queries are linearly independent. We consider two restrictions of this model, which we call weakly and strongly readonce, both generalizing standard readonce branching programs and parity decision trees. Our main results are as follows.
 Averagecase complexity. We define a pseudorandom class of functions which we call directional affine extractors, and show that these functions are hard on average for the strongly readonce model. We then present an explicit construction of such function with good parameters. This strengthens the result of Cohen and Shinkar (ITCS'16) who gave such averagecase hardness for parity decision trees. Directional affine extractors are stronger than the more familiar class of affine extractors. Given the significance of these functions, we expect that our new class of functions might be of independent interest.
 Proof complexity. We also consider the proof system Res[⊕], which is an extension of resolution with linear queries, and define the regular variant of Res[⊕]. A refutation of a CNF in this proof system naturally defines a linear branching program solving the corresponding search problem. If a refutation is regular, we prove that the resulting program is readonce. Conversely, we show that a weakly readonce linear BP solving the search problem can be converted to a regular Res[⊕] refutation with constant blow up, where the regularity condition comes from the definition of weakly readonce BPs, thus obtaining the equivalence between these proof systems.
BibTeX  Entry
@InProceedings{gryaznov_et_al:LIPIcs.CCC.2022.4,
author = {Gryaznov, Svyatoslav and Pudl\'{a}k, Pavel and Talebanfard, Navid},
title = {{Linear Branching Programs and Directional Affine Extractors}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {4:14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16566},
URN = {urn:nbn:de:0030drops165664},
doi = {10.4230/LIPIcs.CCC.2022.4},
annote = {Keywords: Boolean Functions, AverageCase Lower Bounds, AC0\lbrack2\rbrack, Affine Dispersers, Affine Extractors}
}
11.07.2022
Keywords: 

Boolean Functions, AverageCase Lower Bounds, AC0[2], Affine Dispersers, Affine Extractors 
Seminar: 

37th Computational Complexity Conference (CCC 2022)

Issue date: 

2022 
Date of publication: 

11.07.2022 