We give efficient solutions to transportation problems motivated by the following robotics problem.  A robot arm has the task of rearranging m objects between n stations in the plane.  Each object is initially at one of these n stations and needs to be moved to another station.  The robot arm consists of a single link that rotates about a fixed pivot.  The link can extend in and out (like a telescope) so that its length is a variable.  At the end of this “telescoping” link lies a gripper that is capable of grasping any one of the m objects (the gripper cannot be holding mre than one object at the same time).  The robot arm must transport each of the m objects to its destination and come back to where it started.  Since the problem of scheduling the motion of the gripper so as to minimize the total distance traveled in NP-hard, we focus on the problem of minimizing only the total angular motion (rotation of the link about the pivo), or only telescoping motion.  We give algorithms for two different modes of operation: (i) No-drops. No object can be dropped before its destination is reached.  (ii) With-drops.  Any objectcan be dropped at any number of intermediate points.  Our algorithm for case (i) runs in O(m + n log n)  time for angular motion and in O(m + n alpha(n)) time for telescoping motion.  Our algorithm for case (ii) runs in O(m + n) time for angular motion and with the same time bound for telescoping motion.  The most interesting problem turns out to be that of minimizing angular motion for the with-drops mode of operation.

Techniques for parallel divide-and-conquer are presented, resulting in improved parallel algorithms for a number of problems.  The problems for which improved algorithms are given include segment intersection detection, trapezoidal decomposition, and planar point location.  Efficient parallel algorithms are algo given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point.  All of the algorithms presented run in O (log n) time with either a linear or a sublinear number of processors in the CREW PRAM model.

his paper describes how anonymity is achieved in GNUnet, a framework for anonymous distributed and secure networking.

We describe GAP, a simple protocol for anonymous transfer of data which can achieve better anonymity guarantees than traditional indirection schemes and is additionally more efficient. While the building blocks of our technique are similar to previous work, we offer a new perspective on how to perceive and measure anonymity. Based on this new perspective we are able to modify the protocol to allow individual nodes to trade anonymity for efficiency.

Dot-products form the basis of various applications ranging from scientific computations to commercial applications in data mining and transaction processing. Typical scientific computations utilizing sparse iterative solvers use repeated matrix-vector products. These can be viewed as dot-products of sparse vectors. In database applications, dot-products take the form of counting operations. With widespread use of clustered and distributed platforms, these operations are increasingly being performed across networked hosts. Traditional APIs for messaging are susceptible to sniffing, and the data being transferred between hosts is often enough to compromise the entire computation. For example, in a domain decomposition based sparse solver, the entire solution can often be reconstructed easily from boundary values that are communicated on the net. In yet other applications, dot-products may be performed across two hosts that do not want to disclose their vectors, yet, they need to compute the dot-product. In each of these cases, there is a need for secure and anonymous dot-product protocols. Due to the large computational requirements of underlying applications, it is highly desirable that secure protocols add minimal overhead to the original algorithm. Finally, by its very nature, dot-products leak limited amounts of information—one of the parties can detect an entry of the other party’s vector by simply probing it with a vector with a 1 in a particular location and zeros elsewhere. Given all of these constraints, traditional cryptographic protocols are generally unsuitable due to their significant computational and communication overheads. In this paper, we present an extremely efficient and sufficiently secure protocol for computing the dot-product of two vectors using linear algebraic techniques. Using analytical as well as experimental results, we demonstrate superior performance in terms of computational overhead, numerical stability, and security. We show that the overhead of a two-party dot-product computation using MPI as the messaging API across two high-end workstations connected via a Gigabit ethernet approaches multiple 4.69 over an un-secured dot-product. We also show that the average relative error in dot-products across a large number of random (normalized) vectors was roughly $4.5 \times 10^{-9}$.

The Generalized Temporal Role Based Access Control (GTRBAC) model introduces a large set of temporal constraint expressions that facilitates the specification of a comprehensive access control policy. However, the issue of its expressiveness has not been investigated earlier. In this paper, we present an exhaustive analysis of the expressiveness of the constructs provided by GTRBAC and prove that the set of constraints is not minimal by showing that there is a subset of GTRBAC constraints that is sufficient to express all access constraints that can be expressed using the full set. We formally present the minimality result for the GTRBAC constraint set and argue that, although the complete set of constraints in GTRBAC is not minimal, having such an extensive set is advantageous from the perspective of user convenience and the lower complexity of constraint representation. Based on our analysis, we present a set of design guidelines that can considerably enhance security management.

We study the verification of data integrity during peer-to-peer video streaming sessions. Challenges include the timing constraint of streaming, as well as the untrustworthiness of peers. We show the inadequacy of existing authentication protocols and propose a more efficient protocol which utilizes message digest and probabilistic verification. We then propose One Time Digest Protocol (OTDP) and Tree-based Forward Digest Protocol (TFDP) to further reduce the communication overhead. Finally, a comprehensive comparison is presented comparing the performance of existing protocols and our protocols, with respect to overhead, security assurance level, and packet loss tolerance.

Two main results in the area of information hiding in natural language text are presented. A semantically-based scheme dramatically improves the information-hiding capacity of any text through two techniques: (i) modifying the granularity of meaning of individual sentences, whereas our own previous scheme kept the granularity fixed, and (ii) halving the number of sentences affected by the watermark. No longer a

The public part of the vulnerability management cycle, publication-notification-patch is of interest to system administrators.  We describe the architecture of the vulnerability notification Cassandra system (https://cassandra.cerias.purdue.edu).  The timeliness of the notifications was evaluated by using the publication dates of CERT Incident Notes as approximations for the dates when vulnerabilities are widely exploited.  We found that notifications sent by Cassandra in 2001 (until November) provided a forewarning of 60 days on average.  However, these notifications were not always timely.  An analysis of the vulnerability information flow identified sources of undesirable delays.  A new Cassandra service, CVE Change Logs, was created to report daily changes to the CVE and bypass some sources of delays.  Other efforts by MITRE mitigated other sources of delays and consolidated changes on their web site.  An unexpected finding of this study is that the timing and the number of vulnerabilities involved in the method of disclosing vulnerabilities can contribute to notification delays due to the limited processing capacity of intermediates and the finite patching capability of system administrators.  We conclude that the large batch processing of vulnerabilities contributes to notification and patching delays and is undesirable.  For the same reasons, randomly timed disclosures of vulnerabilities should be undesirable, suggesting the creation of a concerted mechanism for the disclosure of vulnerabilities.