We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of $5$ if the weights satisfy \textit{probability constraints}
(for any pair of vertices $u$ and $v$, $w_{uv}+w_{vu}=1$). Special cases ... more >>>

This work initiates the study of algorithms
for the testing of monotonicity of mechanisms.
Such testing algorithms are useful for
searching dominant strategy mechanisms.
An $\e$-tester for monotonicity
is given a query access to a mechanism,
accepts if monotonicity is satisfied,
and rejects with high probability if more than $\e$-fraction
more >>>

This paper introduces a new technique for removing existential quantifiers
over quantum states. Using this technique, we show that there is no way
to pack an exponential number of bits into a polynomial-size quantum
state, in such a way that the value of any one of those bits ... more >>>