|Approximate Kinodynamic Planning Using L2-Norm Dynamic Bounds
||In this paper we address the issue of kinodynamic motion planning. Given a point that moves with bounded acceleration and velocity, we wish to find the time-optimal trajectory from a start state to a goal state (a state consists of both a position an...
|Band Ordering in Lossless Compression of Multispectral Images
||In this paper, we consider a model of lossless image
compression in which each band of a multispectral image is coded
using a prediction function involving values from a previously coded
band of the compression, and examine how the ordering of the...
|Continuous Alternation: The Complexity of Pursuit in Continuous Domains
||Complexity theory has used a game-theoretic notion, namely alternation, to great advantage in modeling parallelism and in obtaining lower bounds. The usual definition of alternation requires that transitions be made in discrete steps. The study of di...
|Designing proxies for Stock Market Indices is Computationally Hard
||In this paper, we study the problem of designing proxies (or portfolios) for various stock market indices based on historical data. We use four different methods for computing market indices, all of which are formulae used in actual stock market anal...
|Experiences During a Collegiate Cyber Defense Competition
||The objective of this article is to encourage schools to participate in the Collegiate Cyber Defense Competition (CCDC) and to ease their entry by providing information about the event and describing the experiences of both the student participants a...
|Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input
||In this paper we show that if the input points to the geometric closest pair problem are given with limited precision (each coordinate is specified with O (log n) bits), then we can compute the closest pair in O (n log log...
|On Dynamic Algorithms for Algebraic Problems
||In this paper, we examine the problem of incrementally evaluating algebraic functions. In particular, if f(x1, x2, …, xn) = (y1, y2, …, ym
|On Threshold Circuits and Polynomial Computation
||A Threshold Circuit consists of an acyclic digraph of unbounded fanin, where each node computes
a threshold function or its negation. This paper investigates the computational power of Threshold Circuits.
A surprising relationship is uncovered betw...
|On-Line Difference Maximization
||In this paper we examine problems motivated by on-line financial problems and
stochastic games. In particular, we consider a sequence of entirely arbitrary distinct values arriving
in random order, and must devise strategies for selecting low value...
|Online matching with blocked input
||In this paper, we examine the problem of "blocked online bipartite matching". This problem is similar to the online matching problem except that the vertices arrive in blocks instead of one at a time. Previously studied problems exist as special case...
|Optimal Size Integer Division Circuits
||Division is a fundamental problem for arithmetic and algebraic computation. This
paper describes Boolean circuits (of bounded fan-in) for integer division (finding reciprocals) that
have size O(M(n)) and depth O(logn<...
|ProtoMon: Embedded Monitors for Cryptographic Protocol Intrusion Detection and Prevention
||Intrusion Detection Systems (IDS) are responsible for monitoring and analyzing host or network activity to detect intrusions in order to protect information from unauthorized access or manipulation. There are two main approaches for intrusion detecti...
|Review of Polynomial and Matrix Computations; Volume 1: Fundamental Algorithms by Dario Bini and Victor Pan.
||The past few decades have produced a wealth of interesting and useful work in the area of algorithms for algebraic, symbolic, and numerical computing. Unfortunately, there has been a huge void in the area of books summarizing and bringing together th...
|Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem
||Searching for a goal is a central and extensively studied problem in computer science. In classical searching problems, the cost of a search function is simply the number of queries made to an oracle that knows the position of the goal. In many robot...
|Stable Computation of the Complex Roots of Unity
||In this correspondence, we show that the problem of computing the complex roots of unity is not as simple as it seems at first. In particular, the formulas given in a standard programmer's reference book (Knuth, Seminumerical Algorithms, 1981)...