^December January – 2006

The way we access, store and display video are all derived from "engineering constraints". Entities such as pixels and frames serves as the building blocks of many video applications. These entities where designed to simplify and reduce the cost of manufacturing process. They were not design for depicting the information contained in the scene. For example, video is inherently limited by the sensors bounds (dimensions, frame-rate, resolution, and modality) regardless the content. The best one can do is trade resolution for field-of-view (zoom). In this talk I will show how these building block may be replaced by content driven units, and how these bounds may be exceeded. By combining information from multiple sensors the user can controlled and exceeded some of these bounds. We can increase space and time resolution and combine information from different sensing modalities. The above engineering approach also dominates video user interface. For example, despite the random access of many recent video storage devices (PC, DVD) we are currently accessing video sequentially. The rest of the talk argues in favor of content driven user interfaces. I will begin with a simple content based time-line. An anchoring layer that is robust to acquisition, broadcast and storage types, and is based only on the video's content. Then I will show steps towards object based video interfaces. An approach for segmenting video content that exploits the inherent temporal redundancy in video will be presented. Along this application, I will show that small coherent regions subsume regular pixels when facing a segmentation problem. An importance based user interface, complete the content driven approach for video interfaces. The importance in this case is evaluated by embedding high dimensional video data into low dimension space where properties as local uniqueness may reflect importance

Storage applications may be revolutionized in the near future by new technologies, such as band recording, page-oriented optical memory, and volume holographic storage. However, all of these require efficient two-dimensional error-correcting codes capable of correcting bursts of errors.

In this talk we will survey the latest results in two-dimensional burst-correcting coding theory. These results use two different approaches to the problem. The first employs interleaving schemes, and to that end, we will generalize the notion of the distance of two points in the plane, to a quantity that reflects the relative dispersion of three (or more) points. In the context of interleaving schemes we will show codes, and their less-known counterpart, anticodes (which also have interesting applications in the game of Go, or multicasting in multi-processor networks), as well as lattice-based interleavers. The second is a direct algebraic approach, in which we will show the first ever constructions for such codes, and bounds on their efficiency.

The presentation is for a general audience. No prior knowledge is needed.

The talk is based on some recent works with Tuvi Etzion (Technion) and Alexander Vardy (UCSD).

Moshe Schwartz was born in Israel in 1975. He received the B.A., M.Sc.,and Ph.D. degrees from the Technion – Israel Institute of Technology, Haifa, Israel, in 1997, 1998, and 2004 respectively, all from the Computer Science Department.

He was a Fulbright post-doctoral researcher in the Department of Electrical and Computer Engineering, University of California San Diego, USA, and is now a post-doctoral researcher in the Department of Electrical Engineering, California Institute of Technology. His research interests include coding theory (both algebraic and combinatorial), constrained coding, network coding, digital sequences, and combinatorial structures.

In peer-to-peer (p2p) systems, work is distributed among the participating peers, unlike the classical client-server architecture, where work is done by a central server. One of the fundamental problems facing p2p systems is that different peers may have different interests: in extreme cases, some peers may even wish to destroy the usability of the system. It is therefore necessary to develop a (possibly implicit) notion of trust, so as to allow peers to continue functioning in the face of diverse, potentially hostile peers. In this talk I will describe a line of recent research which studies the algorithmic aspect of concepts such as "trust," "collaborative filtering" and "recommendation systems."

Informally, program obfuscation aims at making a program "unintelligible" while preserving its functionality. Whereas practitioners have been attempting to obfuscate programs for many years, it has only recently received attention in the theoretical community.

Barak et al formalized the notion of obfuscation, and showed that there exist (contrived) classes of functions that cannot be obfuscated. In contrast, Canetti and Wee showed, under various complexity assumptions, how to obfuscate a particular class of simple functions, called point functions, that output 1 on a single point (and output 0 everywhere else). Thus, it seemed completely possible that most functions of interest can be obfuscated even though in principle general purpose obfuscators do not exist.

We show that this is unlikely to be the case. In particular, we consider the notion of obfuscation w.r.t. auxiliary input, which corresponds to the setting where the adversary, which is given the obfuscated circuit, may have some additional a priori information.

