Multilayer perceptrons are now promising tools in the connectionist approach for classification problems and have already been successfully tested on speech recognition problems. However, the sequential nature of the speech signal remains difficult to handle in that kind of machine.
In this paper, a discriminant hidden Markov model is defined and it is shown how a particular multilayer perceptron with contextual and extra feedback input units can be considered as a general form of such Markov models. Relations with other recurrent networks commonly used in speech recognition are also pointed out. ----- File: 1988/tr-88-009 Designing Computers to Check Their Work Manuel Blum tr-88-009 November 1988 Students, engineers, programmers...are taught to check their work. Computer programs are not. There are several reasons for this:
1. Computer hardware almost never makes errors -- but that fails to recognize that programmers unfortunately do!
2. Programs are hard enough to write without having to also write program checkers for them -- but that is the price of increased confidence!
3. There is no clear notion what constitutes a good checker. Indeed, the same students and engineers who are cautioned to check their work are rarely informed what it is that makes for a good procedure to do so -- but that is just the sort of problem that computer scientists should be able to solve!
In the view of the author, the lack of correctness checks in programs is an oversight. Programs have bugs that could perfectly well be caught by such checks. This paper urges that programs be written to check their work, and outlines a promising and rigorous approach to the study of this fascinating new area. ----- File: 1988/tr-88-010 Knowledge-Intensive Recruitment Learning Joachim Diederich tr-88-010 November 1988 The model described in this paper is a knowledge-intensive connectionist learning system which uses a built-in knowledge representation module for inferencing, and this reasoning capability in turn is used for knowledge-intensive learning. On the connectionist network level, the central process is the recruitment of new units and the assembly of units to represent new conceptual information. Free, uncommitted subnetworks are connected to the built-in knowledge network during learning. The goal of knowledge-intensive connectionist learning is to improve the operationality of the knowledge representation: mediated inferences, i.e., complex inferences which require several inference steps, are transformed into immediate inferences; in other words, recognition is based on the immediate excitation from features directly associated with a concept. ----- File: 1988/tr-88-011 Time, Space and Form in Vision Jerome A. Feldman tr-88-011 December 1988 The prodigious spatial capabilities of the primate visual system are even more remarkable when temporal considerations are taken into account. Recent advances in neurophysiology, psychophysics and computer vision provide significant constraints on how the system could work. This paper presents a fairly detailed connectionist computational model of how the perception and recognition of objects is carried out by primate brains. The model is claimed to be functionally adequate and to satisfy all the constraints established by the various disciplines. One key notion introduced is a multi-input, multi-output network for inverting spatio-temporal cues. The central construct in intermediate level motion vision is taken to be the trajectory and these are used in recognition of dynamic situations called scenarios. The entire development is an extension of the author's 1985 Four Frames model, which required relatively little modification to accommodate temporal change (eventually). ----- File: 1988/tr-88-012 On a Theory of Computation and Complexity Over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines Lenore Blum, Mike Shub, and Steve Smale tr-88-012 December 1988 We present a model for computation over the reals or an arbitrary (ordered) ring R. In this general setting, we obtain universal machines, partial recursive functions, as well as NP complete problems. While our theory reflects the classical theory over Z (e.g., the computable functions are the recursive functions) it also reflects the special mathematical character of the underlying ring R (e.g., complements of Julia sets provide natural examples of R.E. undecidable sets over the reals) and provides a natural setting for studying foundational issues concerning algorithms in numerical analysis. ----- File: 1988/tr-88-013 Program Correctness Checking and the Design of Programs That Check Their Work Manuel Blum and Sampath Kannan tr-88-013 December 1988 A program correctness checker is an algorithm for checking the output of a computation. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class P of problems solvable in polynomial time. It also applies methods of modern cryptography, especially the idea of a probabilistic interactive proof, to the design of program checkers for group theoretic computations. Finally it characterizes the problems that can be checked. ----- File: 1989/tr-89-001 Guaranteeing Performance for Real-Time Communication in Wide-Area Networks Domenico Ferrari tr-89-001 January 1989 The increasing importance of distributed multimedia applications and the emergence of user interfaces based on digital audio and digital video will soon require that computer communication networks offer real-time services. This paper argues that the feasibility for providing performance guarantees in a wide-area network should be investigated, and describes a possible approach. We present a model of the network to be studied, and discuss its generality, as well as the presumable limits to its validity in the future. We also give a careful formulation of the problem, including a precise definition of the guarantees to be provided and a provably correct scheme for the establishment of real-time connections with deterministic, statistical, and best-effort delay bounds. ----- File: 1989/tr-89-002 Pseudo-Random Number Generator From ANY One-Way Function Russell Impagliazzo and Mike Luby tr-89-002 February 1989 We construct a pseudo-random number generator from ANY one-way function. Previous results show how to construct pseudo-random number generators from one-way functions that have special properties (Blum and Micali [BM], Yao [Y], Levin [L1], [Goldreich, Krawczyk and Luby [GKL]). We use techniques borrowed from the theory of slightly-random sources (Santha and Vazirani [SV], Vazirani and Vazirani [VV], Vazirani [V], Chor and Goldreich [CG]) and from the theory of universal hash functions (Carter and Wegman [CW]).
We also introduce a weaker kind of one-way function, that we call an informationally one-way function. For an informationally one-way function f, given y = f(x) for a randomly chosen x, it is hard to generate uniformly a random preimage of y. We show that the existence of an informationally one-way function yields a one-way function in the usual sense, and hence a pseudo-random number generator. These results can be combined to show that the following are equivalent: (1) private key encryption; (2) bit commitment; (3) pseudo-random number generators; (4) one-way functions; (5) informationally one-way functions. ----- File: 1989/tr-89-003 Parallel Search for Maximal Independence Given Minimal Dependence Paul Beame and Michael Luby tr-89-003 February 1989 We consider the problem of finding a maximal independent set fast in parallel when the independence system is presented as an explicit list of minimal dependent sets. Karp and Wigderson [KW] were the first to find an NC algorithm for the special case when the size of each minimal dependent set is at most two, and subsequent work by Luby [Lu1], by Alon, Babai and Itai[ABI] and Goldberg and Spencer [GS] have introduced substantially better algorithms for this case. On the other hand, no previous work on this problem extends even to the case when the size of each minimal dependent set is at most a constant, and we conjecture that this algorithm is a randomized NC algorithm for the general case. ----- File: 1989/tr-89-004 Towards a Theory of Average Case Complexity Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby tr-89-004 February 1989 This paper takes the next step in developing the theory of average case complexity, a study initiated by Levin. Previous works have focused on the existence of complete problems [Le,Gu,VL]. We widen the scope to other basic questions in computational complexity. For the first time in the context of average case complexity, we show the equivalence of search and decision problems, analyze the structure of NP under P reductions, and relate the NP versus average-P to non-deterministic versus deterministic (worst case) exponential time. We also present definitions and basic theorems regarding other complexity classes, such as average log-space. ----- File: 1989/tr-89-005 A Study of Password Security Michael Luby, and Charles Rackoff tr-89-005 February 1989 We prove relationships between the security of a function generator when used in an encryption scheme and the security of a function generator when used in a UNIX-like password scheme. ----- File: 1989/tr-89-006 Fault-Tolerant Routing in Hypercube Multicomputers Using Depth-First Search Ming-Syan Chen, and Kang G. Shin tr-89-006 February 1989 A fault-tolerant routing scheme for hypercube multicomputers is developed using the depth-first search. The routing scheme requires a node to know only the condition (faulty or not) of its own links, and adds information on the components traversed to each message as it is routed toward the destination node.
Performance of the proposed routing scheme is rigorously analyzed. We derive an exact expression for the probability of routing messages via optimal paths (of length identical to the Hamming distance between the corresponding pair of nodes) from the source node to an obstructed node, the first node on a path determined by the above routing scheme from which no optimal path to the destination exists. Moreover, bounds for this probability are derived in closed form. The probability of routing messages via optimal paths between the source and destination can be obtained from this expression by replacing the obstructed node with the destination node. The lengths of paths obtained from this scheme are analyzed, and the scheme, despite its simplicity, is shown to be able to route messages via optimal paths with a very high probability.
Due to the absence of information at each node on components other than its own links, the actual paths chosen by the above scheme could sometimes be longer than the desired. To alleviate this deficiency, we also present a simple modification to the above routing scheme in which every node is made aware of not only the condition of its own links but also that of links one hop away from the node. The improvement of routing efficiency with this additional information at each node is analyzed. ----- File: 1989/tr-89-007 A Linear-Algorithm for Enumerating Perfect Matchings in Skew Bipartite Graphs Paul Dagum tr-89-007 February 1989 Let G = (U,V,E) be a bipartite graph with |E| = m, U union V = {v(subscript 1),..., v(subscript 2n)} and with the bipartition U consisting of all odd indexed vertices and V consisting of all even indexed vertices. An edge in G is always assumed to be oriented towards the endpoint with the larger index. We refer to the up (resp. down) edges of G as the edges which are oriented from an even (resp. odd) indexed vertex. If all the up edges are nested among themselves and among the down edges we say G is a skew graph. The main result of this paper is to give an O(m) algorithm to enumerate perfect matchings in skew graphs. Applications to outerplanar graphs and some problems in chemistry are given. ----- File: 1989/tr-89-008 Spreading Activation and Connectionist Models for Natural Language Processing Joachim Diederich tr-89-008 February 1989 High level cognitive tasks performed by an artificial neural network require both knowledge over a domain and inferencing abilities. To operate in a complex, natural environment neural networks must have robust, reliable and massively parallel inference mechanisms. This paper describes various spreading activation and connectionist mechanisms for inferencing as part of natural language processing systems, including possible techniques to enrich these systems by machine learning. In particular models which attack one or more important problems such as variable binding, knowledge-intensive learning, avoidance of cross-talk and false classifications are selected for this overview. ----- File: 1989/tr-89-009 Constructive Omega(t(superscript 1.26)) Lower Bound for the Ramsey Number R (3,t) Richard Cleve, and Paul Dagum tr-89-009 February 1989 We present a feasibly constructive proof that R(3,t) > 5((t-1)/2)(superscript (log4/log3)) Element Omega (t(superscript 1.26)). This is, as far as we know, the first constructive superlinear lower bound for R(3,t). Also, our result yields the first feasible method for constructing triangle-free k-chromatic graphs that are polynomial-size in k. ----- File: 1989/tr-89-010 Conceptual Hierarchies in Classical and Connectionist Architecture Alfred Kobsa tr-89-010 February 1989 Representation systems for conceptual hierarchies have been used in the field of Artificial Intelligence for nearly two decades. They are based on symbolic representation structures and sequential processes operating upon these structures. Recently, a number of network structures have been developed in the field of Connectionism which are also claimed to be able to represent conceptual hierarchies. Processes in these networks operate in a parallel way and largely without a global control mechanism. This paper investigates the expressive power, interpretation, and inferential capabilities of these networks as compared to traditional representations, of concept hierarchies in particular to KL-ONE, a standard representation language for conceptual hierarchies in the field of natural-language processing. Although the capabilities of current connectionist hierarchies fall short of traditional representations, three inference processes will be described which can be very easily and elegantly realized in a connectionist architecture whilst they are hard and cumbersome to implement in traditional knowledge representation systems. ----- File: 1989/tr-89-011 Preemptive Ensemble Motion Planning on a Tree Greg N. Frederickson, and D. J. Guan tr-89-011 March 1989 Consider the problem of transporting a set of objects between the vertices of a tree by a vehicle that travels along the edges of the tree. The vehicle can carry only one object at a time, and it starts and finishes at the same vertex of the tree. It is shown that if objects can be dropped at intermediate vertices along its route and picked up later, then the problem can be solved in polynomial time. Two efficient algorithms are presented for this problem. The first algorithm runs in O(k + qn) time, where n is the number of vertices in the tree, k is the number of objects to be moved, and q is less than or equal to min{k,n} is the number of nontrivial connected components in a related directed graph. The second algorithm runs in O(k + nlogn) time.
* Has since been revised by author. Contact him via "gnf at cs.purdue.edu" for a current copy. ----- File: 1989/tr-89-012 Nonpreemptive Ensemble Motion Planning on a Tree Greg N. Frederickson, and D. J. Guan tr-89-012 March 1989 Consider the problem of transporting a set of objects between the vertices of a tree by a vehicle that travels along the edges of the tree. The vehicle can carry only one object at a time, and it starts and finishes at the same vertex of the tree. It is shown that if each object must be carried directly from its initial vertex to its destination, then finding a minimum cost transportation is NP-hard. Several fast approximation algorithms are presented for this problem. The fastest runs in O(k + n) time and generates a transportation of cost at most 3/2 times the cost of an optimal transportation, where n is the number of vertices in the tree, k is the number of objects to be moved. Another runs in O(k + nlogbeta(n,q)) time, and generates a transportation of cost at most 5/4 times the cost of an optimal transportation, where q is less than or equal to min{k,n} is the number of nontrivial connected components in a related directed graph.
* Has since been revised by author. Contact him via "gnf at cs.purdue.edu" for a current copy. ----- File: 1989/tr-89-013 The Establishment of the International Computer Science Institute in Berkeley, California: Venturing with Norbert Ron Kay tr-89-013 March 1989 This is an account of the events and considerations which led to the establishment of the International Computer Science Institute in Berkeley, California. The initiative for this undertaking came from Norbert Szyperski, as Managing Director of the German National Center for Computer Science (GMD). He also took the lead in assuring support on the part of German industry and government. Copies of the most important source documents are included as an appendix to this account. ----- File: 1989/tr-89-014 Subtree Isomorphism is in Random NC Philip Gibbons, Richard M. Karp, and Gary L. Miller and Danny Soroker tr-89-014 March 1989 Given two trees, a guest tree G and a host tree H, the subtree isomorphism problem is to determine whether there is a subgraph of H that is isomorphic to G. We present a randomized parallel algorithm for finding such an isomorphism, if it exists. The algorithm runs in time O(log(superscript 3)n) on a CREW PRAM, where n is the number of nodes in H. The number of processors required by the algorithm is polynomial in n. Randomization is used (solely) to solve each of a series of bipartite matching problems during the course of the algorithm. We demonstrate the close connection between the two problems by presenting a log-space reduction from bipartite perfect matching to subtree isomorphism. Finally, we present some techniques to reduce the number of processors used by the algorithm. ----- File: 1989/tr-89-015 Planar Graph Decomposition and All Pairs Shortest Paths Greg N. Frederickson tr-89-015 March 1989 An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but not negative cycles. The algorithm runs in O(pn) time, where n is the number of vertices in G, and p is the minimum cardinality of a subset of the faces that cover all vertices, taken over all planar embeddings of G. The algorithm is based on a decomposition of the graph into O(pn) outerplanar subgraphs satisfying certain separator properties. Linear-time algorithms are presented for various subproblems including that of finding an appropriate embedding of G and a corresponding face-on-vertex covering of cardinality O(p), and of generating all pairs shortest path information in a directed outerplanar graph.
* Has since been revised by author. Contact him via "gnf at cs.purdue.edu" for a current copy. ----- File: 1989/tr-89-016 Explanation and Connectionist Systems Joachim Diederich tr-89-016 April 1989 Explanation is an important function in symbolic artificial intelligence (AI). For example, explanation is used in machine learning and for the interpretation of prediction failures in case-based reasoning. Furthermore, the explanation of results of a reasoning process to a user who is not a domain expert must be a component of any inference system. Experience with expert systems has shown that the ability to generate explanations is absolutely crucial for the user-acceptance of AI systems (Davis, Buchanan & Shortliffe 1977). In contrast to symbolic systems, neural networks have no explicit, declarative knowledge representation and therefore have considerable difficulties in generating explanation structures. In neural networks, knowledge is encoded in numeric parameters (weights) and distributed all over the system.
It is the intention of this paper to discuss the ability of connectionist systems to generate explanations. It will be shown that connectionist systems benefit from the explicit encoding of relations and the use of highly structured networks in order to realize explanation and explanation components. Furthermore, structured connectionist systems using spreading activation have the advantage that any intermediate state in processing is semantically meaningful and can be used for explanation. The paper describes several successful applications of explanation components in connectionist systems which use highly structured networks, and discusses possible future realizations of explanation in neural networks. ----- File: 1989/tr-89-017 Generalization and Parameter Estimation in Feedforward Nets: Some Experiments N. Morgan and H. Bourlard tr-89-017 April 1989 We have begun an empirical study of the relation of the number of parameters (weights) in a feedforward net to generalization performance. Two experiments are reported. In one, we use simulated data sets with well-controlled parameters, such as the signal-to-noise ratio of continuous-valued data. In the second, we train the network on vector-quantized mel cepstra from real speech samples. In each case, we use back-propagation to train the feedforward net to discriminate in a multiple class pattern classification problem. We report the results of these studies, and show the application of cross-validation techniques to prevent overfitting. ----- File: 1989/tr-89-018 A Parallel Algorithm for Maximum Matching in Planar Graphs Marek Karpinski, Elias Dahlhaus, and Andrzej Lingas tr-89-018 April 1989 We present a new parallel algorithm for finding a maximum (cardinality) matching in a planar bipartite graph G. Our algorithm is processor-time product efficient if the size l of a maximum matching of G is large. It runs in time O((n/2-l + (the square root of n))log (superscript 7)n) on a CRCW PRAM with O(n(superscript 1.5)log (superscript 3)n) processors. ----- File: 1989/tr-89-019 A More Practical PRAM Model Phillip B. Gibbons tr-89-019 April 1989 This paper introduces the Asynchronous PRAM model of computation, a variant of the PRAM in which the processors run asynchronously and there is an explicit charge for synchronization. A family of Asynchronous PRAM's are defined, varying in the types of synchronization steps permitted and the costs for accessing the shared memory. Algorithms, lower bounds, and simulation results are presented for an intersting member of the family. ----- File: 1989/tr-89-020 Multiple Network Embeddings into Hypercubes Ajay Gupta and Susanne E. Hambrusch tr-89-020 April 1989 In this paper we study the problem of how to efficiently embed r interconnection networks G(subscript 0),...G(subscript r-1), r is less than or equal to k, into a k-dimensional hypercube H so that every node of the hypercube is assigned at most r nodes all of which belong to different G(subscript i)s. When each G(subscript i) is a complete binary tree or a leap tree of 2(superscript k)-1 nodes, we describe an embedding achieving a dilation of 2 and a load of 5 and 6, respectively. For the cases when each G(subscript i) is a linear array of a 2-dimensional mesh of 2(superscript k) nodes, we describe embeddings that achieve a dilation of 1 and an optimal load of 2 and 4, respectively. Using these embeddings, we also show that r(subscript 1) complete binary trees, r(subscript 2) leap trees, r(subscript 3) linear arrays, and r(subscript 4) meshes can simultaneously be embedded into H with constant dilation and load, (4 over sum over i=1) (r(subscript i)) is less than or equal to k. ----- File: 1989/tr-89-021 Learning Read-Once Formulas Using Membership Queries Lisa Hellerstein and Marek Karpinski tr-89-021 April 1989 In this paper we examine the problem of exact learning (and inferring) of read-once formulas (also called mu-formulas or boolean trees) using membership queries. The power of membership queries in learning various classes of formulas was studied by Angluin [A]. Valiant proved that, using three powerful oracles, read-once formulas can be learned in polynomial time [V]. Pitt and Valiant proved that if RP is not equal to NP, read-once formulas cannot be learned by example in polynomial time [PV,KLPV]. We show that given explicitly a boolean formula f defining a read-once function, if RP is not equal to NP, then there does not exist a polynomial time algorithm for inferring an equivalent read-once formula. An easy argument on the cardinality of the set of all (read-once) 1-term DNF formulas implies an exponential lower bound on the number of membership queries necessary to learn read-once formulas. Angluin showed that it takes time 2(superscript Omega(n)) to learn monotone n-term DNf formulas using membership queries [A]. We prove that, surprisingly, it is possible to learn monotone read-once formulas in polynomial time using membership queries. We present an algorithm that runs in time O(n(superscript 3)) and makes O(n(superscript 3)) queries to the oracle. It is based on a combinatorial characterization of read-once formulas developed by Karchmer et. al. [KLNSW]. We also use the combinatorial characterization to prove two other results. We show that read-once formulas can be learned in polynomial time using only one of the three oracles used in Valiant's polynomial time algorithm. In addition, we show that given an arbitrary boolean formula f, the problem of deciding whether f defines a read-once function is complete in the class D(superscript P) under randomized NC(superscript 1)-reductions. The main results of this paper can also be interpreted in terms of efficient input oracle algorithms for boolean function interpolation (cf. [KUW],[GKS]. ----- File: 1989/tr-89-022 Real-Time Communication in Packet-Switching Wide-Area Networks Domenico Ferrari tr-89-022 May 1989 The increasing importance of distributed multimedia applications and the emergence of user interfaces based on digital audio and digital video will soon require that computer communication networks offer real-time services. This paper argues that the feasibility of providing performance guarantees in a packet-switching wide-area network should be investigated, and describes a possible approach. We present a model of the network to be studied, and discuss its generality, as well as the presumable limits to its validity in the future. We also formulate the problem, give a definition of the guarantees to be provided, and describe a correct scheme for the establishment of real-time connections with deterministic, statistical, and best-effort delay bounds. ----- File: 1989/tr-89-023 Approximating the Permanent of Graphs with Large Factors Paul Dagum and Michael Luby tr-89-023 April 1989 Let G = (U,V,E) be a bipartite graph with |U|=|V|=n. The factor size of G,f, is the maximum number of edge disjoint perfect matchings in G. We characterize the complexity of counting the number of perfect matchings in classes of graphs parameterized by factor size. We describe the simple algorithm, which is an approximation algorithm for the permanent that is a natural simplification of the algorithm suggested in [Broder 86] and analyzed in [Jerrum, Sinclair 88 a,b]. A combinatorial lemma is used to prove that the simple algorithm runs in time n(superscript O(n/f)). Thus (1) for all constants alpha > 0, the simple algorithm runs in polynomial time for graphs with factor size at least alpha(n); (2) for some constant c, the simple algorithm is the fastest known approximation for graphs with factor size at least c log n. (Compare with the approximation algorithms described in [Karmarkar, et. al. 88).
We prove the following complementary hardness results. For functions f such that 3 is less than or equal to f(n) is less than or equal to n-3, the exact counting problem for f(n)-regular bipartite graphs is #P-complete. For any epsilon > 0, for any function f such that 3 is less than or equal to f(n) is less than or equal to n (superscript 1-epsilon), approximate counting for f(n)-regular bipartite graphs is as hard as approximate counting for all bipartite graphs. ----- File: 1989/tr-89-024 An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph Elias Dahlhaus and Marek Karpinski tr-89-024 May 1989 We design the first efficient parallel algorithm for computing Minimal Elimination Ordering (MEO) of an arbitrary graph.
The algorithm works in O(log(superscript 3)n) parallel time and O(nm) processors on a CRCW PRAM, for an n-vertex, m-edge graph, and is optimal up to polylogarithmic factor with respect to the best sequential algorithm of Rose, Tarjan and Lueker.
The MEO Problem for arbitrary graphs arises in a number of combinatorial optimization problems, as well as in database applications, scheduling problems, and the sparse Gaussian elimination of symmetric matrices. It was believed before to be inherently sequential and strongly resisting sublinear parallel time (sublinear sequential storage) algorithms.
As an application, this paper gives the first efficient parallel solutions to the problem of Minimal Fill-In for arbitrary graphs (and connected combinatorial problems, cf. [RTL 76],[Ta 85]), and to the problem of the Gaussian elimination of sparse symmetric matrices [Ro 70], [Ro 73]. (The problem of computing Minimum Fill-In is known to be NP-complete [Ya 81]). It gives also an alternative to [GM 87] efficient parallel algorithm for computing Breadth-First Search (BFS) trees in arbitrary graphs using O(nm) processors on a CRCW PRAM.
The method of solution involves a development of new techniques for solving connected minimal set system problem, and combining it with some new divide-and-conquer methods. ----- File: 1989/tr-89-025 On Parallel Evaluation of Game Trees Richard M. Karp and Yanjun Zhang tr-89-025 May 1989 We present parallel algorithms for evaluating game trees. These algorithms parallelize the "left-to-right" sequential algorithm for evaluating AND/OR trees and the alpha-beta pruningn procedure for evaluating MIN/MAX trees. We show that, on every instance of a uniform tree, these parallel algorithms achieve a linear speed-up over their corresponding sequential algorithms, if number of processors used is close to the height of the input tree. These are the first non-trivial deterministic speed-up bounds known for the "left-to-right" algorithm and the alpha-beta pruning procedure. ----- File: 1989/tr-89-026 Separating Abstraction from Implementation in Communication Network Design Ramon Caceres tr-89-026 May 1989 Datagrams and visual circuits are not disjoint conceptual models for data communication, but rather inhabitants of a wide design space containing many other viable networking solutions. Many design choices often closely associated with these two communication styles can be decoupled from the datagram and virtual circuit abstractions, and combined to form new and effective network implementations. This paper examines several key elements of network architecture. For each element, it shows how certain characteristics often thought to differentiate datagrams and virtual circuits are independent of these two concepts and form a multi-valued spectrum of design choices. This discussion is motivated by the current drive to design a new generation of high-speed wide-area networks, and the observation that this effort would benefit from a more systematic evaluation of existing and future network design alternatives. ----- File: 1989/tr-89-027 Boolean Circuit Complexity of Algebraic Interpolation Problems Marek Karpinski tr-89-027 May 1989 We present here some recent results on fast parallel interpolation of multivariate polynomials over finite fields. Some applications towards the general conversion algorithms for boolean functions are also formulated. ----- File: 1989/tr-89-028 Application of Real-Time Monitoring to Scheduling Tasks with Random Execution Times Dieter Haban and Kang Shin tr-89-028 May 1989 A real-time monitor is employed to aid in scheduling tasks with random execution times in a real-time computing system. Scheduling algorithms are usually based on the worst-case execution time (WET) of each task. Due to data-dependent loops and conditional branches in each program and resource sharing delay during execution, this WET is usually difficult to obtain and could be several orders of magnitude larger than the true exception time. Thus, scheduling tasks based on WET could result in a severe underutilization of CPU cycles and under-estimation of systems schedulability.
To alleviate the above problem, we propose to use a real-time monitor as a scheduling aid. The real-time monitor is composed of dedicated hardware, called Test and Measurement Processor (TMP), and used to measure accurately, with minimal interference, the true execution time which consists of the pure execution time and resource sharing delay. The monitor is a permanent and transparent part of a real-time system, degrades system performance by less than 0.1 percent, and does not interfere with the host system's execution.
Using the measured pure execution time and resource sharing delay for each task, we have developed a mechanism which reduces the discrepancy between the WET and the estimated execution time. This result is then used to decide at an earliest possible time whether or not a task can meet its deadline. ----- File: 1989/tr-89-029 Behavior and Performance Analysis of Distributed Systems Using a Hybrid Monitor Dieter Haban and Dieter Wybranietz tr-89-029 May 1989 This paper describes a hybrid monitor for measuring the performance and observing the behavior of distributed systems during execution. We emphasize data collection, analysis and presentation of execution data. A special hardware support, which consists of a test and measurement processor (TMP), was designed and has been implemented in the nodes of an experimental multicomputer system consisting of eleven nodes. The operations of the TMP are completely transparent with a minimal, less than 0.1%, overhead to the measured system. In the experimental system, all the TMPs were connected with a central monitoring station, using an independent communication network, in order to provide a global view of the monitored system. The central monitoring station displays the resulting information in easy-to-read charts and graphs. Our experience with the TMP shows that it promotes an improved understanding of run-time behavior and performance measurements, to derive qualitative and quantitative assessments of distributed systems. ----- File: 1989/tr-89-030 Monitoring and Measuring Parallel Systems Using a Non-Intrusive Rule-Based System Dieter Haban and Dieter Wybranietz tr-89-030 March 1989 This paper describes a tool for on-line monitoring of distributed systems and the evaluation of the collected data. The hybrid monitor is capable of presenting the interactive user and the local operating system with high-level information of the behavior and the activities in the host system with minimal interferences. A special hardware support, which consists of a test and measurement processor (TMP), was designed and has been implemented in the nodes of an experimental multicomputer system. The operations of the TMP are completely transparent to users with a minimal, less than 0.1 percent, overhead to the hardware system. To provide a global view of the monitored system, a central monitoring station evaluates the locally collected data and displays the resulting information in charts and graphs. A rule-based evaluation system assists in improving the understanding of run-time behavior and in easily assessing performance measurements. Flexibility is achieved by rules given in tables which control the evaluation and the display of monitored and processed data. These rules represent expert-level knowledge about the evaluation of distributed systems. ----- File: 1989/tr-89-031 One-Way Functions are Essential for Complexity Based Cryptography (Extended ) Russell Impagliazzo and Michael Luby tr-89-031 May 1989 In much of modern cryptography, the security of a protocol is based on the intractability of a problem such as factorization of randomly chosen large numbers. The problems assumed intractable all have the same form; they are based on a one-way function, i.e. one that is easy to compute but hard to invert. This is not a coincidence. We show that for many cryptographic tasks any secure protocol for the task can be converted into a one-way function, and thus any proposed protocol for these tasks is implicitly based on a one-way function. Tasks examined here are chosen to cover a spectrum of cryptographic applications: private-key encryption, identification/authentication, bit commitment and coin-flipping by telephone. Thus, unless one-way functions exist, secure protocols for these tasks are impossible. ----- File: 1989/tr-89-032 A Connectionist Model of Unification Andreas Stolcke tr-89-032 May 1989 A general approach to encode and unify recursively nested feature structures in connectionist networks is described. The unification algorithm implemented by the net is based on iterative coarsening of equivalence classes of graph nodes. This method allows the reformulation of unification as a constraint satisfaction problem and enables the connectionist implementation to take full advantage of the potential parallelism inherent in unification, resulting in sublinear time complexity. Moreover, the method is able to process any number of feature structures in parallel, searching for possible unifications and making decisions among mutually exclusive unifications where necessary.
Keywords: Unification, constraint satisfaction, connectionism, feature structures. ----- File: 1989/tr-89-033 Merging Multilayer Perceptrons and Hidden Markov Models: Some Experiments in Continuous Speech Recognition Herve Bourlard and Nelson Morgan tr-89-033 May 1989 The statistical and sequential nature of the human speech production system makes automatic speech recognition difficult. Hidden Markov Models (HMM) have provided a good representation of these characteristics of speech, and were a breakthrough in speech recognition research. However, the a priori choice of a model topology and weak discriminative power limit HMM capabilities. Recently, connectionist models have been recognized as an alternative tool. Their main useful properties are their discriminative power and their ability to capture input-output relationships. They have also proved useful in dealing with statistical data. However, the sequential character of speech is difficult to handle with connectionist models. We have used a classic form of a connectionist system, the Multilayer Perceptron (MLP), for the recognition of continuous speech as part of an HMM system. We show theoretically and experimentally that the outputs of the MLP approximate the probability distribution over output classes conditioned on the input (i.e., the Maximum a Posteriori (MAP) probabilities). We also report the results of a series of speech recognition experiments. By using contextual information at the input of the MLP, frame classification performance can be achieved which is significantly improved over the corresponding performance for simple Maximum Likelihood probabilities, or even MAP probabilities without the benefit of context.
However, it was not so easy to improve the recognition of words in continuous speech by the use of an MLP, although it was clear that the classification at the frame and phoneme levels was better than we achieved with our HMM system. We present several modifications of the original methods that were required to achieve acceptable performance at the word level. Preliminary results are reported for a 1000 word vocabulary, phoneme based, speaker-dependent continuous speech recognition system embedding MLP into HMM. These results show equivalent recognition performance using either the Maximum Likelihood or the outputs of an MLP to estimate emission probabilities of an HMM. ----- File: 1989/tr-89-034 A Survey of Optical Fibers in Communication Ramesh Govindan and Srinivasan Keshav and Dinesh C. Verma tr-89-034 May 1989 In recent years there has been a major effort to integrate fiber optic media into existing communication systems. In this survey, we outline the physics behind fiber optic media and optical interfaces. Different types of optical interfaces and optical media are considered and the advantages and disadvantages of each are listed. We then discuss topologies and protocols suitable for optical fibers in communication. We also take a detailed look into the new Fiber Distributed Data Interface (FDDI) Standard for fiber-optic token rings. Finally, we list off-the-shelf fiber networks available as of September 1988. ----- File: 1989/tr-89-035 Conjectures on Representations in Backpropagation Networks Paul W. Munro tr-89-035 May 1989 The pros and cons of the backpropagation learning procedure have been the subject of numerous debates recently. Some point out its promise as a powerful instrument for finding the weights in a connectionist network appropriate to a given problem, and the generalizability of the solution to novel patterns. Others claim that it is an algorithm for fitting data to a function by error correction through gradient descent. The arguments in this paper focus on the latter (curve-fitting) point of view, but take the point of view that the power of back propagation comes from carefully choosing the form of the function to be fit. This amounts to choosing the architecture and the activation functions of the units (nodes) in the net. A discussion of the role of these two network features motivates two conjectures identifying the form of the squashing function as an important factor in the process. Some preliminary simulations in support of these conjectures are presented. ----- File: 1989/tr-89-036 A Scheme for Real-Time Channel Establishment in Wide-Area Networks Domenico Ferrari and Dinesh C. Verma tr-89-036 May 1989 Multimedia communication involving digital audio and/or digital video has rather strict delay requirements. A real-time channel is defined in this paper as a simplex connection between a source and a destination characterized by parameters representing the performance requirements of the client. A real-time service is capable of creating real-time channels on demand and guaranteeing their performance. These guarantees often take the form of delay bounds that the service enforces in exchange for offered load bounds specified and enforced by the client.
In this paper, we study the feasibility of providing real-time services on a packet-switched store-and-forward wide-area network with general topology. We describe a scheme for the establishment of channels with deterministic or statistical delay bounds, and present the results of the simulation experiments we ran to evaluate it. The results are encouraging: our approach is correct (i.e., satisfies the guarantees even in worst-case situations), uses the network's resources to a fair extent, and efficiently handles channels with a variety of offered load and burstiness characteristics. The packet transmission overhead is quite low, whereas the channel establishment overhead may occasionally become too large; an approximation method is therefore needed to reduce the latter overhead to an acceptable level even in those cases. ----- File: 1989/tr-89-037 A Tagging Method for Distributed Constraint Satisfaction Hans Werner Guesgen tr-89-037 June 1989 Local propagation algorithms such as Waltz' filtering and Mackworth's AC-x algorithms have been successfully applied in AI for solving constraint satisfaction problems (CSPs). In general, these algorithms can only be used as preprocessing methods as they do not compute a global consistent solution for a CSP; they result in local consistency also known as arc consistency.
In this paper, we introduce an extension of local constraint propagation to overcome this drawback, i.e., to compute global consistent solutions for a CSP. The advantage over backtracking approaches is that the method introduced here is easy to implement on parallel machines with an arbitrary number of processors. The underlying idea is to associate recursive tags with the values during the propagation process so that global relationships among the values are maintained. ----- File: 1989/tr-89-038 Metric Constraint Satisfaction with Intervals Peter B. Ladkin tr-89-038 June 1989 We show how algorithms in Dechter, Meiri and Pearl's recent paper on constraint satisfaction techniques for metric information on time points [DeMePe89] may be adapted to work directly with metric constraints on intervals. Inter alia we show termination of path-consistency algorithms if range intervals in the problem contain only rational number endpoints. ----- File: 1989/tr-89-039 Fast Parallel Algorithms for the Clique Separator Decomposition Elias Dahlhaus, Marek Karpinski and Mark B. Novick tr-89-039 July 1989 We give an efficient NC algorithm for finding a clique separator decomposition of an arbitary graph, that is, a series of cliques whose removal disconnects the graph. This algorithm allows one to extend a large body of results which were originally formulated for chordal graphs to other classes of graphs. Our algorithm is optimal to within a polyalgorithmic factor of Tarjan's O(nm) time sequential algorithm. The decomposition can also be used to find NC algorithms for some optimization problems on special families of graphs, assuming these problems can be solved in NC for the prime graphs of the decomposition. These optimization problems include: finding a maximum weight clique, a minimum coloring, a maximum-weight independent set, and a minimum fill-in elimination order. We also give the first parallel algorithms for solving these problems by using the clique separator decomposition. Our maximum independent set algorithm applied to chordal graphs yields the most efficient known parallel algorithm for finding a maximum-weight independent set of a chordal graph. ----- File: 1989/tr-89-040 The Possibility of an Executable Specification Language Peter B. Ladkin tr-89-040 July 1989 We consider what it takes to build an executable specification language for concurrent systems. The key ingredients are executability and very-high-level specification. Many researchers have concluded that one can't have both in any reasonable way. We consider a number of criteria for an executable specification language. We conclude that it is possible to build such a language, and thus that executability should be a criterion for evaluating any specification language for concurrent systems. ----- File: 1989/tr-89-041 Geometric Learning Algorithms; Stephen M. Omohundro tr-89-041 June 1989 Emergent computation in the form of geometric learning is central to the development of motor and perceptual systems in biological organisms and promises to have a similar impact on emerging technologies including robotics, vision, speech, and graphics. This paper examines some of the trade-offs involved in different implementation strategies, focussing on the tasks of learning discrete classifications and smooth nonlinear mappings. The trade-offs between local and global representations are discussed, a spectrum of distributed network implementations are examined, and an important source of computational inefficiency is identified. Efficient algorithms based on k-d trees and the Delaunay triangulation are presented and the relevance to biological networks is discussed. Finally, extensions of both the tasks and the implementations are given.
Keywords: learning algorithms, neural networks, computational geometry, emergent computation, robotics. ----- File: 1989/tr-89-042 Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs Elias Dahlhaus, Peter Hajnal and Marek Karpinski tr-89-042 June 1989 Dirac's classical theorem asserts that, if every vertex of a graph G on n vertices has degree at least n/2, then G has a Hamiltonian cycle. We give a fast parallel algorithm on a CREW-PRAM to find a Hamiltonian cycle in such graphs. Our algorithm uses a linear number of processors and is optimal up to a polylogarithmic factor. The algorithm works in O((log (superscript 4)) n) parallel time and uses linear number of processors on a CREW-PRAM. Our method bears some resemblance to Anderson's RNC algorithm [An] for maximal paths: we, too, start from a system of disjoint paths and try to glue them together. We are, however, able to perform the base step (perfect matching) deterministically. We also prove that a perfect matching in dense graphs can be found in NC(superscript 2). The cost of improved time is a quadratic number of processors.
On the negative side, we prove that finding an NC algorithm for perfect matching in slightly less dense graphs (1/2 - epsilon) |V| is as hard as the same problem for all graphs, and interestingly the problem of finding a Hamiltonian cycle becomes NP-complete. ----- File: 1989/tr-89-043 Parallel Asynchronous Connected Components in a Mesh Susan Hambrusch and Michael Luby tr-89-043 July 1989 Levialdi [6] introduced a parallel synchronous algorithm for counting the number of connected components in a binary image embedded in an n x n mesh of processors that runs in time O(n). We describe a parallel asynchronous algorithm for the same problem achieving the same time ----- File: 1989/tr-89-044 Removing Randomness in Parallel Computation Without a Processor Penalty Michael Luby tr-89-044 July 1989 We develop some general techniques for converting randomized parallel algorithms into deterministic parallel algorithms without a blowup in the number of processors. One of the requirements for the application of these techniques is that the analysis of the randomized algorithm uses only pairwise independence. Our main new result is a parallel algorithm for coloring the vertices of an undirected graph using at most delta + 1 distinct colors in such a way that no two adjacent vertices receive the same color, where delta is the maximum degree of any vertex in the graph. The running time of the algorithm is O((log (superscript 3)) n log log n) using a linear number of processors on a concurrent read, exclusive write (CREW) parallel random access machine (PRAM). Our techniques also apply to several other problems, including the maximal independent set problem and the maximal matching problem. The application of the general technique to these last two problems is mostly of academic interest because parallel algorithms that use a linear number of processors which have better running times have been previously found [Israeli, Siloach86], [Goldberbg, Spencer 87]. ----- File: 1989/tr-89-045 Parallel Path-Consistency Algorithms for Constraint Satisfaction Peter B. Ladkin and Roger D. Maddux tr-89-045 August 1989 This paper concerns heuristic algorithms used for solution of Boolean Constraint Satisfaction Problems, or CSPs [Mon74, Mac77, Fre78, Mac87]. CSPs occur particularly in areas of artificial intelligence such as vision, temporal reasoning, and truth-maintenance systems. The most common form involves binary constraints and we consider properties of binary CSPs only (we shall omit the adjective from now on). CSPs may be represented by labeled digraphs called binary constraint networks, or BCNs. Many constraint satisfaction techniques operate upon BCNs. An important property of BCNs is that of path-consistency, which is used extensively as a heuristic for solving CSPs (many classes of CSPs are NP-hard, e.g. [VilKau86]). nEvery BCN has a path-consistent reduction, and it is known that algorithms for computing it are serial O(n superscript 3) in the number of variables [Mac77, Fre78, All83, MacFre85, MohHen86].
We have formulated CSPs and path-consistency computations in the framework of Tarski's relation algebra, and give a brief overview below [Tar41, LadMad88.2]. We give a parallel O((n superscript 2) log n) algorithm for achieving path-consistency. We also give a class of hard examples on which all algorithms proposed so far, and possible parallelisations of them, take time 0(n superscript 2). This effectively constrains parallel path- consistency algorithms of the most common form (which we glorify with the name of reduction-type) within a fairly narrow asymptotic range.
In the next section, we introduce the relation-algebraic formulation of CSPs. We formulate some algorithms in the following section, ending with the O((n superscript 2) log n) parallel path-consistency algorithm. In the final section, we describe the class of problems on which the reduction-type algorithms take 0(n superscript 2) time. ----- File: 1989/tr-89-046 On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials over Finite Fields Michael Clausen, Andreas Dress, Johannes Grabmeier, and Marek Karpinski tr-89-046 July 1989 Given a black box which will produce the value of a k-sparse multivariate polynomial for any given specific argument, one may ask for optimal strategies (1) to distinguish such a polynomial from the zero-polynomial, (2) to distinguish any two such polynomials from one other and (3) to (uniformly) reconstruct the polynomial from such an information source. While such strategies are known already for polynomials over fields of characteristic zero, the equally important, but considerably more complicated case of a finite field K of small characteristic is studied in the present paper. The result is that the time complexity of such strategies depends critically on the degree m of the extension field of K from which the arguments are to be chosen; e.g., if m equals the number n of variables, then (1) can be solved by k+1 and (2) as well as (3) by 2k+1 queries, while in case m=1 essentially 2 (superscript log n log k) queries are needed. ----- File: 1989/tr-89-047 The Transitive Closure of a Random Digraph; Richard M. Karp tr-89-047 August 1989 In a random $n$-vertex digraph, each arc is present with probability $p$, independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph. We show that, when $n$ is large and $np$ is equal to a constant $c$ greater than 1, it is very likely that all but one of the strong components are very small, and that the unique large strong component contains about $ size 9 {\(*H} sup 2 n$ vertices, where $ size 9 {\(*H}$ is the unique root in $[0,1]$ of the equation $1~-~x~-~e sup -cx ~=~0$. Nearly all the vertices outside the large strong component lie in strong components of size 1. Provided that the expected degree of a vertex is bounded away from 1, our transitive closure algorithm runs in expected time $O(n)$. For all choices of $n$ and $p$, the expected execution time of the algorithm is $O(w(n)~(n^ log ^n) sup 4/3 )$, where $w(n)$ is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be $\(*W (n sup 2 )$ the algorithm presents the transitive closure in the compact form $(A~ times ~B)~\(cu~C$, where $A$ and $B$ are sets of vertices, and $C$ is a set of arcs. ----- File: 1989/tr-89-048 Parallel Heuristics for the Steiner Tree Problem in Images without Sorting or Routing Susanne Hambrusch and Lynn TeWinkel tr-89-048 August 1989 In this paper we consider the problem of determining a minimum-cost rectilinear Steiner tree when the input is an n X n binary array I which is stored in an n X n mesh of processors. We present several heuristic mesh algorithms for this NP-hard problem. A major design criteria of our algorithms is to avoid sorting and routing which are expensive operations in practice. All of our algorithms have a O(n log k) running time, where k is the number of connected components formed by the entries of value `1'. The main contribution of the paper are two conceptually different methods for connecting components in an image. ----- File: 1989/tr-89-049 Spatial Reasoning Based on Allen's Temporal Logic Hans Werner Guesgen tr-89-049 July 1989
"If one were to categorize the behavior of the intelligent machine of the future, one might do so on the basis of the machine's capabilities to carry out temporal reasoning over interrelated entities that change with time; to carry out spatial reasoning for solving problems dealing with entities occupying space; and, on a more complex level, to reason over interrelated entities occupying space and changing in time with respect to their attributes and spatial interrelationships." --Avi Kak [12]
There are a lot of approaches to spatial reasoning which are more or less efficient. Nevertheless, they are not always adequate from the cognitive point of view. What we want to suggest in this paper is reasoning based on qualitative descriptions of spatial relationships. We introduce a set of basic relations similar to the one Allen suggested for temporal reasoning and we show how inferences can be performed on this set.
We start with one dimensional descriptions which we extend to more-dimensional ones in various ways. A theoretical base is provided and the soundness of our approach is proven. Although we do not claim our approach to be suitable in general, it is an efficient and straightforward way in many situations to handle spatial knowledge. ----- File: 1989/tr-89-050 Learning Read-Once Formulas with Queries Dana Angluin, Lisa Hellerstein and Marek Karpinski tr-89-050 July 1989 A read-once formula is a boolean formula in which each variable occurs at most once. Such formulas are also called m-formulas or boolean trees. This paper treats the problem of exactly identifying an unknown read-once formula using specific kinds of queries. The main results are a polynomial time algorithm for exact identification of monotone read-once formulas using only membership queries, and a polynomial time algorithm for exact identification of general read-once formulas using equivalence and membership queries (a protocol based on the notion of a minimally adequate teacher[1]). Our results improve on Valiant's previous results for read-once formulas [18]. We also show that no polynomial time algorithm using only membership queries or only equivalence queries can exactly identify all read-once formulas. ----- File: 1989/tr-89-051 A Note on Computational Indistinguishability Oded Goldreich tr-89-051 July 1989 We show that the following two conditions are equivalent:
----- File: 1989/tr-89-052 An Efficient Parallel Algorithm for the 3MIS Problem Elias Dahlhaus and Marek Karpinski tr-89-052 September 1989 The paper considers the problem of computing a maximal independent set in hypergraphs (see [Karp, Ramachandran 88] and [Beame, Luby 89]). We present an efficient deterministic parallel algorithm for the case when the maximal cardinality of any hyperedge is 3. The algorithm works in O((log superscript 4) n) parallel time with O(n + m) processors on a CREW PRAM and is optimal up to a polylogarithmic factor. ----- File: 1989/tr-89-053 Supporting Formal Program Developments: the DEVA Environment Stefan Jahnichen, Robert Gabriel, Matthias Weber and Matthias Anlauff tr-89-053 September 1989 The project ToolUse aims at providing means for active assistance in the design, implementation and evolution of software. This is achieved and supported by a formal development language called Deva. As Deva uses two-dimensional notations to get better structured and surveyable representations of developments, and as different Deva implementations have been used within the project, both internal and external integration play crucial roles in the project ToolUse. The paper shortly introduces the language DEVA, sketches one of its implementations, and discusses both kinds of integration. ----- File: 1989/tr-89-054 Fast Evaluation of Boolean Formulas by CREW-PRAMs Rudiger Reischuk tr-89-054 September 1989 We extend the result of Cook, Dwork and Reischuk [CDR86] that a CREW-PRAM with a linear number of processors can computer the or of n bits in less than log(subscript 2)n time to arbitrary Boolean formulas of logarithmic depth. Furthermore a matching lower bound for the or shown by Kutylowski [K89] is generalized to probabilistic and nondeterministic computations. ----- File: 1989/tr-89-055 On the Theory of Average Case Complexity (Revised Edition) Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby tr-89-055 September 1989 This paper takes the next step in developing the theory of average case complexity initiated by Leonid A. Levin. Previous works [Levin 84, Gurevich 87, Venkatesan and Levin 88] have focused on the existence of complete problems. We widen the scope to other basic questions in computational complexity. Our results include:1) The existence of pseudorandom generators.
2) The existence of a pair of efficiently constructible distributions which are computationally indistinguishable but statistically very different.
The extension is based on two observations: (1) a real-time channel can be looked upon as a network with bounded delays connecting the multiplexing point (a virtual source) to the demultiplexing point (a virtual destination); and the parameters of the physical channel can be used to define the service time at the virtual source and sink. Multiplexing is nothing but channel establishment over this network. By a judicious definition of the parameter specifying service times, it is possible to make multiplexing decisions at the multiplexing point (source) without consulting the destination, which is merely informed about the new multiplexed channel. ----- File: 1989/tr-89-058 Controlled Gradual Disclosure Schemes for Random Bits and Their Applications Richard Cleve tr-89-058 October 1989 We construct a protocol that enables a secret bit to be revealed gradually in a very controlled manner. In particular, if Alice possesses a bit S that was generated randomly according to the uniform distribution and 1/2 < p(subscript 1) < ... < p(subscript m) = 1 then, using our protocol with Bob, Alice can achieve the following. The protocol consists of m stages and after the i-th stage, Bob's best prediction of S, based on all his interactions with Alice, is correct with probability exactly p(subscript i) (and a reasonable condition is satisfied in the case where S is not initially uniform). Furthermore, under an intractabilility assumption, our protocol can be made "oblivious" to Alice and "secure" against an Alice or Bob that might try to cheat in various ways. Previous proposed gradual disclosure schemes for single bits release information in a less controlled manner: the probabilities that represent Bob's confidence of his knowledge of S follow a random walk that eventually drifts towards 1, rather that a predetermined sequence of values.
Using controlled gradual disclosure schemes, we show how to construct an improved version of the protocol proposed by Luby, Micali and Rackoff for two-party secret bit exchanging ("How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin," Proc. 22nd Ann. IEEE Symp. on Foundations of Computer Science, 1983, pp. 11-21) that is secure against additional kinds of attacks that the previous protocol is not secure against. Also, our protocol is more efficient in the number of rounds that it requires to attain a given level of security, and is proven to be asymptotically optimal in this respect.
We also show how to use controlled gradual disclosure schemes to improve existing protocols for other cryptographic problems, such as multi-party function evaluation. ----- File: 1989/tr-89-059 Accessing and Customizing Services in Distributed Systems Ralf Guido Herrtwich and Uwe Wolfgang Brandenburg tr-89-059 October 1989 In a distributed system, entities access services provided to them by other entities at remote sites. While it may be unimportant to the service users which entities act as service providers, they often have other requirements on the services they use. On the other hand, service providers only have certain possibilities. Both the requirements and possibilities can be described by means of quality-of-service parameters (QOSPs), which have to be determined for each service session. In this paper we design a session establishment service (SES) which takes QOSP values into account. The SES can be used for any kind of QOSPs since it uses badness specifications as a uniform means to identify the usefulness of a certain QOSP value to a service user, to determine the relative importance of single QOSPs, and to calculate the overall quality of a service. Three kinds of QOSPs are distinguished: Static parameters do not change as long as the service is available, dynamic parameters depend on the current state of a service provider, and retrospective parameters result from evaluations of the service which are obtained from previous service users. While some QOSP values are available others can only be accomplished if the service provider schedules its resources appropriately. The reservation of resources can be integrated within the SES. This is especially important for real-time services. ----- File: 1989/tr-89-060 VC Dimension and Learnability of Sparse Polynomials and Rational Functions Marek Karpinski and Thorsten Werther tr-89-060 November 1989 We prove upper and lower bounds on the VC dimension of sparse univariate polynomials over reals, and apply these results to prove uniform learnability of sparse polynomials and rational functions. As another application we solve an open problem of Vapnik [Vapnik 82] on uniform approximation of the general regression functions, a central problem of computational statistics (cf. [Vapnik 82], p. 256). ----- File: 1989/tr-89-061 On Space-bounded Learning and the Vapnik-Chervonenkis Dimension (Thesis) Sally Floyd tr-89-061 December 1989 This thesis explores algorithms that learn a concept from a concept class of Vapnik-Chervonenkis (VC) dimension d by saving at most d examples at a time. The framework is the model of probably approximately correct (pac) learning introduced by Valiant [V84]. A maximum concept class of VC dimension d is defined. For a maximum class C of VC dimension d, we give an algorithm for representing a finite set of positive and negative examples of a concept by a subset of d labeled examples of that set. This data compression scheme of size d is used to construct a space-bounded algorithm called the iterative compression algorithm that learns a concept from the class C by saving at most d examples at a time. These d examples represent the current hypothesis of the learning alorithm. A space-bounded algorithm is called acyclic if a hypothesis that has been rejected as incorrect is never reinstated. We give a sufficient condition for the iterative compression algorithm to be acyclic on a maximum class C. Classes for which the iterative compression algorithm is acyclic include positve half-spaces in Euclidean space E(superscript n), balls in E(superscript n), and arbitrary rectangles and triangles in the plane. The iterative compression algorithm can be thought of as learning a boundary between the positive and the negative examples. ----- File: 1989/tr-89-062 The Asynchronous PRAM: A Semi-Synchronous Model for Shared Memory MIMD Machines (Thesis) Phillip Baldwin Gibbons tr-89-062 December 1989 This thesis introduces the Asynchronous PRAM model of computation, of the design and analysis of algorithms that are suitable for large parallel machines in which processors communicate via a distributed, shared memory. The Asynchronous PRAM is a variant of the well-studied PRAM model which differs from the PRAM in two important respects: (i) the processors run asynchronously and there is an explicit charge for synchronization, and (ii) there is a non-unit time cost to access the shared memory.
Many new algorithms are presented for the Asynchronous PRAM model. We modify a number of PRAM algorithms for improved asymptotic time and processor complexity in the Asynchronous PRAM. We show general classes of problems for which the time complexity can be improved by restructuring the computation. We prove lower bounds that reflect limitation on information flow and load balancing in this model. Simulation results between the Asynchronous PRAM and various known synchronous models are presented as well.
We introduce a post office gossip game for studying the inherent synchronization complexity of coordinating processors using pairwise synchronization primitives. Results are presented that compare the relative power of various such primitives. These results and techniques are used to reduce the amount of synchronization in Asynchronous PRAM algorithms.
Furthermore, we discuss a programming model based on the Asynchronous PRAM. We introduce the notion of a semi-synchronous programming model, a model for repeatable asynchronous programs. Repeatable programs, in which the output and all intermediate results are the same every time the program is run on a particular input, greatly simplify the tasks of writing, debugging, analyzing, and testing programs.
Finally, we discuss hardware support for the Asynchronous PRAM model. In particular, we present a cache protocol suitable for the Asynchronous PRAM and a new technique for barrier synchronous PRAM and a new technique for barrier synchronization. ----- File: 1989/tr-89-063 Five Balltree Construction Algorithms; Stephen M. Omohundro tr-89-063 December 1989 Balltrees are simple geometric data structures with a wide range of practical applications to geometric learning tasks. In this report we compare 5 different algorithms for constructing balltrees from data. We study the tradeoff between construction time and the quality of the constructed tree. Two of the algorithms are on-line, two construct the structures from the data set in a top down fashion, and one uses a bottom up approach. ----- File: 1989/tr-89-064 Program Checkers for Algebraic Problems (Thesis) Sampath Kanan tr-89-064 February 1989 In this thesis we explore a model of ensuring the correctness of results produced by programs. This model called program checking is distinct from the two methods in the literature -- testing and verification. Testing does not provide mathematical guarantees on the correctness of computation. Verification requires going into the inner workings of a program to determine its correctness, and is infeasible to implement for all but very simple programs.
Program checking treats the program as a black box. In the checking scenario the program is run on the desired input and the output is checked by a program checker. The checker is allowed to make other calls to the program to ensure the correctness of the original computation with very high probability. The theory of program checking draws heavily from the theory of interactive proof systems and probabilistic algorithms, but the model is intended to be very practical as well.
Our focus in this thesis is on program checkers for algebraic problems. The unifying theme amongst such problems is the concept of random self-reducibility. A function f is randomly self-reducible if the computation of f(x) for any x can be reduced to the computation of several "randomly chosen" inputs. For most of the algebraic problems considered in this thesis the checkers use the fact that the problem is at least partially self-reducible. This allows us to construct sets of instances whose answers are related. Verifying consistency of the program's answers on these instances allows us to design checkers for problems in linear algebra such as rank and determinant and for problems such as graph isomorphism and group intersection.
We also study the connection between interactive proofs and program checking. Using the two step approach of designing an interactive proof and converting it into a checker, we design a checker for group intersection. We construct bounded round interactive proofs for a few other problems including the problem of permutation group non-isomorphism. This interactive proof uses interesting consequences of the classification of finite simple groups.
Finally we consider the notion of random self-reducibility in its own right and obtain negative results about the random self-reducibility of certain functions. ----- File: 1989/tr-89-065 Lectures on a Theory of Computation and Complexity over the Reals (or an Arbitrary Ring) Lenore Blum tr-89-065 December 1989 These lectures discuss a new theory of computation and complexity which attempts to integrate key ideas from the classical theory in a setting more amenable to problems defined over continuous domains. The goal is to develop theoretical foundations for a theory of computational complexity for numerical analysis and scientific computation that might embody some of the naturalness and strengths of the classical theory.
We highlight key aspects of the new theory as well as to give exposition, in this setting, of classical ideas and results. Indeed, one of our themes will be the comparison of results over the integers with results over the reals and complex numbers. Contrasting one theory with the other will help illuminate each, and give deeper understanding to such basic concepts as decidability, definability, computability and complexity. ----- File: 1990/tr-90-001 The Delaunay Triangulation and Function Learning; Stephen M. Omohundro tr-90-001 January 1990 In this report we consider the use of the Delaunay triangulation for learning smooth nonlinear functions with bounded second derivatives from sets of random input output pairs. We show that if interpolation is implemented by piecewise-linear approximation over a triangulation of the input samples, then the Delaunay triangulation has a smaller worst case error at each point than any other triangulation. The argument is based on a nice connection between the Delaunay criterion and quadratic error functions. The argument also allows us to give bounds on the average number of samples needed for a given level of approximation. ----- File: 1990/tr-90-002 Speech Segmentation and Labeling on the NeXT Machine Chuck Wooters and Nelson Morgan tr-90-002 January 1990 We are attempting to incorporate connectionist models into speech recognition algorithms. Since these models require a large amount of training data, it was necessary to build an automated speech labeling/segmentation application. There were two significant system requirements for this program:
We report here on a program we have developed to integrate automatic labeling and segmentation of continuous speech with a manual system for observing and correcting these signal annotations. The overall system has functioned well enough to permit easy user marking of 600 sentences in a reasonable amount of time. ----- File: 1990/tr-90-003 Considerations for the Electronic Implementation of Artificial Neural Networks Nelson Morgan tr-90-003 January 1990 Computer scientists and designers have long been interested in comparisons between artificial automata and the human brain [Von Neumann, 1957]. Mental activity is often characterized as the result of the parallel operation of large numbers of neurons (~10 superscript 11 for the human brain). Neurons interact electrochemically on a time scale of milliseconds, and are jointly capable of significant feats of pattern recognition (such as recognizing a friend wearing an unusual costume). These commonplace human achievements are currently unattainable by large electronic computers built from components with characteristic delays in the nanosecond range. Artificial Neural Network (ANN) researchers hope that simplified functional models of nervous tissue can help us to design algorithms and machines that are better than conventional computers for difficult problems in machine perception and intelligence.
However, engineering constraints for silicon implementations of these systems may suggest design choices which differ from mimicry of biology in significant ways. In particular, large silicon ANN systems may require multiplexing of communication AND CO and computation as a consequence of limited connectivity. This report discusses considerations such as these, and concludes with a short description of an ongoing effort to design silicon ANN building blocks using powerful CAD tools. ----- File: 1990/tr-90-004 On the Complexity of Genuinely Polynomial Computation Marek Karpinski and Friedhelm Meyer auf der Heide tr-90-004 January 1990 We present the separation results on genuinely (also called strong) sequential, parallel, and non-deterministic complexity classes for the set of arithmetic RAM operations {+, -, *} and {+, -, DIV subscript c}. In particular, we separate non-uniform polynomial time from non-uniform parallel polynomial time for the set of operations {+, -, *}, answering a question posed in [Meyer auf der Heide 88]. ----- File: 1990/tr-90-005 Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents Dima Y. Grigoriev, Marek Karpinski, and Michael F. Singer tr-90-005 January 1990 We present the first algorithm for the (black box) interpolation of t-sparse rational functions without knowing bounds on exponents of their sparse representations. ----- File: 1990/tr-90-006 A Resource Reservation Protocol for Guaranteed-Performance Communication in the Internet David P. Anderson, Ralf Guido Herrtwich, and Carl Schaefer tr-90-006 February 1990 This report describes the Session Reservation protocol (SRP). SRP is defined in the DARPA Internet family of protocols. It allows communicating peer entities to reserve the resources (CPU and network bandwidth) necessary to achieve given performance objectives (delay and throughput). The immediate goal of SRP is to support continuous media (digital audio and video) in IP-based distributed systems. However, it is applicable to any application that requires guaranteed-performance network communication.
The design goals of SRP include: independence from transport protocols (SRP can be used with standard protocols such as TCP or with new real-time protocols); compatibility with IP (packets are not modified); and that a host implementing SRP can benefit from its use even when communicating with hosts not supporting SRP.
SRP is based on a workload and scheduling model called the DASH resource model. This model defines a parameterization of client workload, an abstract interface for hardware resources, and an end-to-end algorithm for negotiated resource reservation based on cost minimization. SRP implements this end-to-end algorithm, handling those resources related to network communication. ----- File: 1990/tr-90-007 Client Requirements for Real-Time Communication Services Domenico Ferrari tr-90-007 March 1990 A real-time communication service provides its clients with the ability to specify their performance requirements and to obtain guarantees about the satisfaction of those requirements. In this paper, we propose a set of performance specifications that seem appropriate for such services; they include various types of delay bounds, throughput bounds, and reliability bounds. We also describe other requirements and desirable properties from a client's viewpoint, and the ways in which each requirement is to be translated to make it suitable for lower levels in the protocol hierarchy. Finally, we present examples of requirements specification, and discuss some of the possible objections to our approach. ----- File: 1990/tr-90-008 An Algebraic Approach to General Boolean Constraint Problems Hans W. Guesgen and Peter B. Ladkin tr-90-008 March 1990 We consider an algebraic approach to the statement and solution of general Boolean constraint satisfaction problems (CSPs). Our approach is to consider partial valuations of a constraint network (including the relational constraints themselves) as sets of partial functions, with the operators of join and projection. We formulate all the usual concepts of CSPs in this framework, including k-consistency, derived constraints, and backtrack-freeness, and formulate an algorithm scheme for k-consistency which has the path-consistency scheme in [LadMad88.2] as a special case. This algebra may be embedded in the cylindric algebra of Tarski [HeMoTa71, 85], via the embedding of [ImiLip84], and a connection with relational database operations. CSPs are shown to correspond to conjunctive queries in relational database theory, and we formulate a notion of equivalence of CSPs with hidden variables, following [ChaMer76, Ull80], and show that testing equivalence is NP-hard. ----- File: 1990/tr-90-009 Miniature Language Acquisition: A touchstone for cognitive science; Jerome A. Feldman, George Lakoff, Andreas Stolcke, and Susan Hollbach Weber tr-90-009 March 1990 (revised April 1990) Cognitive Science, whose genesis was interdisciplinary, shows signs of reverting to a disjoint collection of fields. This paper presents a compact, theory-free task that inherently requires an integrated solution. The basic problem is learning a subset of an arbitrary natural language from picture-sentence pairs. We describe a very specific instance of this task and show how it presents fundamental (but not impossible) challenges to several areas of cognitive science including vision, language, inference and learning. ----- File: 1990/tr-90-010 L0: A Testbed for Miniature Language Acquisition; Susan Hollbach Weber and Andreas Stolcke tr-90-010 May 1990 L0 constitutes a recent effort in Cognitive Science to build a natural language acquisition system for a limited visual domain. As a preparatory step towards addressing the issue of learning in this domain, we have built a set of tools for rapid prototyping and experimentation in the areas of language processing, image processing, and knowledge representation. The special focus of our work was the integration of these different components into a flexible system which would allow us to better understand the domain given by L0 and experiment with alternative approaches to the problems it poses. ----- File: 1990/tr-90-011 A Network for Extracting the Locations of Point Clusters Using Selective Attention; Subutai Ahmad and Stephen Omohundro tr-90-011 May 1990 This report explores the problem of dynamically computing visual relations in connectionist systems. It concentrates on the task of learning whether three clumps of points in a 256x256 image form an equilateral triangle. We argue that feed-forward networks for solving this task would not scale well to images of this size. One reason for this is that local information does not contribute to the solution: it is necessary to compute relational information such as the distances between points. Our solution implements a mechanism for dynamically extracting the locations of the point clusters. It consists of an efficient focus of attention mechanism and a cluster detection scheme. The focus of attention mechanism allows the system to select any circular portion of the image in constant time. The cluster detector directs the focus of attention to clusters in the image. These two mechanisms are used to sequentially extract the relevant coordinates. With this new representation (locations of the points) very few training examples are required to learn the correct function. The resulting network is also very compact: the number of required weights is proportional to the number of input pixels. ----- File: 1990/tr-90-012 A Connectionist Unification Algorithm Steffen Hoelldobler tr-90-012 March 1990 Unification plays an important role in many areas of computer science, mathematical logic, and artificial intelligence. It is also at the heart of connectionist models concerned with knowledge representation and inference. However, most of these models are severly restricted by their propositional fixation as they are defined over a finite set of constants and predicates. This restriction is caused by the inability to unify terms built from function symbols, constants and variables. In this paper a connectionist unification algorithm is presented. It utilizes the fact that the most general unifier of two terms corresponds to a finest valid equivalence relation defined on a occurrence-label representation of the unification problem. The algorithm exploits the maximal parallelism inherent in the computation of such a finest valid equivalence relation while using only computational features of connectionism. It can easily be restricted to solve special forms of the unification problem such as the word problem, the matching problem, or the unification problem over infinite trees. ----- File: 1990/tr-90-013 Towards Optimal Simulations of Formulas by Bounded-Width Programs Richard Cleve tr-90-013 March 1990 We show that, over an arbitrary ring, for any fixed epsilon > 0, all balanced algebraic formulas of size s are computed by algebraic straight-line programs that employ a constant number of registers and have length O (s superscript(1+epsilon)). In particular, in the special case where the ring is GF(2), we obtain a technique for simulating balanced Boolean formulas of size s by bounded-width branching programs of length O(s superscript(1+epsilon)), for any fixed epsilon > 0. This is an asymptotic improvement in efficiency over previous simulations in both the Boolean and algebraic setting. ----- File: 1990/tr-90-014 Dynamic Constraints Hans Werner Guesgen and Joachim Hertzberg tr-90-014 April 1990 Usually, a constraint describes a relation on variables, and networks of constraints are obtained by sharing variables among constraints. Manipulating a constraint or a constraint network means manipulating the variables until a consistent assignment is found. There are, however, deviations from this classical view, e.g., manipulating the constraints themselves to make the computation of consistent assignments more efficient, or relaxing constraints to make an overspecified constraint problem solvable.
In this paper, we present a formalism that subsumes classical constraint satisfaction, constraint manipulation, and constraint relaxation. The idea is that the constraints in a network are not static but that their relations can and must be manipulated and that manipulating relations subsumes manipulating variable values. We clarify the relation between classical constraint networks and the newly developed dynamical ones; we prove termination properties of dynamic constraint networks in the special case of filtering; and we show by examples how to express constraint manipulation and constraint relaxation in the new formalism. ----- File: 1990/tr-90-015 Learning Feature-based Semantics with Simple Recurrent Networks; Andreas Stolcke tr-90-015 April 1990 The paper investigates the possibilities for using simple recurrent networks as transducers which map sequential natural language input into non-sequential feature-based semantics. The networks perform well on sentences containing a single main predicate (encoded by transitive verbs or prepositions) applied to multiple-feature objects (encoded as noun-phrases with adjectival modifiers), and shows robustness against ungrammatical inputs. A second set of experiments deals with sentences containing embedded structures. Here the network is able to process multiple levels of sentence-final embeddings but only one level of center-embedding. This turns out to be a consequence of the network's inability to retain information that is not reflected in the outputs over intermediate phases of processing. Two extensions to Elman's \shortcite{Elman:88} original recurrent network architecture are introduced. ----- File: 1990/tr-90-016 Temporal Reasoning Based on Semi-Intervals (Revised Version) Christian Freksa tr-90-016 April 1990 A generalization of Allen's interval-based approach to temporal reasoning is presented. The scope of reasoning capabilities can be considerably extended by using relations between semi-intervals rather than intervals as the basic units of knowledge. Semi-intervals correspond to beginnings or endings of temporal events. We develop a representational framework in which relations between semi-intervals appear as coarse knowledge in comparison with relations between intervals. We demonstrate the advantages of reasoning on the basis of semi-intervals: 1) coarse knowledge can be processed directly; computational effort is saved; 2) incomplete knowledge about temporal intervals can be fully exploited; 3) incomplete inferences made on the basis of complete knowledge can be used directly for further inference steps; 4) there is no trade-off in computational strength for the added flexibility and efficiency; 5) semi-intervals correspond to natural entities both from a cognitive and from a computational point of view. The presented scheme supports reasoning on the basis of fine-grained or complete knowledge, on the basis of coarse or incomplete knowledge, and on combinations of both kinds of knowledge. The notion of `conceptual neighborhood' is central to the presented approach. Besides enhancing the reasoning capabilities in several directions, this notion allows for a drastic compaction of the knowledge base underlying Allen's inference scheme. A connection to fuzzy reasoning on the basis of `conceptual neighborhood' is drawn. It is suggested that reasoning based on the simplified knowledge base may be particularly suited for the implementation of parallel inference engines.
[Revised version was published as:
Freksa C, Temporal reasoning based on semi-intervals, Artificial
Intelligence 54 (1992) 199-227.]
-----
File: 1990/tr-90-017
Time Dated Streams in Continuous-Media Systems
Ralf Guido Herrtwich
tr-90-017
May 1990
Data in continuous-media systems, such as digital
audio and video, has time parameters associated with
it that determine its processing and display. We
present the "time capsule" abstraction to describe
how timed data shall be stored, exchanged, and
accessed in a real-time system. When data is written
into a time capsule, a time stamp and a duration are
associated with the data item. When it is read, a time
stamp is used to select the data item. The time capsule
abstraction includes the notion of "clocks" that
ensure periodic data access that is typical for
continuous-media applications. By modifying the
parameters of a clock, effects such as time lapses or
slow motion can be achieved.
-----
File: 1990/tr-90-018
A Connectionist Approach to Symbolic Constraint Satisfaction
Hans Werner Guesgen
tr-90-018
April 1990
Algorithms for solving constraint satisfaction
problems, i.e., for finding one, several, or all
solutions for a set of constraints on a set of
variables, have been introduced in a variety of
papers in the area of Artificial Intelligence. Here,
we illustrate how a connectionist network for
constraint satisfaction can be implemented.
The idea is to use a connectionist node for each value of each variable and for each tuple of each constraint of the constraint satisfaction problem, and to connect them according to the way in which the constraints are related to the variables. Goedel numbers are used as potentials of the nodes that correspond to variables, representing possible paths of solutions. ----- File: 1990/tr-90-019 Applications of Topology to Lower Bound Estimates in Computer Science Michael D. Hirsch tr-90-019 May 1990 This research explores the relationship between topology and computer science by analyzing simple problems in which the role played by topology is crucial, yet which can be approached using techniques that are not too esoteric. The goal is to develop a set of topological tools which can then be applied to other, more central, problems in complexity theory.
We define the concepts of "a problem" and "problem reduction" in computer science in such a way as to make the techniques of point set and algebraic topology applicable. Following Smale, we define "topological complexity" as the minimal number of branch nodes in an algebraic computation tree and relate it to the Schwartz genus of a map.
We introduce a new problem, the new point problem (NPP), and calculate its topological complexity for a variety of spaces. NPP has many variations. The most realistic and applicable version is the following. Given a list of n distinct points in a metric space X with a known lower bound delta for the distance between any two points, what is the topological complexity of finding a new point y such that delta is still a lower bound for the distance between any two points.
We prove:
PrE-nets inherit from the algebraic theory of abstract datatypes and from net-theory. From the side of algebraic specification notions like the modular decomposition, initial models or consistency and completeness carry over to PrE-nets and preserve their standard semantics. These notions are related to the static semantics and the invariants of the dynamic behavior of a non-sequential system. From the net-theoretic side theorems and methods for analysis of behavioral properties are applicable to PrE-nets in a straightforward way. Here we consider in particular net transformations and decomposition methods. ----- File: 1990/tr-90-021 Structure and Schedulingin Real-Time Protocol Implementations David P. Anderson, Luca Delgrossi and Ralf G. Herrtwich tr-90-021 June 1990 Real-time network communication involves 1) the underlying network and its contention mechanism, 2) the design of transport protocols, 3) the scheduling of CPU and network interface devices, and 4) the process/interrupt structure of protocol implementations. This paper is concerned with 3) and 4), in the context of network communication of digital audio and video data.
We describe the issues and design alternatives for CPU and network interface scheduling in the sending host, and CPU scheduling for protocol processing in the receiving host. We discuss how the proposed policies can be incorporated in existing operating systems such as UNIX. Our discussion is based on the "DASH resource model", a workload and scheduling model designed for real-time communication. ----- File: 1990/tr-90-022 Buffer Space Allocation for Real-Time Channels in a Packet-Switching Network Domenico Ferrari and Dinesh C. Verma tr-90-022 June 1990 Broadband integrated networks will have to offer real-time communication services; that is, they will have to transport information with performance guarantees. A paper previously published by the authors presented a scheme for establishing real-time channels in a pure packet-switching network; that scheme did not include any method for allocating buffer space in the network's nodes to the channels being established. This paper completes the description and evaluation of that scheme, since it presents one such method, and some of the results of the extensive simulations performed to test it. The method is found to be correct and to have a low overhead. While the utilization of the buffer space allocated to the statistical channels is often quite low, thereby indicating that our worst-case approach tends to overallocate space to those channels, the space our method gives to deterministic channels seems to be reasonably well utilized. ----- File: 1990/tr-90-023 On the Power of Randomization in Online Algorithms; S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson tr-90-023 June 1990 Against an adaptive adversary, we show that the power of randomization in online algorithms is severely limited! We prove the existence of an efficient ``simulation'' of randomized online algorithms by deterministic ones, which is best possible in general.
The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases. ----- File: 1990/tr-90-024 An Introduction to Randomized Algorithms; Richard M. Karp tr-90-024 June 1990 Research conducted over the past fifteen years has amply demonstrated the advantages of algorithms that make random choices in the course of their execution. This paper presents a wide variety of examples intended to illustrate the range of applications of randomized algorithms, and the general principles and approaches that are of greatest use in their construction. The examples are drawn from many areas, including number theory, algebra, graph theory, pattern matching, selection, sorting, searching, computational geometry, combinatorial enumeration, and parallel and distributed computation. ----- File: 1990/tr-90-025 Approximating the Number of Solutions of a GF[2] Polynomial Marek Karpinski and Michael Luby tr-90-025 July 1990 We develop a polynomial time Monte-Carlo algorithm for estimating the number of solutions to a multivariate polynomial over GF[2]. This gives the first efficient method for estimating the number of points on algebraic varieties ove GF[2], which has been recently proven to be #P-complete even for cubic polynomials. There are a variety of applications of our result, which will be discussed in the full version of the paper. ----- File: 1990/tr-90-026 Audio and Video in Distributed Computer Systems: Why and How? Ralf Guido Herrtwich tr-90-026 July 1990 Technological advances allow computer systems to handle "continuous media" such as audio and video in addition to "discrete media" such as text and graphics. As with the introduction of computer graphics ten years ago, the integration of continuous media will extend the range of computer applications and change existing paradigms for computer usage and programming. Distributed computer systems that are capable of handling continuous media can (1) unify the methods of information distribution, (2) personalize information services through interactive access and individual information selection, and (3) make information presentation more effective. The major obstacles to using continuous media in today's computer systems are performance limitations. In addition to high-capacity and high-speed hardware, system software is needed that meets the real-time demands of audio and video, and that provides application interfaces which take the special requirements of these new data types into account. ----- File: 1990/tr-90-027 Complexity Theoretic Issues Concerning Block Ciphers Related to D.E.S. Richard Cleve tr-90-027 July 1990 The D.E.S. cipher is naturally viewed as a composition of sixteen invertible transformations on 64-bit strings (where the transformations depend of the value of a 56-bit key). Each of the transformations has a special form and satisfies the particular property that each of its output bits is determined by a "small" number of its input bits. We investigate the computational power of block ciphers on n-bit strings that can be expressed as polynomial-length (with respect to n) compositions of invertible transformations that have a form similar to those of D.E.S. In particular, we require that the basic transformations have the property that each of their output bits depends on the value of a small number of their input bits (where "small" is somewhere in the range between O(1) and O(log n)). We present some sufficient conditions for ciphers of this type to be "pseudorandom function generators" and, thus, to yield private key cryptosystems that are secure against adaptive chosen plaintext attacks. ----- File: 1990/tr-90-028 Temporal Resoning with Intervals in Branching Time Peter B. Ladkin, Frank D. Anger, and Rita V. Rodriguez tr-90-028 July 1990 Allen [ALLE83] adapted path-consistency techniques [MACK77] to heuristic reasoning concerning intervals over linear time, by calculating the composition table of binary relations on intervals, and using it in the path-consistency algorithm. We consider here a model of branching time which is dense, unbounded, future branching, without rejoining branches. The algorithm in [ALLE83] works directly with branching-time intervals, provided only that the composition table of the binary branching-time interval relations is used instead of Allen's table [LADK88]. Here we calculate the composition table which has to be used, which is considerably more complex than the table for linear-time intervals. This provides a heuristic, cubic-time algorithm for reasoning with branch-time intervals. ----- File: 1990/tr-90-029 On Location: Points About Regions Peter B. Ladkin and Judith S. Crow tr-90-029 July 1990 In this paper we formalize Whitehead's construction for inducing point structures from region structures using a primitive relation of connection on regions [Whi79]. Our concern is to formulate a spatiotemporal analogue to the construction of temporal periods/points from events, and is reminiscent of the temporal constructions of Kamp [Kam79] and van Benthem [vBen83]. We compare our interpretation of Whitehead with the Kamp/van Benthem/Russell constructions and find some unresolved issues of interdefinability. Our goal is an appposite formulation of spatiotemporal locations as suggested for Situation Theory by Barwise and Perry [BP83]. ----- File: 1990/tr-90-030 On the Magnification of Exchange Graphs with Applications to Enumeration Problems (Thesis) Paul Dagum tr-90-030 July 1990 This thesis concerns the design of fully polynomial approximation algorithms for some #P-complete enumeration problems. The types of enumeration problems we consider can be regarded as instances of computing |F| for set systems (V,F) having a description in terms of a "complete set of implicants" I with |I| = O(|V| superscript 2). By studying the geometric quantities of adjacency and magnification of the "exchange graph" of set systems, we establish criteria for the design of fully polynomial algorithms. ----- File: 1990/tr-90-031 Fault Tolerance in Feed-foward Artificial Neural Networks Carlo H. Sequin and Reed D. Clay tr-90-031 July 1990 The errors resulting from defective units and faulty weights in layered feed-forward ANN's are analyzed, and techniques to make these networks more robust against such failures are discussed. First, using some simple examples of pattern classification tasks and of analog function approximation, it is demonstrated that standard architectures subjected to normal backpropagation training techniques do not lead to any noteworthy fault tolerance. Additional, redundant hardware coupled with suitable new training techniques are necessary to achieve that goal. A simple and general procedure is then introduced that develops fault tolerance in neural networks: The type of failures that one might expect to occur during operation are introduced at random during the training of the network, and the resulting output errors are used in a standard way for backpropagation and weight adjustment. The result of this training method is a modified internal representation that is not only more robust to the type of failures encountered in training, but which is also more tolerant of faults for which the network has not been explicitly trained. ----- File: 1990/tr-90-032 A Note on Self-Testing/Correcting Methods for Trigonometric Functions Richard Cleve and Michael Luby tr-90-032 July 1990 Blum, Luby and Rubinfeld (1990) introduced the notion of self-testing/correcting for various problems. We show how to apply some of their techniques to construct a self-testing/correcting pair for the problem of computing the sin and cos functions. ----- File: 1990/tr-90-033 The Computational Complexity of (XOR, AND)-Counting Problems Andrzej Ehrenfeucht and Marek Karpinski tr-90-033 July 1990 We characterize the computational complexity of counting the exact number of satisfying assignments of (XOR, AND)-formulas in their RSE-representation (i.e., equivalently, polynomials in GF[2] [x subscript 1, ..., x subscript n]. This problem refrained for some time efforts to find a polynomial time solution and efforts to prove the problem to be #P-complete. Both main results can be generalized to the arbitrary finite fields GF[q]. Because counting the number of solutions of polynomials over finite fields is generic for many other algebraic counting problems, the results of this paper settle a border line for the algebraic problems with a polynomial time counting algorithms and for problems which are #P-complete. In [Karpinski, Luby 89] the counting problem for arbitrary multivariate polynomials over GF[2] has been proved to have randomized polynomial time approximation algorithms. ----- File: 1990/tr-90-034 Finite Representations of Deformable Functions Peitro Perona tr-90-034 July 1990 Starting from a `template' function F(x) and composing it with a family of transformations T subscript 0 (e.g., rotations, scalings) of its domain one obtains a family of `deformations' of F, F0T(x) spanning an n-dimensional space; n is in general infinite. A technique is presented that allows (1) to compute the best approximation of a given family using linear combinations of a finite number of `basis' functions; (2) to characterize those functions F generating finite-dimensional families. The technique applies to all cases where T subscript 0 belongs to a compact group of transformations. The results presented here have applications in early vision and signal processing for the computation of filters in a continuum of orientations and scales. ----- File: 1990/tr-90-035 An Introduction to Real-Time Scheduling Ralf Guido Herrtwich tr-90-035 July 1990 Until now, real-time processing techniques were only used in more exotic computer applications such as process automation. With the advent of computer systems capable of handling time-critical data such as digital audio and video, they become important for general-purpose computing as well. Real-time scheduling, i.e., assigning resources to processes in a way that takes the timing requirements of these processes into account, is the single most important technique in the construction of real-time systems. This tutorial introduces the most widely used system models for real-time scheduling, describing resource characteristics, process parameters, and scheduling objectives. It summarizes, illustrates, and verifies essential findings about basic real-time scheduling algorithms such as earliest-deadline-first, least-laxity-first, and rate-monotonic scheduling for both sporadic and periodic processes. ----- File: 1990/tr-90-036 The Goedel Incompleteness Theorem and Decidability over a Ring Lenore Blum tr-90-036 August 1990 Goedel showed in 1931 that given any reasonable (consistent and effective) theory of arithmetic, there are true assertions about the natural numbers that are not theorems in that theory. This "incompleteness theorem" ended Hilbert's program of formalizing mathematics and is rightfully regarded as the most important result in the foundations of mathematics in this century. Now the concept of undecidability of a set plays an important role in understanding Goedel's work. On the other hand, the question of the undecidability of the Mandelbrot set has been raised by Roger Penrose. Penrose acknowledges the difficulty of formulating his question because "decidability" has customarily only dealt with countable sets, not sets of real or complex numbers.
Here we give an exposition of Goedel's result in an algebraic setting and also a formulation (and essentially an answer) to Penrose's problem. The notions of computability and decidability over a ring R underly our point of view. Goedel's Theorem follow from the Main Theorem: There is a definable undecidable set over Z. By way of contrast, Tarski's Theorem asserts that every definable set over the reals or any real closed field R is decidable over R. We show a converse to this result, namely: any sufficiently infinite ordered field with this property is necessarily real closed. ----- File: 1990/tr-90-037 Two Results on the List Update Problem; Sandy Irani tr-90-037 August 1990 In this paper we give a randomized on-line algorithm for the list update problem. Sleator and Tarjan show a deterministic algorithm, Move-to-Front, that achieves competitive ratio of (2L-1)/L for lists of length L. Karp an Raghavan show that no deterministic algorithm can beat 2L/(L+1). We show that Move-to-Front in fact achieves an optimal competitive ratio of 2L/(L+1). We show a randomized algorithm that achieves a competitive ratio of (31 L + 1 )/16(L+1) against an oblivious adversary. This is the first randomized strategy whose competitive factor beats a constant less than 2.
Keywords: Analysis of Algorithms, On-line Algorithms, Competitive Analysis, Amortized Analysis, Linear Lists. ----- File: 1990/tr-90-038 Information-Based Complexity: New Questions for Mathematicians J. F. Traub and H. Woznaikowski tr-90-038 August 1990 [No Abstract] ----- File: 1990/tr-90-039 The Monte Carlo Algorithm with a Pseudo-Random Generator J. F. Traub and H. Woznaikowski tr-90-039 August 1990 We analyze the Monte Carlo algorithm for the approximation of multivariate integrals when a pseudo-random generator is used. We establish lower and upper bounds on the error of such algorithms. We prove that as long as a pseudo-random generator is capable of producing only finitely many points, the Monte Carlo algorithm with such a pseudo-random generator fails for L subscript 2 or continuous functions. It also fails for Lipschitz functions if the number of points does not depend on the number of variables. This is the case if a linear congruential generator is used with one initial seed. On the other hand, if a linear congruential generator of period m is used for each component with independent uniformly distributed initial seeds, then the Monte Carlo algorithm with such a pseudo-random generator using n function values behaves as for the uniform distribution and its expected error is roughly n superscript (-1/2) as long as the number n of function values is less than m superscript 2. ----- File: 1990/tr-90-040 Designing Checkers for Programs that Run in Parallel Ronitt Rubinfeld tr-90-040 August 1990 We extend the theory of program result checking to parallel programs, and find general techniques for designing such result checkers. We find result checkers for many basic problems in parallel computation. We show that there are P-complete problems (evaluating straight-line programs, linear programming) that have very fast (even constant depth) parallel result checkers. Sorting, multiplication, parity, majority and the all pairs shortest path problem all have constant depth result checkers. In addition, the sequential versions of the parallel result checkers given for integer sorting and the all pairs shortest path problems are the first deterministic sequential result checkers for those problems. ----- File: 1990/tr-90-041 Self-Testing/Correcting with Applications to Numerical Problems Manuel Blum, Michael Luby and Ronitt Rubinfeld tr-90-041 August 1990 Suppose someone gives us an extremely fast program P that we can call as a black box to compute a function f. Should we trust that P works correctly? A self-testing/correcting pair for f allows us to: (1) estimate the probability that P(x) is not equal to f(x) when x is randomly chosen; (2) on any input x, compute f(x) correctly as long as P is not too faulty on average. Furthermore, both (1) and (2) take time only slightly more than the original running time of P.
We present general techniques for constructing simple to program self-testing/correcting pairs for a variety of numerical functions, including integer multiplication, modular multiplication, matrix multiplication, inverting matrices, computing the determinant of a matrix, computing the rank of a matrix, integer division, modular exponentiation and polynomial multiplication. ----- File: 1990/tr-90-042 CHCL - A Connectionist Inference System for Horn Logic based on the Connection Method and using Limited Resources Steffen Hoelldobler tr-90-042 August 1990 A connectionist inference system for a class of Horn clauses is presented. The system is based on a connectionist unification algorithm for first-order terms and utilizes Bibel's connection method. The resources of the system are limited in that at most one instance of each clause may be used in a proof. ----- File: 1990/tr-90-043 ODA-Based Data Modeling in Multimedia Systems Ralf Guido Herrtwich and Luca Delgrossi tr-90-043 August 1990 A multimedia system can handle both discrete media (text, graphics) and continuous media (audio, video). The design of a multimedia system comprises processing and data model