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.

We introduce planning games, the study of interactions of self-motivated agents in automated planning settings. Planning games extend STRIPS-like models of single-agent planning to systems of multiple self-interested agents, providing a rich class of structured games that capture subtle forms of local interactions. We consider two basic classes of planning games and adapt game-theoretic solution concepts to these models. In both models, agents may need to cooperate in order to achieve their goals, but are assumed to do so only in order to increase their net benefit. For each model we study the computational problem of finding a stable solution and provide efficient algorithms for systems exhibiting acyclic interaction structure.

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

We consider the following question: given a two-argument boolean function $f$, represented as an $Ntimes N$ binary matrix, how hard is to determine the (deterministic) communication complexity of $f$?

We address two aspects of this question. On the computational side, we prove that, under appropriate cryptographic assumptions (such as the intractability of factoring), the deterministic communication complexity of $f$ is hard to approximate to within some constant. Under stronger (yet arguably reasonable) assumptions, we obtains even stronger hardness results that match the best known approximation.

On the analytic side, we present a family of functions for which determining the communication complexity (or even obtaining non-trivial lower bounds on it) imply proving circuit lower bounds for some corresponding problems. Such connections between circuit complexity and communication complexity were known before (Karchmer-Wigderson 1988) only in the more involved context of relations (search problems) and not in the context of functions (decision problems). This result, in particular, may explain the difficulty of analyzing the communication complexity of certain functions such as the ``clique vs. independent-set'' family of functions, introduced by Yannakakis (1988).

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.

The topology of metabolic networks may provide important insights not only into the metabolic capacity of species, but also into the habitats in which they evolved. In this talk I will present several analyses of metabolic networks and show how various ecological insights can be obtained from genomic-based data. I will first introduce various factors that affect the structure of metabolic networks, and specifically the environmental and genetic determinants that affect network modularity. I will then present the first large-scale computational reconstruction of metabolic growth environments, analyzing the metabolic networks of hundreds of species and using a graph-theory based algorithm to identify for each species a set of seed compounds that must be exogenously acquired. Such seed sets form ecological "interfaces" between metabolic networks and their surroundings, approximating the effective biochemical environment of each species. Phylogenetic analysis of the seed sets reveals the complex dynamics governing gain and loss of biosynthetic capacity across the phylogenetic tree. I will further present an extension of this framework, accounting for interactions between species, by introducing a pair-wise, topology-based measure of biosynthetic support, which reflects the extent to which the nutritional requirements of one species could be satisfied by the biosynthetic capacity of another. I will show that this measure is aligned with host-parasite interactions and facilitates successful prediction of such interactions on a large-scale. Finally, I will discuss the application of this approach to the analysis of microbial communities and metagenomic data of the human microbiota and outline future research directions; The "reverse ecology" approach demonstrated in these analyses lays the foundations for further studying the complex web of interactions characterizing various ecosystems and the evolutionary interplay between organisms and their habitats on a large scale.

Traditionally, text categorization has been studied as the problem of training of a classifier using labeled data. However, people can categorize documents into named categories without any explicit training because we know the meaning of category names. In this paper, we introduce {em Dataless Classification}, a learning protocol that uses world knowledge to induce classifiers without the need for any labeled data. Like humans, a dataless classifier interprets a string of words as a set of semantic concepts. We propose a model for dataless classification and show that the label name alone is often sufficient to induce classifiers. Using Wikipedia as our source of world knowledge, we get 85.29% accuracy on tasks from the 20 Newsgroup dataset and 88.62% accuracy on tasks from a Yahoo! Answers dataset without {em any labeled or unlabeled}

Short Bio: Lev Ratinov is a Phd candidate in University of Illinois at Urbana-Champaign. He has done work on Machine Learning in Natural Language Processing and Information Extraction and has published a number of papers in several international conferences including "Dataless Classification"(AAAI08), "Learning and Inference with Constraints" (AAAI08), and "Guiding Semi-Supervision with Constraint-Driven Learning" (ACL07