Given a set F

f_1, …, f_n of n continuous functions from R^d to R, we consider the problem of finding a center x* that minimizes OPT

sum_{f in F} f(x*). We present an efficient bi-criteria approximation that returns a small set X such that sum_{fin F}min_{xin X}f(x) exceeds OPT by a factor of no more than (1+eps). The quality of our algorithm (namely, the running time and the size of X) depends on the combinatorial complexity of the set F. I.e., the complexity of the arrangement formed by the functions f_i when viewed as manifolds in R^{d+1}. Given a set of n data elements e_1, …, e_n, a parameter k, and a cost function d(-,-), the ``bi-criteria approximate clustering'' problem addressed the finding of k'>k centers c_1, ..,c_{k'} for which sum_{i=1}^n min_j d(e_i,c_j) is at most (1+eps)-times the optimal k clustering. Bi-criteria approximate clustering stands at the center of several approximation algorithms for clustering and has seen a significant amount of research over the past decade.

Defining the function set F appropriately, our algorithm can be applied to obtain bi-criteria approximate clustering in several standard and new clustering settings. These include variants of k-mean clustering, where both the data elements e_i and the centers c_j are points in R^d, and the projective clustering in which the centers c_j are flats (affine subspaces) instead of points. We suggest the first approximation for the generalized projective clustering, where both the data elements e_i and the centers c_j are flats. New settings for which our scheme applies include recovering missing entries in a matrix, solving k-means in the context of missing data, motion analysis, and camera pose estimation. Not only does our framework unify several previous approaches for bi-criteria approximation, in the case of projective clustering it significantly improves the state of the art. Joint work with Michael Langberg.

Generalization sets are a software analysis concept that describes specialization of behavior in a way less restrictive than inheritance in OOP languages. According to the UML 2.0 standard, a generalization set divides a type into disjoint sub-types. Each sub-type may override the behavior of the super-type. A type may have several generalization sets. The sets are non-disjoint. An instance of the super-type may be an instance of each sub-type in each set. For example, an instance of a Person can be both an instance of an Employed or Unemployed person, and of a Resident or a Foreigner person.

In this talk we present several possible designs for the concept of Generalization Sets. Each design is centered around a particular design pattern: Inheritance, State or Enumeration. We discuss the advantages and disadvantages of each approach, and show examples of combining instances of these patterns to implement a type that has more then one generalization set. Finally, we compare the different properties of the patterns.

This talk is based on a submission to ECOOP 2009 by Mayer Goldberg and Guy Wiener

Locally Decodable Codes (LDC) allow one to decode any particular symbol of the input message by making a constant number of queries to a codeword, even if a constant fraction of the codeword is damaged. In a recent work ~cite{Yekhanin08} Yekhanin constructs a $3$-query LDC with sub-exponential length of size $exp(exp(O(frac{log n}{loglog n})))$. However, this construction requires a conjecture that there are infinitely many Mersenne primes. In this paper we give an unconditional $3$-query LDC construction with a shorter codeword length of $exp(exp(O(sqrt{log n log log n })))$. We also give a $2^r$-query LDC with length of $exp(exp(O(sqrt[r]{log n log log^{r-1} n })))$. The main ingredient in our construction is the existence of super-polynomial size set-systems with restricted intersections by cite{Grolmusz00} which hold only over composite numbers.