Affine extractors give some of the best-known lower bounds for various computational models, such as AC$^0$ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudl\'{a}k, and Talebanfard (CCC' 22) introduced a stronger version of affine extractors known as directional affine extractors, together with a generalization of ROBPs where each node can make linear queries, and showed that the former implies strong lower bound for a certain type of the latter known as strongly read-once linear branching programs (SROLBPs). Their main result gives explicit constructions of directional affine extractors for entropy $k > 2n/3$, which implies average-case complexity $2^{n/3-o(n)}$ against SROLBPs with exponentially small correlation. A follow-up work by Chattopadhyay and Liao (ECCC' 22) improves the hardness to $2^{n-o(n)}$ at the price of increasing the correlation to polynomially large, via a new connection to sumset extractors introduced by Chattopadhyay and Li (STOC' 16) and explicit constructions of such extractors by Chattopadhyay and Liao (STOC' 22). Both works left open the questions of better constructions of directional affine extractors and improved average-case complexity against SROLBPs in the regime of small correlation.

This paper provides a much more in-depth study of directional affine extractors, SROLBPs, and ROBPs. Our main results include:
(1) formal separation between SROLBP and ROBP, showing that SROLBPs can be exponentially more powerful than ROBPs.
(2) An explicit construction of directional affine extractors with $k=o(n)$ and exponentially small error, which gives average-case complexity $2^{n-o(n)}$ against SROLBPs with exponentially small correlation, thus answering the two open questions raised in previous works.
(3) An explicit function in AC$^0$ that gives average-case complexity $2^{(1-\delta)n}$ against ROBPs with negligible correlation, for any constant $\delta>0$. Previously, the best size lower bound for any function in AC$^0$ against ROBPs is only $2^{\Omega(\sqrt{n})}$.

One of the key ingredients in our constructions is a new linear somewhere condenser for affine sources, which is based on dimension expanders. We conjecture that it also works for general weak random sources, and prove it under the Polynomial Freiman-Ruzsa conjecture. The condenser also leads to an unconditional improvement of the entropy requirement of explicit affine extractors with negligible error.

Affine extractors give some of the best-known lower bounds for various computational models, such as AC$^0$ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudl\'{a}k, and Talebanfard (CCC' 22) introduced a stronger version of affine extractors known as directional affine extractors, together with a generalization of ROBPs where each node can make linear queries, and showed that the former implies strong lower bound for a certain type of the latter known as strongly read-once linear branching programs (SROLBPs). Their main result gives explicit constructions of directional affine extractors for entropy $k > 2n/3$, which implies average-case complexity $2^{n/3-o(n)}$ against SROLBPs with exponentially small correlation. A follow-up work by Chattopadhyay and Liao (ECCC' 22) improves the hardness to $2^{n-o(n)}$ at the price of increasing the correlation to polynomially large, via a new connection to sumset extractors introduced by Chattopadhyay and Li (STOC' 16) and explicit constructions of such extractors by Chattopadhyay and Liao (STOC' 22). Both works left open the questions of better constructions of directional affine extractors and improved average-case complexity against SROLBPs in the regime of small correlation.

This paper provides a much more in-depth study of directional affine extractors, SROLBPs, and ROBPs. Our main results include:
(1) formal separation between SROLBP and ROBP, showing that SROLBPs can be exponentially more powerful than ROBPs.
(2) An explicit construction of directional affine extractors with $k=o(n)$ and exponentially small error, which gives average-case complexity $2^{n-o(n)}$ against SROLBPs with exponentially small correlation, thus answering the two open questions raised in previous works.
(3) An explicit function in AC$^0$ that gives average-case complexity $2^{(1-\delta)n}$ against ROBPs with negligible correlation, for any constant $\delta>0$. Previously, the best size lower bound for any function in AC$^0$ against ROBPs is only $2^{\Omega(\sqrt{n})}$.

One of the key ingredients in our constructions is a new linear somewhere condenser for affine sources, which is based on dimension expanders. We conjecture that it also works for general weak random sources, and prove it under the Polynomial Freiman-Ruzsa conjecture. The condenser also leads to an unconditional improvement of the entropy requirement of explicit affine extractors with negligible error.

Affine extractors give some of the best-known lower bounds for various computational models, such as AC$^0$ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudl\'{a}k, and Talebanfard (CCC' 22) introduced a stronger version of affine extractors known as directional affine extractors, together with a generalization of ROBPs where each node can make linear queries, and showed that the former implies strong lower bound for a certain type of the latter known as strongly read-once linear branching programs (SROLBPs). Their main result gives explicit constructions of directional affine extractors for entropy $k > 2n/3$, which implies average-case complexity $2^{n/3-o(n)}$ against SROLBPs with exponentially small correlation. A follow-up work by Chattopadhyay and Liao (ECCC' 22) improves the hardness to $2^{n-o(n)}$ at the price of increasing the correlation to polynomially large, via a new connection to sumset extractors introduced by Chattopadhyay and Li (STOC' 16) and explicit constructions of such extractors by Chattopadhyay and Liao (STOC' 22). Both works left open the questions of better constructions of directional affine extractors and improved average-case complexity against SROLBPs in the regime of small correlation.

This paper provides a much more in-depth study of directional affine extractors, SROLBPs, and ROBPs. Our main results include:
(1) formal separation between SROLBP and ROBP, showing that SROLBPs can be exponentially more powerful than ROBPs.
(2) An explicit construction of directional affine extractors with $k=o(n)$ and exponentially small error, which gives average-case complexity $2^{n-o(n)}$ against SROLBPs with exponentially small correlation, thus answering the two open questions raised in previous works.
(3) An explicit function in AC$^0$ that gives average-case complexity $2^{(1-\delta)n}$ against ROBPs with negligible correlation, for any constant $\delta>0$. Previously, the best size lower bound for any function in AC$^0$ against ROBPs is only $2^{\Omega(\sqrt{n})}$.

One of the key ingredients in our constructions is a new linear somewhere condenser for affine sources, which is based on dimension expanders. We conjecture that it also works for general weak random sources, and prove it under the Polynomial Freiman-Ruzsa conjecture. The condenser also leads to an unconditional improvement of the entropy requirement of explicit affine extractors with negligible error.