Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > READ ONCE BRANCHING PROGRAMS:
Reports tagged with read once branching programs:
TR14-023 | 19th February 2014
Gil Cohen, Anat Ganor, Ran Raz

#### Two Sides of the Coin Problem

Revisions: 1

In the Coin Problem, one is given n independent flips of a coin that has bias $\beta > 0$ towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply ... more >>>

TR17-179 | 20th November 2017
Alexander Knop

#### IPS-like Proof Systems Based on Binary Decision Diagrams

It is well-known that there is equivalence between ordered resolution and ordered binary decision diagrams (OBDD) [LNNW95]; i.e., for any unsatisfiable formula ?, the size of the smallest ordered resolution refutation of ? equal to the size of the smallest OBDD for the canonical search problem corresponding to ?. But ... more >>>

TR18-112 | 5th June 2018
Raghu Meka, Omer Reingold, Avishay Tal

#### Pseudorandom Generators for Width-3 Branching Programs

Revisions: 1

We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work ... more >>>

TR20-016 | 17th February 2020
Kuan Cheng, William Hoza

#### Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if ... more >>>

TR21-020 | 15th February 2021
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma

#### Error Reduction For Weighted PRGs Against Read Once Branching Programs

Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [BCG20], is a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and ... more >>>

TR21-048 | 27th March 2021
William Hoza

#### Better Pseudodistributions and Derandomization for Space-Bounded Computation

Revisions: 1

Three decades ago, Nisan constructed an explicit pseudorandom generator (PRG) that fools width-$n$ length-$n$ read-once branching programs (ROBPs) with error $\varepsilon$ and seed length $O(\log^2 n + \log n \cdot \log(1/\varepsilon))$ (Combinatorica 1992). Nisan's generator remains the best explicit PRG known for this important model of computation. However, a recent ... more >>>

ISSN 1433-8092 | Imprint