Shiva Chaudhuri, Jaikumar Radhakrishnan

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 >>>

Sai Sandeep

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 >>>