^May June – 2010 ^July

The popularity of web-based mapping services such as Google Earth/Maps and Microsoft Virtual Earth (Bing), has led to an increasing awareness of the importance of spatial data and its incorporation into both web-based search and the databases that support it, whereas in the past attention to spatial data had been primarily limited to geographic information systems (GIS). An immediate byproduct of this awareness is the expectation of a real time response as is the experience of users of spreadsheets. Spatial data is distinguished from conventional data by having extent, which means that rather than being limited to locations, it also includes collections of locations [and, most importantly in both cases, their attributes]. Having extent is challenging in several respects. First, it is not easy to order such data which impacts the ability to retrieve it quickly. Second, the specification of the data is both vague and ambiguous by virtue of the amount of precision that is needed to make it useful. The ambiguity is very clear when one considers that a location as well as a collection of locations can be specified either or both geometrically via, for example, its centroid or its boundary, and verbally via the name that is used to refer to it. The latter is both aided and complicated by the possible need to make use of knowledge, whether implicit or explicit, of the information that is inherent in its container hierarchy. In this lecture we explore how these issues are manifested and resolved, both conceptually, and via demonstrations of real systems, thereby demonstrating how wide a net has been cast on geographic information systems by todaysapplications.

*The lecture is sponsored by the ACM Distinguished Speaker Program*

The problem of deciding which advertisements a publisher should display, given some contextual information about its users, is nicely captured by the contextual bandit setting. In this talk, I will give an overview of the contextual bandit problem (also known as the multiarmed bandit problem with expert advice) and present new algorithms for this setting. I will focus on a couple recent theoretical developments that are bringing us closer to getting similar guarantees in the bandit setting as we have in supervised learning. I will also discuss some generalizations of the contextual bandit problem that are particularly relevant to computational advertising.

Imposing constraints in the form of a finite automaton or a regular expression is an effective way to incorporate additional a priori knowledge into sequence alignment procedures. With this motivation, Arslan introduced the Regular Language Constrained Sequence Alignment problem and proposed an $O(n^2t^4)$ time and $O(n^2t^2)$ space algorithm for solving it, where $n$ is the length of the input strings and $t$ is the number of states in the non deterministic automaton which is given as input. Chung et al. proposed a faster $O(n^2t^3)$ time algorithm for the same problem.

In this talk, I present an additional speed up to the algorithms for Regular Language Constrained Sequence Alignment by reducing their worst case time complexity bound to $O(n^2t^3/log t)$. This is done by establishing an optimal bound on the size of Straight-Line Programs solving the maxima computation subproblem of the basic dynamic programming algorithm.

In addition, I present a another solution we have studied, which is based on a Steiner Tree computation. While this solution does not yield an improvement in the worst case, our simulations show that both approaches are efficient in practice, especially when the input automata are dense.

Joint work with Gregory Kucherov and Michal Ziv-Ukelson.

Let $X$ be a simple region, and let $Q$ be a set of $m$ points in $X$. A disk cover of $Q$ with respect to $X$, is a set of disks (of variable radii), such that the union of these disks covers $Q$ and is contained in $X$. In other words: (i) each disk in the cover is contained in $X$, and (ii) each point $q in Q$, lies in a disk of the cover. A minimum disk cover of $Q$ with respect to $X$ is a disk cover of $Q$ with respect to $X$ of minimum cardinality. The problem of computing a minimum disk cover of a point set $Q$ with respect to a simple region $X$ arises, e.g., in the following setting. $X$ represents a secured area, and each point of $Q$ represents a client of a radio network. One must place the smallest possible number of transmitters, such that each client is served by at least one of the transmitters (i.e., is within the transmission range of at least one of the transmitters), and any point outside the area, is outside the range of each of the transmitters. Surprisingly, this problem is solvable in polynomial time, due to very nice combinatorial structure. In a paper presented at WADS 2009 and recently accepted to Algorithmica, we presented an exact polynomial time algorithm for the above problem (joint work with Matya Katz). In a paper accepted to ESA 2010 we give an improved almost-linear time algorithm (Joint work with Haim Kaplan, Matya Katz and Micha Sharir). I'll give the highlights of the proof, which I find simple, nice and elegant.

