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

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

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

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

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

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

Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities, is an outstanding problem that has received a lot of attention after its introduction by Raz and Tzamaret (2008). Very recently, Efremenko, Garlik and Itsykson (2023) proved the first exponential lower bounds ... more >>>

We initiate a study of doubly-efficient interactive proofs of proximity, while focusing on properties that can be tested within query-complexity that is significantly sub-linear, and seeking interactive proofs of proximity in which

1. The query-complexity of verification is significantly smaller than the query-complexity of testing.

2. The query-complexity of the ... more >>>