^May June – 2010

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.

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

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.

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.