We construct an $\varepsilon$-error PRG for permutation read-once branching programs of length $n$ and width $w$ with seed length
$$
O\left((\log w+\log(1/\varepsilon))\cdot \log n\right).
$$
This gives an exponential improvement in the dependence on $w$ compared with the constructions of De (CCC 2011) and Steinke (ECCC 2012). Compared with the ... more >>>

The graph homomorphism problem HOM is: given an $n$-vertex source graph $G$ and an $h$-vertex target graph $H$, is there a mapping from $V(G)$ to $V(H)$ that preserves edges? A straightforward brute-force algorithm for HOM has running time $O(2^{n \log h})$ and it is known that, under ETH, there are ... more >>>

The Orthogonal Vectors Problem (OV$_{n,d}$) takes as input two sets $A,B$ each containing $n$ $d$-dimensional Boolean vectors, and outputs $1$ if and only if there exists $a \in A$ and $b \in B$ such that $a$ and $b$ are orthogonal. The OV conjecture states that for every $\varepsilon > 0$, ... more >>>