6093420
Secure Biometric Authentication for Weak Computational Devices
This paper presents computationally “lightweight” schemes for performing biometric authentication that carry out the comparison stage without revealing any information that can later be used to impersonate the user (or reveal personal biometric information). Unlike some previous computationally expensive schemes — which make use of slower cryptographic primitives — this paper presents methods that are particularly suited to financial institutions that authenticate users with biometric smartcards, sensors, and other computationally limited devices. In our schemes, the client and server need only perform cryptographic hash computations on the feature vectors, and do not perform any expensive digital signatures or public-key encryption operations. In fact, the schemes we present have properties that make them appealing even in a framework of powerful devices capable of public-key signatures and encryptions. Our schemes make it computationally infeasible for an attacker to impersonate a user even if the attacker completely compromises the information stored at the server, including all the server’s secret keys. Likewise, our schemes make it computationally infeasible for an attacker to impersonate a user even if the attacker completely compromises the information stored at the client device (but not the biometric itself, which is assumed to remain attached to the user and is not stored on the client device in any form).
8676248
Authenticated Dictionaries for Fresh Attribute Credentials
We describe several schemes for efficiently populating an authenticated dictionary with fresh credentials. The thrust of this effort is directed at allowing for many data authors, called sources, to collectively publish information to a common repository, which is then distributed throughout a network to allow for authenticated queries on this information. Authors are assured of their contributions being added to the repository based on cryptographic receipts that the repository returns after performing the updates sent by an author. While our motivation here is the dissemination of credential status data from multiple credential issuers, applications of this technology also include time stamping of documents, document version integrity control, and multiple-CA certificate revocation management, to name just a few.
14677263
Teaching the analysis of algorithms with visual proofs
We describe an approach for visually teaching important proofs in the Junior-Senior level course on the design and analysis of data structures and algorithms (CS7/DS&amp;A). The main idea of this educational paradigm is to justify important claims about data structures and algorithms by using pictures that visualize proofs so clearly that the pictures can qualify as proofs themselves. The advantage of using this approach for DS&amp;A is that it augments or even replaces inductive arguments that many students find difficult. Moreover, this paradigm communicates important algorithmic facts in a compelling way for students who are more visually-oriented. We illustrate this technique by giving examples of visual proofs of several key concepts in DS&amp;A.
1270229
Fast Randomized Parallel Methods for Planar Convex Hull Construction
Abstract We present a number of efficient parallel algorithms for constructing 2-dimensional convex hulls on a randomized CRCW PRAM. Specifically, we show how to build the convex hull of n presorted points in the plane in O(1) time using O(n log n) work, with n-exponential probability, or, alternately, in O ( log ∗ n) time using O(n) work, with n-exponential probability. We also show how to find the convex hull of n unsorted planar points in O(log n) time using O(n log h) work, with n-exponential probability, where h is the number of edges in the convex hull (h is O(n), but can be as small as O(1)). Our algorithm for unsorted inputs depends on the use of new in-place procedures, that is, procedures that are defined on a subset of elements in the input and that work without reordering the input. In order to achieve our n-exponential confidence bounds we use a new parallel technique called failure sweeping.
14228028
Efficient piecewise-linear function approximation using the uniform metric: (preliminary version)
We give an <italic>O</italic>(<italic>n</italic>log<italic>n</italic>)-time method for finding a best <italic>k</italic>-link piecewise-linear function approximating an <italic>n</italic>-point planar data set using the well-known uniform metric to measure the error, ε≥0, of the approximation. Our method is based upon new characterizations of such functions, which we exploit to design an efficient algorithm using a plane sweep in “ε space” followed by several applications of the parametric searching technique. The previous best running time for this problem was <italic>O</italic>(<italic>n</italic><supscrpt>2</supscrpt>).
15210615
An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction
In the Constructive Solid Geometry (CSG) representation a geometric object is described as the hierarchical combination of a number of primitive shapes using the operations union, intersection, subtraction, and exclusive-union. This hierarchical description defines an expression tree, T, called the CSG tree, with leaves associated with primitive shapes, internal nodes associated with operations, and whose "value" is the geometric object. Evaluation of CSG trees is an important computation that arises in many rendering and analysis problems for geometric models, with ray shooting (also known as "ray casting") being one of the most important. Given any CSG tree T, which may be unbalanced, we show how to convert T into a functionally-equivalent binary tree, D, that is balanced. We demonstrate the utility of this conversion by showing how it can be used to improve the worst-case running time for ray shooting against a CSG model from O(n2) to O(n log n), which is optimal. In addition, the practicality of our method has been demonstrated in experimental benchmarking tests using the BRL-CAD package.
29722627
A theory of satisficing decisions and control
The existence of an optimal control policy and the techniques for finding it are grounded fundamentally in a global perspective. These techniques can be of limited value when the global behaviour of the system is difficult to characterize, as it may be when the system is nonlinear, when the input is constrained, or when only partial information is available regarding system dynamics or the environment. Satisficing control theory is an alternative approach that is compatible with the limited rationality associated with such systems. This theory is extended by the introduction of the notion of strong satisficing to provide a systematic procedure for the design of satisficing controls. The power of the satisficing approach is illustrated by applications to representative control problems.
11363478
Learning To Cooperate in a Social Dilemma: A Satisficing Approach to Bargaining
Learning in many multi-agent settings is inherently repeated play. This calls into question the naive application of single play Nash equilibria in multi-agent learning and suggests, instead, the application of give-and-take principles of bargaining. We modify and analyze a satisficing algorithm based on (Karandikar et al., 1998) that is compatible with the bargaining perspective. This algorithm is a form of relaxation search that converges to a satisficing equilibrium without knowledge of game payoffs or other agents' actions. We then develop an M action, N player social dilemma that encodes the key elements of the Prisoner's Dilemma. This game is instructive because it characterizes social dilemmas with more than two agents and more than two choices. We show how several different multi-agent learning algorithms behave in this social dilemma, and demonstrate that the satisficing algorithm converges, with high probability, to a Pareto efficient solution in self play and to the single play Nash equilibrium against selfish agents. Finally, we present theoretical results that characterize the behavior of the algorithm.
1846400
Common metrics for human-robot interaction
This paper describes an effort to identify common metrics for task-oriented human-robot interaction (HRI). We begin by discussing the need for a toolkit of HRI metrics. We then describe the framework of our work and identify important biasing factors that must be taken into consideration. Finally, we present suggested common metrics for standardization and a case study. Preparation of a larger, more detailed toolkit is in progress.
12614052
Learning haptic feedback for guiding driver behavior
Information about the driving state can be conveyed to automobile drivers through force feedback signals sent via the pedals and steering wheel. Because the set of possible haptic signals and driver responses is huge, it is desirable to automatically learn which signals are most useful to drivers. Thus, it is instructive to explore how machine learning techniques can be used as a step in the design of a haptic interface system. In this paper, we present a learning algorithm that learns useful haptic feedback and apply the algorithm to learning feedback for automobile drivers. We present evidence to show that the algorithm is sensitive enough to learn useful feedback under some circumstances, but that its scope may be limited by people's ability to act as admittance controllers.
44773632
Satisficing Games
Optimization is a mathematical sophistication of the common sense view that decision makers ought to do the best they can, and leads to well known solution concepts for mathematical games. For multi-agent systems in naturalistic settings, however, uncertainty and complexity may subordinate optimal performance to the more moderate goals of functionality and robustness. Moderation is another common sense idea that can be made mathematically precise by defining a notion of comparative rationality, leading to a theory of satisficing games. Preferences in an m-agent satisficing game are characterized by a 2m-dimensional interdependence function, from which the joint m-dimensional gains and losses of the agent system can be derived and compared to determine the set of jointly satisficing decisions. This paradigm permits decision makers in the presence of uncertainty to consider multiple sets of possible actions and make decisions that are both robust and functional. Two well-known games, Prisoner's Dilemma and Battle of the Sexes, are analyzed from this, point of view.