Prophet inequality concerns a basic optimal stopping problem and states that simple threshold stopping policies --- i.e., accepting the first reward larger than a certain threshold --- can achieve tight $\frac{1}{2}$-approximation to the optimal prophet value. Motivated by its economic applications, this paper studies the robustness of this approximation to natural strategic manipulations in which each random reward is associated with a self-interested player who may selectively reveal his realized reward to the searcher in order to maximize his probability of being selected. We say a threshold policy is $\alpha$(-strategically)-robust if it (a) achieves the $\alpha$-approximation to the prophet value for strategic players; and (b) meanwhile remains a $\frac{1}{2}$-approximation in the standard non-strategic setting. Starting with a characterization of each player's optimal information revealing strategy, we demonstrate the intrinsic robustness of prophet inequalities to strategic reward signaling through the following results: (1) for arbitrary reward distributions, there is a threshold policy that is $\frac{1-\frac{1}{e}}{2}$-robust, and this ratio is tight; (2) for i.i.d. reward distributions, there is a threshold policy that is $\frac{1}{2}$-robust, which is tight for the setting; and (3) for log-concave (but non-identical) reward distributions, the $\frac{1}{2}$-robustness can also be achieved under certain regularity assumptions.

We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. Given an n-vertex graph G with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter є, achieves approximation factor (loglogn)2O(1/є3), and has amortized update time O(nєlogL) per operation, where L is the ratio of longest to shortest edge length. Query time for distance-query is O(2O(1/є)· logn· loglogL), and query time for shortest-path query is O(|E(P)|+2O(1/є)· logn· loglogL), where P is the path that the algorithm returns. To the best of our knowledge, even allowing any o(n)-approximation factor, no adaptive-update algorithms with better than Θ(m) amortized update time and better than Θ(n) query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting.

The Pandora's Box problem and its extensions capture optimization problems with stochastic input where the algorithm can obtain instantiations of input random variables at some cost. To our knowledge, all previous work on this class of problems assumes that different random variables in the input are distributed independently. As such it does not capture many real-world settings. In this paper, we provide the first approximation algorithms for Pandora's Box-type problems with correlations. We assume that the algorithm has access to samples drawn from the joint distribution on input. Algorithms for these problems must determine an order in which to probe random variables, as well as when to stop and return the best solution found so far. In general, an optimal algorithm may make both decisions adaptively based on instantiations observed previously. Such fully adaptive (FA) strategies cannot be efficiently approximated to within any sub-linear factor with sample access. We therefore focus on the simpler objective of approximating partially adaptive (PA) strategies that probe random variables in a fixed predetermined order but decide when to stop based on the instantiations observed. We consider a number of different feasibility constraints and provide simple PA strategies that are approximately optimal with respect to the best PA strategy for each case. All of our algorithms have polynomial sample complexity. We further show that our results are tight within constant factors: better factors cannot be achieved even using the full power of FA strategies.

We have tried to promote STEM (Science, Technology, Engineering, and Math) education for underserved students using interactive robots. As an advanced attempt to integrate art and design into STEM education (i.e., STEAM), in the present paper we introduce our afterschool program in which elementary students create live theatre using multiple robots as actors. We hope to receive feedback and comments on our afterschool curriculum and case study, and thus, we can run better sessions at schools and make a standardized protocol regarding this robot actors approach.

Distance perception is important for many virtual reality applications, and numerous studies have found underestimated egocentric distances in head-mounted display (HMD) based virtual environments. Applying minification to imagery displayed in HMDs is a method that can reduce or eliminate the underestimation [Kuhl et al. 2009; Zhang et al. 2012]. In a previous study, we measured distance judgments with direct blind walking through an Oculus Rift DK1 HMD and found that participants judged distance accurately in a calibrated condition, and minification caused subjects to overestimate distances [Li et al. 2014]. This article describes two experiments built on the previous study to examine distance judgments and minification with the Oculus Rift DK2 HMD (Experiment 1), and in the real world with a simulated HMD (Experiment 2). From the results, we found statistically significant distance underestimation with the DK2, but the judgments were more accurate than results typically reported in HMD studies. In addition, we discovered that participants made similar distance judgments with the DK2 and the simulated HMD. Finally, we found for the first time that minification had a similar impact on distance judgments in both virtual and real-world environments.

