Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with designs:
TR11-144 | 2nd November 2011
Greg Kuperberg, Shachar Lovett, Ron Peled

Probabilistic existence of rigid combinatorial structures

We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, $t$-designs, and $t$-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. ... more >>>

TR20-106 | 15th July 2020
Eshan Chattopadhyay, Jesse Goodman

Explicit Extremal Designs and Applications to Extractors

Revisions: 3

An $(n,r,s)$-design, or $(n,r,s)$-partial Steiner system, is an $r$-uniform hypergraph over $n$ vertices with pairwise hyperedge intersections of size $0$, we extract from $(N,K,n,k)$-adversarial sources of locality $0$, where $K\geq N^\delta$ and $k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $K\geq N^{1/2+o(1)}$. As a result, we ... more >>>

ISSN 1433-8092 | Imprint