^June July – 2008 ^August

Adviser: Luis Gravano and Panagiotis (Panos) Ipeirotis

Abstract: The vast majority of Internet users utilize search functionality to navigate the text and text-annotated collections of a variety of web sites. Users of sites such as the New York Times archive, YouTube, and others often face long lists of results for their queries due to the large size of the collections. Processing numerous items is also a hurdle for "exploratory" users who have no specific query in mind, such as a new shopper in an online store or a researcher accessing a news archive. In this work, we attempt to address this problem. We investigate faceted searching and browsing to provide users with access methods that are useful for discovering the content and the structure of long search results or large collections. Hierarchies that organize items based on their topics are common for browsing a large set of items. For example, Yahoo! uses a topic-based hierarchy to guide users to their web pages of interest. Google News and Newsblaster enable news readers to quickly navigate the daily news based on a hierarchy of topics and related events. We first present summarization-aware topic faceted searching and browsing, which integrates clustering and summarization, so that users can browse a list of summarized clusters in the query results instead of individual documents. We have built a fully functional summarization-aware system for daily news. In addition to the topic facet, time can be used as an alternative facet for browsing search results. We explore time as an important dimension and suggest a general framework for time-based language models to consider time in the retrieval task. In fact, many facets, other than topic and time, can be useful for faceted searching and browsing. As a result, we propose supervised and unsupervised methods to identify and extract multiple relevant facets from collections. Yet incorporating such facets in searching or browsing is not an easy task. A typical approach to utilize facets in searching and browsing is to build individual hierarchies for each facet. Unfortunately, these hierarchies are currently manually or semi-manually constructed and populated. This prevents deploying such hierarchies for large collections due to the cost of manually annotating each item in the collections. To solve this problem, we propose a system to automate the construction of hierarchies for the extracted facets, and corresponding human studies to verify the effectiveness of our methods. We apply the faceted hierarchies to a range of large data sets, including collections of annotated images, television programming schedules, and web pages.

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the $O(Nlog N)$ running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and sub-linear running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear time is infeasible; nevertheless, in many applications it suffices to find only the significant Fourier coefficients, that is, the Fourier coefficients whose magnitude is at least a $tau$-fraction (say, 1%) of the $ell_2$-norm of the entire Fourier transform (ie, the sum of squared Fourier coefficients). In this paper we present an algorithm that finds the significant Fourier coefficients of functions $f$ over any finite abelian group $G$, which is: {bf Local.} The running time and number of function entries read by the algorithm is polynomial in $log N$, $1/tau$ and $L_1(f)$ (for $N=card G$ and $L_1(f)$ denoting the sum of absolute values of the Fourier coefficients of $f$). {bf Input-oblivious.} The set of entries read by the algorithm depends only on the domain $G$ and on an upper bound on the sum of Fourier coefficients $L_1(f)$, and not on the input function $f$ itself. That is, the {em same fixed} set of entries is read for all functions over the same domain and with the same upper bound on their sum of Fourier coefficients. {bf Robust to noise.} The algorithm finds the significant Fourier coefficients of $f$, even if the function entries it receives are corrupted by random noise. Furthermore, we present extensions of this algorithm to handle {em adversarial noise} in running time {em sub-linear} in the domain size. Our algorithm improves on the prior input-oblivious algorithms in: (1) handling functions over any finite abelian group, (2) being robust to noise, and (3) achieving {better running time in terms of $L_1(f)$.

We present applications of our algorithm to compressed sensing, to solving noisy variants of the Hidden Number Problem with advice, and to decoding polynomial rate Homomorphism codes and polynomial rate Multiplication codes.

An error correcting code is said to be locally testable if there is a test that can check whether a given string is a codeword of the code, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first explicitly studied by Goldreich and Sudan (J. ACM 53(4)) and since then several constructions of LTCs were suggested.

While the best known construction of LTCs achieves very efficient parameters, it relies heavily on algebraic tools and on PCP machinery. We present a new and arguably simpler construction of LTCs that is purely combinatorial and does not rely on PCP machinery. Finally, our construction matches the parameters of the best known construction.

The rapid accumulation of genetic material (e.g. sequencing of genes and genomes) and the prediction of new proteins should help us to better understand evolution at the molecular level. This task, however, is not trivial. First, the evolution of many organisms includes operations such as horizontal transfers (i.e. events of transferring genetic material from one lineage in the evolutionary tree to a different lineage) and rearrangements of genetic material. Thus, it requires accurate modeling of complex biological phenomena. Second, as most of the problems in the field are NP-hard, it requires designing sophisticated algorithms and heuristics for accurate and fast inference of evolutionary models. In this talk I will describe our recent attempts to address these challenges. I will discuss hardness issues related to inferring phylogenetic trees and networks, and will describe a few approaches for modeling and inferring evolution in the presence of horizontal gene transfer, partial horizontal gene transfer, and rearrangements of genetic material. No background in biology will be assumed.

I will present two results due to Hartmanis and Hopcroft.

Let F be any formal system for proving theorems. We assume that F is axiomatizable, that F is consistent, and that F is of sufficient power to prove basic theorems of set theory.

Theorem 1: For every F we can effectively construct an i such that $\phi_i$ is recursive and $P^{\phi_i}=NP^{\phi_i}$ can neither be proved nor disproved in F.

Theorem 2: There exist an algorithm which can be explicitly given whose running time is $n^2$ but there is no proof in F that it runs in time $<2^n$

This work presents research in the field of machine learning and transportation studies. Urban Traffic Control System (UTCS), which rely on a network of sensors, aim to describe real-time traffic in urban areas using a set of parameters and estimating them. Though the state of the art systems focus on data analysis, little has been done to date in terms of prediction. In this work, we describe a machine learning system for traffic flow management and control to address the problem of traffic regulation. This new algorithm is obtained by combining a Random Forests algorithm with an Adaboost algorithm as a weak learner. We show that o! ur algorithm performs relatively well on real data, and enables, according to the traffic flow evaluation model, to estimate and predict whether there is congestion or not at a given time at a given road intersection. The problem of avoiding traffic congestion can be solved by updating the signal timing of the traffic lights at an intersection in advance, based on the prediction of heavy traffic.

In the problem of secure computation, two or more parties wish to compute a function of their private inputs while maintaining several security properties, such as independence of their inputs, privacy, correctness of the computation and others. General protocols for computing all of the above properties, and others, are well known. An exception is the emph{fairness} property, which guarantees that if one party receives output, then all parties receive output. Fairness is only generally achievable if a strict majority of the players are honest. Indeed, it was proven by Cleve cite{Cleve86} in 1986 that it is impossible for two parties to flip a fair coin.

In this talk, I will first present a recent surprising result (STOC 08) that demonstrates the possibility of computing certain particular functions of interest with complete fairness. I will then introduce a new (weaker) security definition called "partial fairness", and present a general feasibility results in this model.

Abstract: The speaker works in requirements engineering (RE) and has not done any work on aspect orientation, cross-cutting cocerns, or early aspects. Nevertheless, RE is certainly early. The speaker believes that in RE, one never sees any cross-cutting concerns, but there are plenty of concerns and these are all requirements. The speaker is of the view that, in the early stages, requirements are not well enough structured that any concern can be identified as cross cutting as opposed to not cross cutting. Everything is just a concern. Nevertheless, there will certainly be cross-cutting concerns later when the required system is built.

---

Bio: Daniel M. Berry got his Ph.D. in Computer Science from Brown University in 1974. He was on the faculty of the Computer Science Department at the University of California, Los Angeles, USA from 1972 until 1987. He was in the Computer Science Faculty at the Technion, Israel from 1987 until 1999. From 1990 until 1994, he worked for half of each year at the Software Engineering Institute at Carnegie Mellon University, USA, where he was part of a group that built CMU's Master of Software Engineering program. During the 1998-1999 academic year, he visited the Computer Systems Group at the University of Waterloo in Waterloo, Ontario, Canada. In 1999, Berry moved to what is now the Cheriton School of Computer Science at the University of Waterloo. Berry's current research interests are software engineering in general, and requirements engineering and electronic publishing in the specific.

Abstract: This talk describes grounded analysis (GA) as a method to discover grounded theories (GTs) to be subjected to later empirical validation. It shows that a good instance of Requirements Engineering (RE) is an instance of GA for the purpose of discovering the artifacts that RE produces. Therefore, these artifacts are also GTs.

Work with Michael W. Godfrey, Ric Holt, Cory J. Kapser, and Isabel Ramos

Bio: Daniel M. Berry got his Ph.D. in Computer Science from Brown University in 1974. He was on the faculty of the Computer Science Department at the University of California, Los Angeles, USA from 1972 until 1987. He was in the Computer Science Faculty at the Technion, Israel from 1987 until 1999. From 1990 until 1994, he worked for half of each year at the Software Engineering Institute at Carnegie Mellon University, USA, where he was part of a group that built CMU's Master of Software Engineering program. During the 1998-1999 academic year, he visited the Computer Systems Group at the University of Waterloo in Waterloo, Ontario, Canada. In 1999, Berry moved to what is now the Cheriton School of Computer Science at the University of Waterloo. Berry's current research interests are software engineering in general, and requirements engineering and electronic publishing in the specific.

This talk should (hopefully) be of interest to people working in distributed systems, distributed CSPs, and multi-agent systems. Loosely coupled multi-agent systems are perceived as easier to plan for because they require less coordination between agent sub-plans. In this paper we set out to formalize this intuition. We establish an upper bound on the complexity of multi-agent planning problems that depends exponentially on two parameters quantifying the level of agents' coupling, and on these parameters only. The first parameter is problem-independent, and it measures the inherent level of coupling within the system. The second is problem-specific and it has to do with the minmax number of action-commitments PER AGENT required to solve the problem. Most importantly, the direct dependence on the number of agents, on the overall size of the problem, and on the length of the agents' plans, is only polynomial.

This result is obtained using a new algorithmic methodology which we call ``planning as CSP+planning''. We believe this to be one of the first formal results to both quantify the notion of agents' coupling and to demonstrate a tractable planning algorithm for fixed coupling levels. Joint work with Carmel Domshlak from the Technion.