We study the complexity of computing Boolean functions using AND, OR
and NOT gates. We show that a circuit of depth $d$ with $S$ gates can
be made to output a constant by setting $O(S^{1-\epsilon(d)})$ (where
$\epsilon(d) = 4^{-d}$) of its input values. This implies a
superlinear size lower bound ... more >>>

Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. ... more >>>