Linear branching programs and directional affine extractors

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F22%3A00559512" target="_blank" >RIV/67985840:_____/22:00559512 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.CCC.2022.4" target="_blank" >https://doi.org/10.4230/LIPIcs.CCC.2022.4</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.CCC.2022.4" target="_blank" >10.4230/LIPIcs.CCC.2022.4</a>

Result language

angličtina

Original language name

Linear branching programs and directional affine extractors

Original language description

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.n- 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.n- 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

37th Computational Complexity Conference (CCC 2022)

ISBN

978-3-95977-241-9

ISSN

1868-8969

e-ISSN

—

Number of pages

16

Pages from-to

1-16

Publisher name

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl

Event location

Philadelphia

Event date

Jul 20, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—