For a directed graph $G = (V, E)$, we say that a weight function $\rho \colon E \to [M]$ is *min-isolating* if the minimum-weight path from $u$ to $v$ is unique for each pair of vertices $u, v \in V$ such that $v$ is reachable from $u$. If we could ... more >>>

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