The noisy population recovery problem is a basic statistical inference problem. Given an unknown distribution in $\{0,1\}^n$ with support of size $k$,
and given access only to noisy samples from it, where each bit is flipped independently with probability $1/2-\eps$,
estimate the original probability up to an additive error of ... more >>>

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of
a class of high-degree polynomials that can be simulated via arithmetic circuits ... more >>>

We investigate the possible structural changes one can perform on a game graph without destroying the winning regions of the players playing a parity game on it. More precisely, given a game graph $(G,p)$ for which we can efficiently compute winning regions, can we remove or add a vertex or ... more >>>