^December January – 2009 ^February

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.

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).

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