We present a new lower bound technique for two types of restricted
Branching Programs (BPs), namely for read-once BPs (BP1s) with
restricted amount of nondeterminism and for (1,+k)-BPs. For this
technique, we introduce the notion of (strictly) k-wise l-mixed
Boolean functions, which generalizes the concept of l-mixedness ... more >>>

We present a new efficient sampling method for approximating
r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on
n variables up to an additive error \epsilon n^r.We prove a new
general paradigm in that it suffices, for a given set of constraints,
to pick a small uniformly random ... more >>>

In this paper, we investigate and analyze for the first time the
stability properties of heterogeneous networks, which use a
combination of different universally stable queueing policies for
packet routing, in the Adversarial Queueing model. We
interestingly prove that the combination of SIS and LIS policies,
LIS and NTS policies, ... more >>>