The ExactlyN problem in the number-on-forehead (NOF) communication setting asks k players, each of whom can see every input but their own, if the k input numbers add up to N. Introduced by Chandra, Furst and Lipton in 1983, ExactlyN is important for its role in understanding the strength of ... more >>>

We show that the deterministic decision tree complexity of a (partial) function or relation f lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation f \circ g as long as the gadget g satisfies a property that we call stifling. We observe that several simple ... more >>>

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on n input bits, each of which has approximate Fourier sparsity at most O(n^3) and randomized parity decision tree complexity \Theta(n). This improves upon the ... more >>>

We construct a simple and total XOR function F on 2n variables that has only O(\sqrt{n}) spectral norm, O(n^2) approximate rank and n^{O(\log n)} approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of \Omega(\sqrt{n}). This yields the first exponential gap between the logarithm of the ... more >>>