We consider the general network information flow problem, which was introduced by Ahlswede et. al. We show a periodicity effect: for every integer m greater than 1, there exists an instance of the network information flow problem that admits a solution if and only if the alphabet size is a ... more >>>

We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function $f$, where $\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a monotone $f$, and rejects $f$ with high probability if it is $\e$-far from being monotone (i.e., every monotone ... more >>>