All reports by Author Edward Pyne:

__
TR23-102
| 13th July 2023
__

Chin Ho Lee, Edward Pyne, Salil Vadhan#### On the Power of Regular and Permutation Branching Programs

__
TR23-040
| 28th March 2023
__

Edward Pyne, Ran Raz, Wei Zhan#### Certified Hardness vs. Randomness for Log-Space

__
TR22-150
| 7th November 2022
__

Aaron (Louie) Putterman, Edward Pyne#### Near-Optimal Derandomization of Medium-Width Branching Programs

__
TR22-034
| 3rd March 2022
__

Chin Ho Lee, Edward Pyne, Salil Vadhan#### Fourier Growth of Regular Branching Programs

__
TR21-143
| 13th October 2021
__

Edward Pyne#### Hitting Sets For Regular Branching Programs

Revisions: 2

__
TR21-108
| 22nd July 2021
__

Edward Pyne, Salil Vadhan#### Limitations of the Impagliazzo--Nisan--Wigderson Pseudorandom Generator against Permutation Branching Programs

__
TR21-019
| 17th February 2021
__

Edward Pyne, Salil Vadhan#### Pseudodistributions That Beat All Pseudorandom Generators

Revisions: 1

__
TR20-138
| 9th September 2020
__

William Hoza, Edward Pyne, Salil Vadhan#### Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

Revisions: 1

Chin Ho Lee, Edward Pyne, Salil Vadhan

We give new upper and lower bounds on the power of several restricted classes of arbitrary-order read-once branching programs (ROBPs) and standard-order ROBPs (SOBPs) that have received significant attention in the literature on pseudorandomness for space-bounded computation.

Regular SOBPs of length $n$ and width $\lfloor w(n+1)/2\rfloor$ can exactly simulate general ... more >>>

Edward Pyne, Ran Raz, Wei Zhan

Let $\mathcal{L}$ be a language that can be decided in linear space and let $\epsilon >0$ be any constant. Let $\mathcal{A}$ be the exponential hardness assumption that for every $n$, membership in $\mathcal{L}$ for inputs of length~$n$ cannot be decided by circuits of size smaller than $2^{\epsilon n}$.

We ...
more >>>

Aaron (Louie) Putterman, Edward Pyne

We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length $n$ and width $w$ in space

$$\tilde{O}\left(\log n+\sqrt{\log n}\cdot\log w\right).$$

In particular, we obtain an almost optimal space $\tilde{O}(\log n)$ derandomization of programs up to width $w=2^{\sqrt{\log n}}$.

Previously, ...
more >>>

Chin Ho Lee, Edward Pyne, Salil Vadhan

We analyze the Fourier growth, i.e. the $L_1$ Fourier weight at level $k$ (denoted $L_{1,k}$), of read-once regular branching programs.

We prove that every read-once regular branching program $B$ of width $w \in [1,\infty]$ with $s$ accepting states on $n$-bit inputs must have its $L_{1,k}$ bounded by

$$

\min\left\{ ...
more >>>

Edward Pyne

We construct an explicit $\varepsilon$-hitting set generator (HSG) for regular ordered branching programs of length $n$ and $\textit{unbounded width}$ with a single accept state that has seed length

\[O(\log(n)(\log\log(n)+\log(1/\varepsilon))).\]

Previously, the best known seed length for regular branching programs of width $w$ with a single accept state was ...
more >>>

Edward Pyne, Salil Vadhan

The classic Impagliazzo--Nisan--Wigderson (INW) psesudorandom generator (PRG) (STOC `94) for space-bounded computation uses a seed of length $O(\log n \cdot \log(nwd/\varepsilon))$ to fool ordered branching programs of length $n$, width $w$, and alphabet size $d$ to within error $\varepsilon$. A series of works have shown that the analysis of the ... more >>>

Edward Pyne, Salil Vadhan

A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a pseudorandom pseudodistribution generator (PRPG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of PRPGs for ... more >>>

William Hoza, Edward Pyne, Salil Vadhan

We prove that the Impagliazzo-Nisan-Wigderson (STOC 1994) pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of $\widetilde{O}(\log d + \log n \cdot \log(1/\varepsilon))$, assuming the program has only one accepting vertex in the final layer. Here, $n$ is the length of the ... more >>>