Algorithmic Construction of Sets for k-Restrictions Dana Moshkovitz
tarix 03.01.2019 ölçüsü 490 b. #89126
Dana Moshkovitz Joint work with Noga Alon and Muli Safra Tel-Aviv University Talk Plan Techniques Greedine$$ k-wise approximating distributions Concatenation Problem Definition On Forgetful Hot-Tempered Pirates and Helpless Goldsmiths Formal Definition [~NSS95] Input: alphabet , length m. demands f1,…,fs:k{0,1}, Solution: Am s.t for every 1i1<… there is aA s.t. fj(a(i1),…,a(ik))=1. Measure: how small |A| isApplications Goldsmith-Pirate Games Capture Many Known Problems universal sets hashing and its generalizations group testing set-cover gadget separating codes superimposed codes color coding … every k configuration is tried. Application II Hashing Goal: small set of functions [m][q]For every kq in [m], some function maps them to k different elements Generalized Hashing Theorem Definition (t,u)-hash families [ACKL] : for all TU, |T|=t, |U|=u, some function f satisfies f(i)≠f(j) for every iT, jU-{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 GQuestion: simple k-path?if G were DAG… Application IV Orientations [AYZ94] Delete ‘bad’ edges Now G is a DAG… 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 PraD[ 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)) approximatableSo 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… Our goal: simulate deterministically the probabilistic boundOur Results Outline Greedine$$ Claim: Can find a solution of size --1(klnm+lns) in time poly(C(m,k), s, |support|)Proof: Formulate as Set-Cover: 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 if for any permutation :[k][k], {C1,…,Cs} = {(C1),…,(Cs)} Dostları ilə paylaş:
