^March April – 2012 ^May

Distance oracle is a data structure that provides fast answers to distance queries. Recently, the problem of designing distance oracles capable of answering restricted distance queries, that is, estimating distances on a subgraph avoiding some forbidden vertices, has attracted a lot of attention. In this talk, we will consider forbidden set distance oracles for planar graphs. I’ll present an efficient compact distance oracle that is capable of handing any number of failures. In addition, we will consider a closely related notion of fully dynamic distance oracles. In the dynamic distance oracle problem instead of getting the failures in the query phase, we rather need to handle an adversarial online sequence of update and query operations. Each query operation involves two vertices s and t whose distance needs to be estimated. Each update operation involves inserting/deleting a vertex/edge from the graph. I’ll show that our forbidden set distance oracle can be tweaked to give fully dynamic distance oracle with improved bounds compared to the previously known fully dynamic distance oracle for planar graphs. Joint work with Ittai Abraham and Cyril Gavoille

Many significant historical corpora contain leaves that are mixed up and no longer bound in their original state as multi-page documents. The reconstruction of old manuscripts from a mix of disjoint leaves can therefore be of a paramount importance to historians and literary scholars. In collaboration with the The Friedberg Genizah Project, we show that visual similarity provides meaningful pair-wise similarities between handwritten leaves and then go a step further and suggest a semi-automatic clustering tool that helps reconstruct the original documents. The proposed solution is based on a graphical model that makes inferences based on catalog information provided for each leaf as well as on the pairwise similarities of handwriting. Several novel active clustering techniques are explored, and the solution is applied to a significant part of the Cairo Genizah, where the problem of joining leaves remains unsolved even after a century of extensive study by hundreds of human scholars.

Augmented Reality is the technology and art of fusing virtual content into our reality. The technology was invented before the personal computer and runs nowadays on any smartphone. Yet, the “ultimate” Augmented Reality application that is as useful and as natural as taking a picture with a camera phone, have not been demonstrated so far.

We propose an intuitive framework that captures the challenges in creating disruptive AR experiences. We name this framework The Reality Mixing Continuum. The continuum spans between experiences that assume nothing in advance about the environment (the real world) and those that make strict assumptions about it. We discuss why assumptions about the environment are key in shaping an “ultimate” experience.

In the scope of that framework we describe our own quest, focused on Augmented Reality technological paradigms that enable natural experiences, while minimizing the assumptions about the environment. We describe three new paradigms: In-Place content creation with the premise of blending virtual and real content naturally. In-Place Sketch Interaction for manipulating augmented content. And, Out of the Cube, enabling a tangible interaction based on the Rubik’s Cube.

The presentation includes video demonstrations reviewing the latest and greatest in the field of Augmented Reality with the intention to introduce the field to the audience as well as to stimulate thinking about existing challenges.

Einstein didnt believe in quantum mechanics because "God does not play dice". We will show that one possible interpretation of Einstein's own law, governing free fall in space-time, is that god plays a considerable amount of dice. We arrived at this line of inquiry through our study of airplane boarding, which in turn started from a problem in disk scheduling which is a part of "practical" systems performance analysis, landing squarly in the realm of computer science with or without software engineering. We will try to survey the interconnections between all these topics. No prior knowledge is required, experience with boarding airplanes will be useful.