waashk/dblp huggingface dataset:
the myth of the folk theorem. a well-known result in game theory known as "the folk theorem" suggests that finding nash equilibria in repeated games should be easier than in one-shot games. in contrast, we show that the problem of finding any (approximate) nash equilibrium for a three-player infinitely-repeated game is computationally intractable (even when all payoffs are in {-1,0,1}), unless all of ppad can be solved in randomized polynomial time. this is done by showing that finding nash equilibria of (k+1)-player infinitely-repeated games is as hard as finding nash equilibria of k-player one-shot games, for which ppad-hardness is known (daskalakis, goldberg and papadimitriou, 2006; chen, deng and teng, 2006; chen, teng and valiant, 2007). this also explains why no computationally-efficient learning dynamics, such as the "no regret" algorithms, can be "rational" (in general games with three or more players) in the sense that, when one's opponents use such a strategy, it is not in general a best reply to follow suit.
finding short lattice vectors within mordell's inequality. the celebrated lenstra-lenstra-lovász lattice basis reduction algorithm (lll) can naturally be viewed as an algorithmic version of hermite's inequality on hermite's constant. we present a polynomial-time blockwise reduction algorithm based on duality which can similarly be viewed as an algorithmic version of mordell's inequality on hermite's constant. this achieves a better and more natural approximation factor for the shortest vector problem than schnorr's algorithm and its transference variant by gama, howgrave-graham, koy and nguyen. furthermore, we show that this approximation factor is essentially tight in the worst case.
rethinking internet routing. internet routing introduces many interesting challenges, far beyond the basic problem of computing paths on a graph. this talk presents an overview of several open research questions in internet routing, with the broader goal of placing the design of future routing architectures on a stronger theoretical foundation.
agnostically learning decision trees. we give a query algorithm for agnostically learning decision trees with respect to the uniform distribution on inputs. given black-box access to an *arbitrary* binary function f on the n-dimensional hypercube, our algorithm finds a function that agrees with f on almost (within an epsilon fraction) as many inputs as the best size-t decision tree, in time poly(n,t,1ε). this is the first polynomial-time algorithm for learning decision trees in a harsh noise model. we also give a *proper* agnostic learning algorithm for juntas, a sub-class of decision trees, again using membership queries. conceptually, the present paper parallels recent work towards agnostic learning of halfspaces (kalai et al, 2005); algorithmically, it is more challenging. the core of our learning algorithm is a procedure to implicitly solve a convex optimization problem over the l1 ball in 2n dimensions using an approximate gradient projection method.
achieving higher magnification in context. the difficulty of accessing information details while preserving context has generated many different focus-in-context techniques. a common limitation of focus-in-context techniques is their ability to work well at high magnification. we present a set of improvements that will make high magnification in context more feasible. we demonstrate new distortion functions that effectively integrate high magnification within its context. finally, we show how lenses can be used on top of other lenses, effectively multiplying their magnification power in the same manner that a magnifying glass applied on top of another causes multiplicative magnification. the combined effect is to change feasible detail-in-context magnification factors from less than 8 to more than 40.
sketchread: a multi-domain sketch recognition engine. we present sketchread, a multi-domain sketch recognition engine capable of recognizing freely hand-drawn diagrammatic sketches. current computer sketch recognition systems are difficult to construct, and either are fragile or accomplish robustness by severely limiting the designer's drawing freedom. our system can be applied to a variety of domains by providing structural descriptions of the shapes in that domain; no training data or programming is necessary. robustness to the ambiguity and uncertainty inherent in complex, freely-drawn sketches is achieved through the use of context. the system uses context to guide the search for possible interpretations and uses a novel form of dynamically constructed bayesian networks to evaluate these interpretations. this process allows the system to recover from low-level recognition errors (e.g., a line misclassified as an arc) that would otherwise result in domain level recognition errors. we evaluated sketch-read on real sketches in two domains--family trees and circuit diagrams--and found that in both domains the use of context to reclassify low-level shapes significantly reduced recognition error over a baseline system that did not reinterpret low-level classifications. we also discuss the system's potential role in sketch based user interfaces.
a framework for unifying presentation space. making effective use of the available display space has long been a fundamental issue in user interface design. we live in a time of rapid advances in available cpu power and memory. however, the common sizes of our computational display spaces have only minimally increased or in some cases, such as hand held devices, actually decreased. in addition, the size and scope of the information spaces we wish to explore are also expanding. representing vast amounts of information on our relatively small screens has become increasingly problematic and has been associated with problems in navigation, interpretation and recognition. user interface research has proposed several differing presentation approaches to address these problems. these methods create displays that vary considerably, visually and algorithmically. we present a unified framework that provides a way of relating seemingly distinct methods, facilitating the inclusion of more than one presentation method in a single interface. furthermore, it supports extrapolation between the presentation methods it describes. of particular interest are the presentation possibilities that exist in the ranges between various distortion presentations, magnified insets and detail-in-context presentations, and between detail-in-context presentations and a full-zooming environment. this unified framework offers a geometric presentation library in which presentation variations are available independently of the mode of graphic representation. the intention is to promote the ease of exploration and experimentation into the use of varied presentation combinations.
tools for expressive text-to-speech markup. this paper describes handicapped accessible text-to-speech markup software developed for poetry and performance. most text-to-speech software allows the user to select a voice, but provides no control over performance parameters such as rate, volume, and pitch. for users with vocal disabilities, the default "computer voice" is often dreaded since it provides no personalization. evolving standards exist for text-to-speech markup (sable, java speech markup language, spoken text markup language), but few tools exist for non-experts to modify documents using these prosody options [1, 5]. furthermore, we could find fewer tools allowing for straightforward live performance using a synthesized voice [3]. thus we created an easy to learn text-to-speech markup tool that requires little training to use.
crossy: a crossing-based drawing application. we introduce crossy, a simple drawing application developed as a benchmark to demonstrate the feasibility of goal-crossing as the basis for a graphical user interface. while crossing was previously identified as a potential substitute for the classic point-and-click interaction, this work is the first to report on the practical aspects of implementing an interface solely based on goal-crossing.
metisse is not a 3d desktop! twenty years after the general adoption of overlapping windows and the desktop metaphor, modern window systems differ mainly in minor details such as window decorations or mouse and keyboard bindings. while a number of innovative window management techniques have been proposed, few of them have been evaluated and fewer have made their way into real systems. we believe that one reason for this is that most of the proposed techniques have been designed using a low fidelity approach and were never made properly available. in this paper, we present metisse, a fully functional window system specifically created to facilitate the design, the implementation and the evaluation of innovative window management techniques. we describe the architecture of the system, some of its implementation details and present several examples that illustrate its potential.
revisiting visual interface programming: creating gui tools for designers and programmers. involving graphic designers in the large-scale development of user interfaces requires tools that provide more graphical flexibility and support efficient software processes. these requirements were analysed and used in the design of the tkz-inc graphical library and the intuikit interface design environment. more flexibility is obtained through a wider palette of visual techniques and support for iterative construction of images, composition and parametric displays. more efficient processes are obtained with the use of the svg standard to import graphics, support for linking graphics and behaviour, and a unifying model-driven architecture. we describe the corresponding features of our tools, and show their use in the development of an application for airports. benefits include a wider access to high quality visual interfaces for specialised applications, and shorter prototyping and development cycles for multidisciplinary teams.
"killer app" of wearable computing: wireless force sensing body protectors for martial arts. ubiquitous and wearable computing both have the goal of pushing the computer into the background, supporting all kinds of human activities. application areas include areas such as everyday environments (e.g. clothing, home, office), promoting new forms of creative learning via physical/virtual objects, and new tools for interactive design. in this paper, we thrust ubiquitous computing into the extremely hostile environment of the sparring ring of a martial art competition. our system uses piezoelectric force sensors that transmit signals wirelessly to enable the detection of when a significant impact has been delivered to a competitor's body. the objective is to support the judges in scoring the sparring matches accurately, while preserving the goal of merging and blending into the background of the activity. the system therefore must take into account of the rules of the game, be responsive in real-time asynchronously, and often cope with untrained operators of the system. we present a pilot study of the finished prototype and detail our experience.
predictive interaction using the delphian desktop. this paper details the design and evaluation of the delphian desktop, a mechanism for online spatial prediction of cursor movements in a windows-icons-menus-pointers (wimp) environment. interaction with wimp-based interfaces often becomes a spatially challenging task when the physical interaction mediators are the common mouse and a high resolution, physically large display screen. these spatial challenges are especially evident in overly crowded windows desktops. the delphian desktop integrates simple yet effective predictive spatial tracking and selection paradigms into ordinary wimp environments in order to simplify and ease pointing tasks. predictions are calculated by tracking cursor movements and estimating spatial intentions using a computationally inexpensive online algorithm based on estimating the movement direction and peak velocity. in testing the delphian desktop effectively shortened pointing time to faraway icons, and reduced the overall physical distance the mouse (and user hand) had to mechanically traverse.
guided gesture support in the paper pda. ordinary paper offers properties of readability, fluidity, flexibility, cost, and portability that current electronic devices are often hard pressed to match. in fact, a lofty goal for many interactive systems is to be "as easy to use as pencil and paper". however, the static nature of paper does not support a number of capabilities, such as search and hyperlinking that an electronic device can provide. the paper pda project explores ways in which hybrid paper electronic interfaces can bring some of the capabilities of the electronic medium to interactions occurring on real paper. key to this effort is the invention of on-paper interaction techniques which retain the flexibility and fluidity of normal pen and paper, but which are structured enough to allow robust interpretation and processing in the digital world. this paper considers the design of a class of simple printed templates that allow users to make common marks in a fluid fashion, and allow additional gestures to be invented by the users to meet their needs, but at the same time encourages marks that are quite easy to recognize.
supporting interaction in augmented reality in the presence of uncertain spatial knowledge. a significant problem encountered when building augmented reality (ar) systems is that all spatial knowledge about the world has uncertainty associated with it. this uncertainty manifests itself as registration errors between the graphics and the physical world, and ambiguity in user interaction. in this paper, we show how estimates of the registration error can be leveraged to support predictable selection in the presence of uncertain 3d knowledge. these ideas are demonstrated in osgar, an extension to openscenegraph with explicit support for uncertainty in the 3d transformations. the osgar runtime propagates this uncertainty throughout the scene graph to compute robust estimates of the probable location of all entities in the system from the user's viewpoint, in real-time. we discuss the implementation of selection in osgar, and the issues that must be addressed when creating interaction techniques in such a system.
tangible nurbs-curve manipulation techniques using graspable handles on a large display. this paper presents tangible interaction techniques for fine-tuning one-to-one scale nurbs curves on a large display for automotive design. we developed a new graspable handle with a transparent groove that allows designers to manipulate virtual curves on a display screen directly. the use of the proposed handle leads naturally to a rich vocabulary of terms describing interaction techniques that reflect existing shape styling methods. a user test raised various issues related to the graspable user interface, two-handed input, and large-display interaction.
low-cost multi-touch sensing through frustrated total internal reflection. this paper describes a simple, inexpensive, and scalable technique for enabling high-resolution multi-touch sensing on rear-projected interactive surfaces based on frustrated total internal reflection. we review previous applications of this phenomenon to sensing, provide implementation details, discuss results from our initial prototype, and outline future directions.
automation and customization of rendered web pages. on the desktop, an application can expect to control its user interface down to the last pixel, but on the world wide web, a content provider has no control over how the client will view the page, once delivered to the browser. this creates an opportunity for end-users who want to automate and customize their web experiences, but the growing complexity of web pages and standards prevents most users from realizing this opportunity. we describe chickenfoot, a programming system embedded in the firefox web browser, which enables end-users to automate, customize, and integrate web applications without examining their source code. one way chickenfoot addresses this goal is a novel technique for identifying page components by keyword pattern matching. we motivate this technique by studying how users name web page components, and present a heuristic keyword matching algorithm that identifies the desired component from the user's name.
citrus: a language and toolkit for simplifying the creation of structured editors for code and data. direct-manipulation editors for structured data are increasingly common. while such editors can greatly simplify the creation of structured data, there are few tools to simplify the creation of the editors themselves. this paper presents citrus, a new programming language and user interface toolkit designed for this purpose. citrus offers language-level support for constraints, restrictions and change notifications on primitive and aggregate data, mechanisms for automatically creating, removing, and reusing views as data changes, a library of widgets, layouts and behaviors for defining interactive views, and two comprehensive interactive editors as an interface to the language and toolkit itself. together, these features support the creation of editors for a large class of data and code.
bridging the gap from theory to practice: the path toward innovation in human-computer interaction. how do we break away from existing tools and techniques in hci and truly innovate in a way that benefits the next generation of computer users? today, too many of our technological designs and inventions are "one off" point designs, not building on or contributing to a theoretical foundation of understanding around human perception, cognition, social behavior and physical movement. of course, these point designs can be successful in and of themselves, so why bother with theory and models? in order to mature as a field in a way that benefits users, it can be argued that we need to work more closely together and with an awareness of multiple disciplines, including not just the computer science and engineering arenas, but also psychology, sociology, and any field of human behavior. of course, this could be a daunting task-how do we know that important improvements in user interface design can be obtained? i will present a series of examples of what i consider to be significant contributions to the field of hci, each based on a multidisciplinarian, theory-driven approach. i hope to challenge the audience to creatively consider ways that their own work could be more theoretically motivated, and what it might take for more of us to move forward in that direction.
cursive: a novel interaction technique for controlling expressive avatar gesture. we are developing an interaction technique for rich nonverbal communication through an avatar. by writing a single letter on a pen tablet device, a user can express their ideas or intentions, non-verbally, using their avatar body. our system solves the difficult problem of controlling the movements of a highly articulated, 3d avatar model using a common input device within the context of an office environment. we believe that writing is a richly expressive and natural means for controlling expressive avatar gesture.
distributed mediation of ambiguous context in aware environments. many context-aware services make the assumption that the context they use is completely accurate. however, in reality, both sensed and interpreted context is often ambiguous. a challenge facing the development of realistic and deployable context-aware services, therefore, is the ability to handle ambiguous context. in this paper, we describe an architecture that supports the building of context-aware services that assume context is ambiguous and allows for mediation of ambiguity by mobile users in aware environments. we illustrate the use of our architecture and evaluate it through three example context-aware services, a word predictor system, an in/out board, and a reminder tool.
focus plus context screens: combining display technology with visualization techniques. computer users working with large visual documents, such as large layouts, blueprints, or maps perform tasks that require them to simultaneously access overview information while working on details. to avoid the need for zooming, users currently have to choose between using a sufficiently large screen or applying appropriate visualization techniques. currently available hi-res "wall-size" screens, however, are cost-intensive, space-intensive, or both. visualization techniques allow the user to more efficiently use the given screen space, but in exchange they either require the user to switch between multiple views or they introduce distortion.in this paper, we present a novel approach to simultaneously display focus and context information. focus plus context screens consist of a hi-res display and a larger low-res display. image content is displayed such that the scaling of the display content is preserved, while its resolution may vary according to which display region it is displayed in. focus plus context screens are applicable to practically all tasks that currently use overviews or fisheye views, but unlike these visualization techniques, focus plus context screens provide a single, non-distorted view. we present a prototype that seamlessly integrates an lcd with a projection screen and demonstrate four applications that we have adapted so far.
the ahi: an audio and haptic interface for contact interactions. we have implemented a computer interface that renders synchronized auditory and haptic stimuli with very low (0.5ms) latency. the audio and haptic interface (ahi) includes a pantograph haptic device that reads position input from a user and renders force output based on this input. we synthesize audio by convolving the force profile generated by user interaction with the impulse response of the virtual surface. auditory and haptic modes are tightly coupled because we produce both stimuli from the same force profile. we have conducted a user study with the ahi to verify that the 0.5ms system latency lies below the perceptual threshold for detecting separation between auditory and haptic contact events. we discuss future applications of the ahi for further perceptual studies and for synthesizing continuous contact interactions in virtual environments.
collapse-to-zoom: viewing web pages on small screen devices by interactively removing irrelevant content. overview visualizations for small-screen web browsers were designed to provide users with visual context and to allow them to rapidly zoom in on tiles of relevant content. given that content in the overview is reduced, however, users are often unable to tell which tiles hold the relevant material, which can force them to adopt a time-consuming hunt-and-peck strategy. collapse-to-zoom addresses this issue by offering an alternative exploration strategy. in addition to allowing users to zoom into relevant areas, collapse-to-zoom allows users to collapse areas deemed irrelevant, such as columns containing menus, archive material, or advertising. collapsing content causes all remaining content to expand in size causing it to reveal more detail, which increases the user's chance of identifying relevant content. collapse-to-zoom navigation is based on a hybrid between a marquee selection tool and a marking menu, called marquee menu. it offers four commands for collapsing content areas at different granularities and to switch to a full-size reading view of what is left of the page.