Many real-world problems are distributed by nature. Examples include network file systems, the scheduling of meetings among multiple agents, flight scheduling, industrial control systems, mobile sensor nets, wireless routing, etc. Agents or nodes that solve such distributed problems often coordinate their moves and share information to improve the efficiency of the problem solving process. Distributed search for solving distributed constraints problems is a domain in which agentsare naturally cooperative. In problems such as the meetings scheduling, agents are assumed to cooperate faithfully in finding a globally optimal solution. The degree of information sharing by the agents during search spans a wide range. At one extreme one can have an algorithm that involves sharing complete information by the agents. At this extreme case several agents can appoint a single representative (mediator) to solve their combined search problem by itself. The mediator agent receives the complete information of the agents and uses it for the search it performs. When coordination among the agents during search is less tight, agents could keep their private information about their constraints with other agents and only respond to specific requests about constraints values. At this other extreme we propose the use of asymmetric constraints among agents.

A {it generalized} Davenport-Schinzel sequence is one over a finite alphabet, none of whose subsequences are isomorphic to some fixed {it forbidden subsequence}. Davenport-Schinzel sequences have been used in bounding the complexity of geometric arrangements and the running time of algorithms and data structures. Let Ex(s,n) be the maximum length of an s-free sequence over an n-letter alphabet. The foremost open problem in this area is to characterize the asymptotic growth of Ex(s,n), for different forbidden subsequences s. In this talk I will survey everything that is known and worth knowing about the function Ex(s,n), including some new results

In this talk I will begin with a short background for computer scientists on proteins and their structures. Then I will give a brief overview on some aspects of the challenging field of computational protein structure prediction. In the second part of the talk I will summarize the main project of my PhD thesis: A novel cooperative energy term for hydrogen bonds. (In more details: hydrogen bonds are major constituents of protein structures and thus have been subject to many works. Yet, the common treatment of hydrogen bonds by energy functions is a considerable contributor to the infamous "local minima problem", which has annoyed predictors since the earliest days of this field. Cooperative terms for hydrogen bonds attempt to ease this problem by shifting the focus from the individual hydrogen bond to patterns of hydrogen bonds. I will present the main ideas of our novel cooperative hydrogen-bond term that is both effective and computationally efficient).

We review simple numerical methods for approximating solutions to second order differential equations. The specific aim is to explain why the simple "Verlet" algorithm, which is a direct second order finite difference approximation to the second order differential, is so desirable and widely used for initial value problems with conservation properties. The application of broad interest is Molecular Dynamics, but we will review the method by interpreting the basic properties of the method applied to the harmonic oscillator. Stability, energy conservation and time step control will be addressed for the discrete time.

We define a simple mathematical problem which we call the optimal base problem: Given a multiset S of positive integers, find a numeral base B such that the size of the representation of S in B is minimal. For example if S={16,30,54,60} then in base 10 the sum of the digits is 25, while in base 2 it is 13, and in base 3 it is 12. The problem gets more interesting when we allow mixed radix bases such as B=<3,5,2,2} with respect to which the sum of the digits in S is only 9. We analyze the complexity of this problem and propose a quasi-polynomial algorithm to solve it. Our implementation improves significantly on existing techniques. Finally we present also an application.

Joint work with Michael Codish, Carsten Fuhs and Peter Schneider-Kamp

The phenomenon of visual curve completion, where the visual system completes the missing contours of an occluded object, is a major problem in computer vision and vision research. I will first present some of the state-of-the-art algorithms for curve completion, as well as relevant perceptual and biological insights. Then I will discuss our own approach for curve completion, which is based on the abstraction of the visual cortex with modern differential geometry tools. In this work we present formal theoretical analysis and numerical solution methods, and we show results on natural images.

To save on municipal budget we wish to minimize the number of policemen in a city described by a graph. The policemen are positioned at graph vertices (cross-roads) and are in control of their own vertex along with its neighbors. Whenever a criminal occurs in her vicinity, the guard sends alarm signal to the central office. The condition is that having known the set of worried policemen, the department head should be able to locate the unique vertex where the crime happens. We will prove that in Manhattan the police posts have to be placed at exactly 35% of the street intersections. We will also survey known results on the problem in alternative settings: different types of graphs, the number of thieves greater than one, and the graphical radius of control greater than one.