We first argue that any useful positive result about the possibility of obfuscation must satisfy this extended definition. We then prove that there exist many natural classes of functions that cannot be obfuscated w.r.t. auxiliary input, both when the auxiliary input is dependent of the function being obfuscated and even when the auxiliary input is independent of the function being obfuscated

A short bio: I did my undergraduate studies in the Hebrew university in 1994-1997. I did my Master's degree in the Weizmann Institute in 1998-2001, under the supervision of Adi Shamir. I am currently doing my PhD at MIT, under the supervision of Shafi Goldwasser.

I will present a simple randomized construction of size $n^3$ and depth $5.3 \log(n)$ monotone circuit for the majority function on n variables.The result can be viewed as a reduction in the size and a partial derandomization of Valiant's classical construction of an $n^{5.3}$ monotone formula from 1984. On the other hand, compared with the deterministic monotone circuit obtained from the sorting network of Ajtai, Komlos, and Szemeredi 1983, the circuit is much simpler and has depth $O(\log n)$ with a small constant.

Techniques used in the construction incorporate fairly recent results showing that expansion yields performance guarantee for the belief propagation message passing algorithms for decoding low-density parity-check (LDPC) codes. As part of the construction, we obtain optimal-depth linear-size monotone circuits for the promise version of the problem, where the number of 1's in the input is promised to be either less than one third, or greater than two thirds. At last, I will show that the size can be further reduced at the expense of increased depth, and obtain a monotone circuit for the majority of size and depth about $n^{1+sqrt(2)}$ and $9.9log(n)$.

Joint work with Avner Magen and Toni Pitassi.

Short Bio:

I am a postdoc in the theory group at the Department of Computer Science in the University of British Columbia and at the Pacific Institute for the Mathematical Sciences. My main fields of interest are Theoretical Computer Science, Algebraic Graph Theory, Coding Theory, Expander graphs, and Graphs of High Girth. Before that I was a postdoc at the University of Toronto. I receive my Ph.D. in 2002 from the Hebrew University.

his is joint work with Anna Korhonen (Computer Laboratory, Cambridge University).

This work touches on the relation between syntax and semantics, it stems from the work of Beth Levin in "English Verb Classes and Alternations" (1993): 'If the syntactic properties of a verb indeed follow in large part from its meaning, then it should be possible to identify general principles that derive the behavior of a verb from its meaning.' (p. 11)

In our work, we observe the behaviour (in syntactic terms) of verbs in a corpus and derive the semantic classes of these verbs. The behaviour is described by subcategorisation frames. The subcategorisation frame (SCF) of a verb is the syntactic structure of its arguments. For example the SCF of a transitive verb is "NP" because it has a direct object which is a noun phrase (NP)

We parse the texts and observe the (SCF) distribution of the verbs. We then cluster the verbs using the information bottleneck method as well as a very naive nearest neighbour method

I will describe two works: one on texts from a general corpus (British National Corpus) and the other on a domain specific (biomedical) corpus. The main difference between the corpora is that the biomedical texts contains much less polysemy than is usually seen in general language. We report how polysemy is reflected in the clustering results. Since verbs in a domain specific corpus can have a meaning different from that in general language - we observe semantic classes that are particular to the biomedical domain.

This work has important implications for NLP applications The semantic classes obtained in an unsupervised manner reflect knowledge about the domain. This knowledge can be used for various information retrieval and information extraction applications.

The Program for Medical and Population Genetics, Broad Institute of MIT and Harvard And Center for Human Genetic Research, Massachusetts General Hospital

The pervasive effect of genetic variation on medically important phenotypes provides a means for dissecting their underlying mechanisms by identifying variants that are associated with traits of interest. Current trends in human genetics now facilitate, for the first time, pursuing this potential by execution of large scale studies that scan the entire genome for potentially associated variants. Specifically, the talk will present

(1) The International HapMap Project, a data resource we participated in developing to enable genomewide association studies, and what our analyses of these data tell us about human variation.

(2) The current generation of SNP array technology, and how computation and statistics improvements allow it to cover the majority of common human variants.

(3) The tale of a pilot association scan in an isolated population in Micronesia, where we show such scans are more promising than elsewhere, though we expose practical complexities of real data and the computational challenges they present.

Some of the research presented was performed as part of the International HapMap Analysis Team, or in collaborations with Affymetrix Inc. and the Friedman lab at Rockefeller University.