Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with partitions:
TR06-069 | 11th May 2006
Christian Gla├čer, Alan L. Selman, Stephen Travers, Klaus W. Wagner

The Complexity of Unions of Disjoint Sets

This paper is motivated by the open question
whether the union of two disjoint NP-complete sets always is
NP-complete. We discover that such unions retain
much of the complexity of their single components. More precisely,
they are complete with respect to more general reducibilities.

more >>>

TR22-160 | 31st October 2022
Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, N. V. Vinodchandran

The Geometry of Rounding

Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of $\mathbb{R}^d$ are equivalent, we introduce the following natural partition problem which we call the secluded hypercube partition problem: Given $k\in\mathbb{N}$ (ideally small) and $\epsilon>0$ (ideally large), is there a partition of ... more >>>

ISSN 1433-8092 | Imprint