We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give ... more >>>

A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design ... more >>>

We consider Boolean circuits over $\{\lor,\land,\neg\}$ with negations applied only to input variables. To measure the ``amount of negation'' in such circuits, we introduce the concept of their ``negation width.'' In particular, a circuit computing a monotone Boolean function $f(x_1,\ldots,x_n)$ has negation width $w$ if no nonzero term produced (purely ... more >>>