Algorithmic Construction of Sets for k-Restrictions Dana Moshkovitz

Yüklə 490 b.
ölçüsü490 b.

Algorithmic Construction of Sets for k-Restrictions

  • Dana Moshkovitz

  • Joint work with Noga Alon and Muli Safra

  • Tel-Aviv University

Talk Plan


Problem Definition

On Forgetful Hot-Tempered Pirates and Helpless Goldsmiths

Formal Definition [~NSS95]

  • Input: alphabet , length m. demands f1,…,fs:k{0,1},

  • Solution: Am s.t

    • for every 1i1<…
      • there is aA s.t. fj(a(i1),…,a(ik))=1.
  • Measure: how small |A| is


Goldsmith-Pirate Games Capture Many Known Problems

  • universal sets

  • hashing and its generalizations

  • group testing

  • set-cover gadget

  • separating codes

  • superimposed codes

  • color coding

Application I Universal Set

  • every k configuration is tried.

Application II Hashing

  • Goal: small set of functions [m][q]

  • For every kq in [m], some function maps them to k different elements

Generalized Hashing Theorem

  • Definition (t,u)-hash families [ACKL]: for all TU, |T|=t, |U|=u, some function f satisfies f(i)≠f(j) for every iT, jU-{i}.

  • Theorem: For any fixed 2≤t0, one can construct efficiently a (t,u)-hash family over alphabet of size t+1, whose

  • rate (i.e logqm/n) ≥ (1-)t!(u-t)u-t/uu+1ln(t+1)

Application III Group Testing [DH,ND…]

  • m people

  • at most k-1 are ill

  • can test a group: contains illness?

  • Goal: identify the ill people by few tests.

Group-Tests Theorem

  • Theorem: For every >0, there exists d(), s.t for any number of ill people d>d(), there exists an algorithm that outputs a set of at most (1+)ed2lnm group-tests in time polynomial in the population’s size (m).

Application IV Orientations [AYZ94]

  • Input: directed graph G

  • Question: simple k-path?

  • if G were DAG…

Application IV Orientations [AYZ94]

Application V Set-Cover Gadget

Approximability of Set-Cover


  • Random and Pseudo-Random Solutions


  • D:m[0,1] - probability distribution.

  • density w.r.t D is:

  •  = minI,j PraD[ fj(a(I))=1 ]

Probabilistic Strategy

Deterministic Construction!

  • Deterministic Construction!

First Observation

  • support(D) is a solution if density positive w.r.t D.

Second Observation

  • A k-wise, O()-close to D is a solution.

  • Theorem [EGLNV98]: Product dist. are efficiently (poly(qk,m,-1)) approximatable

So What’s the Problem?

  • It’s much more costly than a random solution!

  • Random solution: ~ klogm/ for all distributions!

  • k-wise -close to uniform: O(2kk2 log2m /2) [AGHP90]

Background Sum-Up

  • Random strings are good solutions for k-restriction problems

    • if one picks the ‘right’ distribution…
  • k-wise approximating distributions are deterministic solutions

    • of larger size…
  • Our goal: simulate deterministically the probabilistic bound

Our Results


  • Greedy

  • on approximation


  • Claim: Can find a solution of size --1(klnm+lns) in time poly(C(m,k), s, |support|)

  • Proof:

  • Formulate as Set-Cover:

    • elements:
    • sets:
  • Apply greedy strategy.


Concatenation Works For Permutations Invariant Demands


Dividing Into BLOCKS

Splitters, [NSS95]

  • What are they?

  • How to construct?

    • needs only (b-1) cuts
    • use concatenation

Multi-Way Splitters

  • For any I1⊎…⊎It[m], |⊎Ij|k, some partition to b blocks is a split.

  • k-restriction problem!

Necklace Splitting [A87]

Necklace Splitting [A87]

Necklace Splitting Theorem

The b=t=2 Case


  • Beat k-wise approximations for k-restriction problems.

  • Multi-way splitters via Necklace Splitting.

  •  Substantial improvements for:

    • Group Testing
    • Generalized Hashing
    • Set-Cover

Further Research

  • Applications: complexity, algorithms, combinatorics, cryptography…

  • Better constructions? different techniques?


  • [NSS95] Universality/Hashing via split and “smart search”.

  • Our work:

  • Generalizing [NSS95] techniques

    • approximating distributions
    • multi-way splitters via topological Necklace Splitting
  • Many more applications: group testing, an improved hardness for SET-COVER under P≠NP…

invariance under permutations

  • Definition: We say C1,…,Cs k are invariant under permutations,

  • if for any permutation :[k][k],

  • {C1,…,Cs} = {(C1),…,(Cs)}

Yüklə 490 b.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2022
rəhbərliyinə müraciət

    Ana səhifə