All reports by Author Edward Pyne:

__
TR24-106
| 17th June 2024
__

James Cook, Jiatu Li, Ian Mertz, Edward Pyne#### The Structure of Catalytic Space: Capturing Randomness and Time via Compression

__
TR23-208
| 21st December 2023
__

Dean Doron, Edward Pyne, Roei Tell#### Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL

__
TR23-168
| 13th November 2023
__

Edward Pyne#### Time-Space Tradeoffs for BPL via Catalytic Computation

Revisions: 2

__
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

James Cook, Jiatu Li, Ian Mertz, Edward Pyne

In the catalytic logspace ($CL$) model of (Buhrman et.~al.~STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This ... more >>>

Dean Doron, Edward Pyne, Roei Tell

We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation.

Our first contribution is a derandomization of bounded-space machines from hardness assumptions for classes of uniform deterministic algorithms, for which strong (but non-matching) lower bounds can be unconditionally proved. ... more >>>

Edward Pyne

We prove that for every $\alpha \in [1,1.5]$,

$$

\text{BPSPACE}[S]\subseteq \text{TISP}[2^{S^{\alpha}},S^{3-\alpha}]

$$

where $\text{BPSPACE}[S]$ corresponds to randomized space $O(S)$ computation, and $\text{TISP}[T,S]$ to time $poly(T)$, space $O(S)$ computation. Our result smoothly interpolates between the results of (Nisan STOC 1992) and (Saks and Zhou FOCS 1995), which prove $\text{BPSPACE}[S]$ is contained ...
more >>>

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