We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, ... more >>>

For every constant $\epsilon>0$, we give an $\exp(\tilde{O}(\sqrt{n}))$-time algorithm for the $1$ vs $1-\epsilon$ Best Separable State (BSS) problem of distinguishing, given an $n^2\times n^2$ matrix $M$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $\rho$ that $M$ accepts with probability $1$, ... more >>>

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function $f: ... more >>>