Počet záznamů: 1
Linear branching programs and directional affine extractors
- 1.
SYSNO ASEP 0559512 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Linear branching programs and directional affine extractors Tvůrce(i) Gryaznov, Svyatoslav (MU-W) SAI, RID, ORCID
Pudlák, Pavel (MU-W) RID, SAI
Talebanfard, Navid (MU-W) SAI, ORCID, RIDČíslo článku 4 Zdroj.dok. 37th Computational Complexity Conference (CCC 2022). - Dagstuhl : Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2022 / Lovett S. - ISSN 1868-8969 - ISBN 978-3-95977-241-9 Rozsah stran s. 1-16 Poč.str. 16 s. Forma vydání Online - E Akce 37th Computational Complexity Conference (CCC 2022) Datum konání 20.07.2022 - 23.07.2022 Místo konání Philadelphia Země US - Spojené státy americké Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova Boolean functions ; average-case lower bounds ; affine dispersers ; affine extractors Vědní obor RIV JC - Počítačový hardware a software Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) CEP GX19-27871X GA ČR - Grantová agentura ČR GA19-05497S GA ČR - Grantová agentura ČR Institucionální podpora MU-W - RVO:67985840 EID SCOPUS 85134412637 DOI 10.4230/LIPIcs.CCC.2022.4 Anotace A natural model of read-once 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 read-once, both generalizing standard read-once branching programs and parity decision trees. Our main results are as follows.
- Average-case complexity. We define a pseudo-random class of functions which we call directional affine extractors, and show that these functions are hard on average for the strongly read-once 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 average-case 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 read-once. Conversely, we show that a weakly read-once 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 read-once BPs, thus obtaining the equivalence between these proof systems.Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2023 Elektronická adresa https://doi.org/10.4230/LIPIcs.CCC.2022.4
Počet záznamů: 1