We consider the following problem: estimate the size of a nonempty set $S\subseteq\left[ N\right] $, given both quantum queries to a membership oracle for $S$, and a device that generates equal superpositions $\left\vert S\right\rangle $ over $S$ elements. We show that, if $\left\vert S\right\vert $ is neither too large nor ... more >>>

We develop the notion of double samplers, first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders.

We show how double samplers give a generic way of amplifying distance in a way that enables ... more >>>

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2016). We consider three different variants of graph homomorphisms, namely injective ... more >>>