Algorithmic Construction of Sets for k-Restrictions Dana Moshkovitz



Yüklə 490 b.
tarix03.01.2019
ö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



Techniques



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



Applications



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



Background

  • Random and Pseudo-Random Solutions



Density

  • 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



Outline

  • Greedy

  • on approximation



Greedine$$

  • 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



Concatenation Works For Permutations Invariant Demands



Theorem



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



Sum-Up

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



Context

  • [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)}




Dostları ilə paylaş:


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2019
rəhbərliyinə müraciət

    Ana səhifə