^June July – 2008

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.

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.

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$

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.