In head-mounted display systems, the confined size of the tracked space limits users from navigating larger virtual environments than the tracked physical space. Previous work suggests this constraint could be broken by asking users to back up or turn 180°whenever they encouter a wall in the real world [Williams et al. 2007]. In this work, we propose that the reorientation rate can be dynamically determined based on the user's instantaneous positional information and the shape of the navigable virtual space around the user. We conducted an experiment to compare our proposed dynamic reorientations with the previous Freeze-Turn reorientation. The results show that, with dynamic reorientations, participants walked a significantly longer distance between orientations than with Freeze-Turn reorientations.

Distance perception is a crucial component for many virtual reality applications, and numerous studies have shown that egocentric distances are judged to be compressed in head-mounted display (HMD) systems. Geometric minification, a technique where the graphics are rendered with a field of view that larger than the HMD's field of view, is one known method of eliminating the distance compression [Kuhl et al. 2009; Zhang et al. 2012]. This study uses direct blind walking to determine how minification might impact distance judgments in the Oculus Rift HMD which has a significantly larger FOV than previous minification studies. Our results show that people were able to make accurate distance judgments in a calibrated condition and that geometric minification causes people to overestimate distances. Since this study shows that minification can impact wide FOV displays such as the Oculus, we discuss how it may be necessary to use calibration techniques which are more thorough than those described in this paper.

Head-mounted display (HMD) systems make it possible to introduce discrepancies between physical and virtual world rotations. Small and hopefully unnoticed discrepancies can be useful for redirected walking algorithms which seek to allow a user to explore a large virtual space while confined to a small real space. Previous work has examined if people can detect discrepancies which are fixed (such as when the virtual world rotation rate is amplified by a fixed value). In this work, we conducted an experiment where participants turn 360 degrees in the real world and indicate if the virtual world rotation rate increased or decreased over the course of the turn. Our results show no difference between rotational gains which instantaneously jump from one value to another compared to gains which slowly change over the course of a 360 degree turn. We also found that the starting gain influenced the point of subjective equality. Finally, our work indicates that the range of reliably detectable gain changes is consistent for starting gains at 1 and starting gains at 2.

Traditional head-mounted display (HMD) locomotion interfaces map real world movements into an equivalent virtual world movement. Therefore, people cannot naturally explore a virtual world that is larger than the real world space. Joysticks, treadmills, redirected walking, and other techniques have been proposed by others to relax this restriction. In this work, we propose a new “general redirected walking” interface which works with arbitrary shaped and sized real worlds and virtual worlds by injecting dynamic translation or rotation gains into virtual world and steering a user to walk along a best direction in the real world identified by three heuristics in real time. We tested our algorithm with 10 virtual world models and 5 real-world (i.e., tracking system) models using software designed to simulate a user walking on a random path. We have also developed a prototype implementation for our HMD system.

Numerous studies report that people underestimate egocentric distances in head-mounted display (HMD) virtual environments compared to real environments when measured with direct blind walking. Recently, Zhang et al. [2012] demonstrated that minification can make verbal reports and blind walking more consistent with similar real world judgments. This research examines if minification causes people to misjudge gap affordances. We found that minification did not affect participants' verbal reports of whether they could fit through a gap without turning their shoulders.

Numerous studies report that people underestimate egocentric distances in Head-Mounted Display (HMD) virtual environments compared to real environments as measured by direct blind walking. Geometric minification, or rendering graphics with a larger field of view than the display's field of view, has been shown to eliminate this underestimation in a virtual hallway environment [Kuhl et al. 2006, 2009]. This study demonstrates that minification affects blind walking in a sparse classroom and does not influence verbal reports of distance. Since verbal reports of distance have been reported to be compressed in real environments, we speculate that minification in an HMD replicates peoples' real-world blind walking and verbal report distance judgments. We also demonstrate a new method for quantifying any unintentional miscalibration in our experiments. This process involves using the HMD in an augmented reality configuration and having each participant indicate where the targets and horizon appeared after each experiment. More work is necessary to understand how and why minification changes verbal- and walking-based egocentric distance judgments differently.