^March April – 2005 ^May

In 1965 Ivan Sutherland introduced the idea of the “Ultimate Display”. The ripples of effect from his original concept and realization are still working themselves out today. In this research we explore one possible paradigm of the Ultimate Interface: one where people don’t actually have to do anything physical in order to interact with and through a computer, but where the computer is directly attuned to their thoughts.

A particularly exciting realm in which to investigate the possibilities inherent in this idea is within immersive virtual environments (IVE). Imagine a situation where a participant only needs to think about an action in order to make it happen - to move, to select an object, to shift gaze, to control the movements of their (virtual) body, or to design the environment itself, by thought alone. What would that be like?

We have connected the Graz brain-computer-interface (BCI) with a highly immersive, Cave-like virtual reality (VR) system. Participants were able to rotate in a virtual bar room and move along a single axis along a virtual street, by only imagining hand and feet movement. Our results indicate that subjects performed in the VR better than with traditional BCI. We are now conducting an additional set of experiments to further understand the advantages of VR to BCI, and to further evaluate the participants’ subjective experience.

We have connected the Graz brain-computer-interface (BCI) with a highly immersive, Cave-like virtual reality (VR) system. Participants were able to rotate in a virtual bar room and move along a single axis along a virtual street, by only imagining hand and feet movement. Our results indicate that subjects performed in the VR better than with traditional BCI. We are now conducting an additional set of experiments to further understand the advantages of VR to BCI, and to further evaluate the participants’ subjective experience.

Bio:

Doron Friedman is a post-doc Research Fellow in the VECG lab in the University College of London, working on the physiological and neuroscientific basis of the sense of presence in virtual reality. His interest is in intelligent media systems. He received his PhD from Tel Aviv University with a thesis on knowledge-based formalization of cinematic expression. His inventions were also deployed in the industry: he was the co-founder of Earthnoise, Inc., a startup company that provided a solution for semi-automated video editing and delivery over the Internet and mobile networks, and the inventor of Falcon2000, a successful AI tool for solving the year2000 problem in Assembly language legacy software.

Edit distance is a fundamental measure of distance between strings, having applications in text processing, web search, and genomics. In some of these applications the two inputs strings are very long. In others, one needs to maintain edit distance on massive repositories of strings. The current best algorithms for edit distance are too inefficient for these tasks, even if one settles for reasonable approximations.

In this talk I will describe the first "sketching schemes" for approximating edit distance. In these schemes, each string is individually compressed into a small "sketch", and the distance between strings is estimated using the sketches alone. Sketching schemes are a main building block in nearest neighbor schemes and are related to low distortion embeddings. They are thus very useful for handling large repositories of strings.

If time permits, I will also outline a new linear time algorithm, which achieves the best known approximation factor for edit distance. This algorithm is useful for estimating edit distance between long strings.

Joint work with T.S. Jayram, Robi Krauthgamer, and Ravi Kumar.

We study a representative task allocation problem called shortest paths: Let $G$ be a graph in which the edges are owned by self interested agents. The cost of each edge is privately known to its owner. Let $s$ and $t$ be two distinguished nodes in $G$. Given a distribution on the edge costs, the goal is to design a mechanism (protocol) which acquires a cheap $s-t$ path.

We first observe that the class of generalized VCG mechanisms has desired monotonicity properties. We exploit this observation to obtain, under an independence assumption, expected payments which are significantly lower than the worst case bounds of [AT02,ess03]. We then investigate whether these payments can be improved when there is competition among paths.

Surprisingly, we give evidence to the fact that typically such competition hardly helps incentive compatible mechanisms. In particular, we show this for the celebrated VCG mechanism. We then construct a novel general protocol combining the advantages of incentive compatible and non-incentive compatible mechanisms.

Under reasonable assumptions on the agents we show that the overpayment of our mechanism is very small. Finally, we show that many other task allocation problems can be reduced to shortest paths.

Joint work with Artur Czumaj

Bio:

Amir Ronen is a senior lecturer (assistant professor) in the Industrial Engineering and Management Faculty at the Technion. He received his Ph.D. from the Hebrew University of Jerusalem in the year 2000. His main areas of interest are the interplay between game theory and computer science, theoretical computer science, game theory, electronic commerce and the Internet.

We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was $\log^{4/3}()$ obtained by Armoni, Ta-Shma, Wigderson and Zhou.

As undirected st-connectivity is complete for the class of problems solvable by symmetric, non-deterministic, log-space computations (the class SL), this algorithm implies that $SL=L$ (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov has presented a, space $\log n \log\log n$, deterministic algorithm for undirected st-connectivity.

Our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labelling and log-space constructible universal-exploration sequences for general graphs.