Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR23-040 | 28th March 2023
Edward Pyne, Ran Raz, Wei Zhan

Certified Hardness vs. Randomness for Log-Space

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

TR22-150 | 7th November 2022
Aaron (Louie) Putterman, Edward Pyne

Near-Optimal Derandomization of Medium-Width Branching Programs

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

TR22-034 | 3rd March 2022
Chin Ho Lee, Edward Pyne, Salil Vadhan

Fourier Growth of Regular Branching Programs

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

TR21-143 | 13th October 2021
Edward Pyne

Hitting Sets For Regular Branching Programs

Revisions: 2

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
Previously, the best known seed length for regular branching programs of width $w$ with a single accept state was ... more >>>

TR21-108 | 22nd July 2021
Edward Pyne, Salil Vadhan

Limitations of the Impagliazzo--Nisan--Wigderson Pseudorandom Generator against Permutation Branching Programs

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

TR21-019 | 17th February 2021
Edward Pyne, Salil Vadhan

Pseudodistributions That Beat All Pseudorandom Generators

Revisions: 1

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

TR20-138 | 9th September 2020
William Hoza, Edward Pyne, Salil Vadhan

Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

Revisions: 1

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

ISSN 1433-8092 | Imprint