From: Kelli McGee \(Kelly Services Inc\) (a-kellim@microsoft.com)
Date: Thu May 27 2004 - 08:29:48 PDT
You are invited to attend…
*****************************************************************************************************
WHO: Dana Moshkovitz
AFFILIATION: School of Computer Science, Tel-Aviv University
TITLE: Algorithmic Construction of Sets for k-Restrictions
WHEN: Fri 6/04/2004
WHERE: 113/1159 Research Lecture Room, Microsoft Research
TIME: 3:30PM-5:00PM
HOST: Jennifer Chayes and Christian Borgs
******************************************************************************************************
ABSTRACT:
In k-restriction problems one wishes to find a small set of strings that satisfies the following property: if one observes any k indices, and seeks for some specific restriction on them (out of a large set of possible restrictions given as input), then at least one of the strings meets this restriction.
Problems of this type arise in many fields in Computer Science. A few prominent examples are group testing and generalized hashing.
The standard approach for deterministically solving such problems is via almost k-wise independence or k-wise approximations for other distributions.
We offer a generic algorithmic method that yields considerably smaller constructions. Specifically it allows us to derive substantial improvements for the problems mentioned above.
To this end, we generalize a previous work of Naor, Schulman and Srinivasan.
Among other results, we greatly enhance the combinatorial objects in the heart of their method, called splitters, using the topological Necklace Splitting Theorem.
We are also able to derive an improved inapproximability result for Set-Cover under the assumption PNP.
Joint work with Noga Alon and Muli Safra
BIO:
Dana Moshkovitz is currently a PhD student under the supervision of Prof. Muli Safra in Tel-Aviv University. Her Masters, also carried out under the supervision of Prof. Safra in TAU, concerned a generic derandomization task with many applications, including group testing and generalized hashing. It also improved the known inapproximability factor for the classic Set-Cover problem, under the assumption P neq NP. This is the work I will present in MSR.
Dana Moshkovitz’s has a broad interest in the theory of Computer Science; mainly in Probabilistically Checkable Proofs, and also in Randomness and Pseudo-Randomness, Property Testing and Coding Theory.
During her studies she was awarded several excellence honors, and finished both her BA and MSc Summa Cum Laude.
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Thu May 27 2004 - 08:30:27 PDT