Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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




ISSN 1433-8092 | Imprint