The complexity class PPP contains all total search problems many-one reducible to the PIGEON problem, where we are given a succinct encoding of a function mapping n+1 pigeons to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original five” syntactically-defined subclasses ... more >>>

We give a lower bound of ?(?n) on the unambiguous randomised parity-query complexity of the approximate majority problem – that is, on the lowest randomised parity-query complexity of any function over {0,1}? whose value is "0" if the Hamming weight of the input is at most n/3, is "1" if ... more >>>

Given a non-negative real matrix $M$ of non-negative rank at least $r$, can we witness this fact by a small submatrix of $M$? While Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a witnessing is possible approximately: an $m\times n$ matrix always ... more >>>