Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SET SYSTEMS:
Reports tagged with Set Systems:
TR96-004 | 18th January 1996

#### Deterministic Restrictions in Circuit Complexity

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

TR21-007 | 14th January 2021
Sai Sandeep

#### Almost Optimal Inapproximability of Multidimensional Packing Problems

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

ISSN 1433-8092 | Imprint