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. 000495 Designing Computers to Check Their Work Manuel Blum tr-88-009 1988 11 __ 000006 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. 000496 Knowledge-Intensive Recruitment Learning Joachim Diederich tr-88-010 1988 11 __ 000006 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. 000497 Time, Space and Form in Vision Jerome A. Feldman tr-88-011 1988 12 __ 000006 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). 000498 On a Theory of Computation and Complexity Over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines Lenore Blum, Mike Shub, Steve Smale tr-88-012 1988 12 __ 000006 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. 000499 Program Correctness Checking and the Design of Programs That Check Their Work Manuel Blum, Sampath Kannan tr-88-013 1988 12 __ 000006 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. 000500 Guaranteeing Performance for Real-Time Communication in Wide-Area Networks Domenico Ferrari tr-89-001 1989 01 __ 000006 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. 000501 Pseudo-Random Number Generator From ANY One-Way Function Russell Impagliazzo, Mike Luby tr-89-002 1989 02 __ 000006 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. 000502 Parallel Search for Maximal Independence Given Minimal Dependence Paul Beame, Michael Luby tr-89-003 1989 02 __ 000006 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. 000503 Towards a Theory of Average Case Complexity Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby tr-89-004 1989 02 __ 000006 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. 000504 A Study of Password Security Michael Luby, Charles Rackoff tr-89-005 1989 02 __ 000006 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. 000505 Fault-Tolerant Routing in Hypercube Multicomputers Using Depth-First Search Ming-Syan Chen, Kang G. Shin tr-89-006 1989 02 __ 000006 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. 000506 A Linear-Algorithm for Enumerating Perfect Matchings in Skew Bipartite Graphs Paul Dagum tr-89-007 1989 02 __ 000006 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. 000507 Spreading Activation and Connectionist Models for Natural Language Processing Joachim Diederich tr-89-008 1989 02 __ 000006 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. 000508 Constructive Omega(t(superscript 1.26)) Lower Bound for the Ramsey Number R (3,t) Richard Cleve, Paul Dagum tr-89-009 1989 02 __ 000006 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. 000509 Conceptual Hierarchies in Classical and Connectionist Architecture Alfred Kobsa tr-89-010 1989 02 __ 000006 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. 000510 Preemptive Ensemble Motion Planning on a Tree Greg N. Frederickson, D. J. Guan tr-89-011 1989 03 __ 000006 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. 000511 Nonpreemptive Ensemble Motion Planning on a Tree Greg N. Frederickson, D. J. Guan tr-89-012 1989 03 __ 000006 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. 000512 The Establishment of the International Computer Science Institute in Berkeley, California: Venturing with Norbert Ron Kay tr-89-013 1989 03 __ 000006 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. 000513 Subtree Isomorphism is in Random NC Philip Gibbons, Richard M. Karp, Gary L. Miller, Danny Soroker tr-89-014 1989 03 __ 000006 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. 000514 Planar Graph Decomposition and All Pairs Shortest Paths Greg N. Frederickson tr-89-015 1989 03 __ 000006 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. 000515 Explanation and Connectionist Systems Joachim Diederich tr-89-016 1989 04 __ 000006 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. 000516 Generalization and Parameter Estimation in Feedforward Nets: Some Experiments N. Morgan, H. Bourlard tr-89-017 1989 04 __ 000006 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. 000517 A Parallel Algorithm for Maximum Matching in Planar Graphs Marek Karpinski, Elias Dahlhaus, Andrzej Lingas tr-89-018 1989 04 __ 000006 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. 000518 A More Practical PRAM Model Phillip B. Gibbons tr-89-019 1989 04 __ 000006 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. 000519 Multiple Network Embeddings into Hypercubes Ajay Gupta, Susanne E. Hambrusch tr-89-020 1989 04 __ 000006 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. 000520 Learning Read-Once Formulas Using Membership Queries Lisa Hellerstein, Marek Karpinski tr-89-021 1989 04 __ 000006 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]. 000521 Real-Time Communication in Packet-Switching Wide-Area Networks Domenico Ferrari tr-89-022 1989 05 __ 000006 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. 000522 Approximating the Permanent of Graphs with Large Factors Paul Dagum, Michael Luby tr-89-023 1989 04 __ 000006 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. 000523 An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph Elias Dahlhaus, Marek Karpinski tr-89-024 1989 05 __ 000006 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. 000524 On Parallel Evaluation of Game Trees Richard M. Karp, Yanjun Zhang tr-89-025 1989 05 __ 000006 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. 000525 Separating Abstraction from Implementation in Communication Network Design Ramon Caceres tr-89-026 1989 05 __ 000006 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. 000526 Boolean Circuit Complexity of Algebraic Interpolation Problems Marek Karpinski tr-89-027 1989 05 __ 000006 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. 000527 Application of Real-Time Monitoring to Scheduling Tasks with Random Execution Times Dieter Haban, Kang Shin tr-89-028 1989 05 __ 000006 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. 000528 Behavior and Performance Analysis of Distributed Systems Using a Hybrid Monitor Dieter Haban, Dieter Wybranietz tr-89-029 1989 05 __ 000006 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. 000529 Monitoring and Measuring Parallel Systems Using a Non-Intrusive Rule-Based System Dieter Haban, Dieter Wybranietz tr-89-030 1989 03 __ 000006 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. 000530 One-Way Functions are Essential for Complexity Based Cryptography (Extended ) Russell Impagliazzo, Michael Luby tr-89-031 1989 05 __ 000006 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. 000531 A Connectionist Model of Unification Andreas Stolcke tr-89-032 1989 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1989/tr-89-032.pdf 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. 000532 Merging Multilayer Perceptrons and Hidden Markov Models: Some Experiments in Continuous Speech Recognition Herve Bourlard, Nelson Morgan tr-89-033 1989 05 __ 000006 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. 000533 A Survey of Optical Fibers in Communication Ramesh Govindan, Srinivasan Keshav, Dinesh C. Verma tr-89-034 1989 05 __ 000006 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. 000534 Conjectures on Representations in Backpropagation Networks Paul W. Munro tr-89-035 1989 05 __ 000006 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. 000535 A Scheme for Real-Time Channel Establishment in Wide-Area Networks Domenico Ferrari, Dinesh C. Verma tr-89-036 1989 05 __ 000006 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. 000536 A Tagging Method for Distributed Constraint Satisfaction Hans Werner Guesgen tr-89-037 1989 06 __ 000006 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. 000537 Metric Constraint Satisfaction with Intervals Peter B. Ladkin tr-89-038 1989 06 __ 000006 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. 000538 Fast Parallel Algorithms for the Clique Separator Decomposition Elias Dahlhaus, Marek Karpinski, Mark B. Novick tr-89-039 1989 07 __ 000006 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. 000539 The Possibility of an Executable Specification Language Peter B. Ladkin tr-89-040 1989 07 __ 000006 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. 000540 Geometric Learning Algorithms; Stephen M. Omohundro tr-89-041 1989 06 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1989/tr-89-041.pdf 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. 000541 Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs Elias Dahlhaus, Peter Hajnal, Marek Karpinski tr-89-042 1989 06 __ 000006 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. 000542 Parallel Asynchronous Connected Components in a Mesh Susan Hambrusch, Michael Luby tr-89-043 1989 07 __ 000006 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 000543 Removing Randomness in Parallel Computation Without a Processor Penalty Michael Luby tr-89-044 1989 07 __ 000006 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]. 000544 Parallel Path-Consistency Algorithms for Constraint Satisfaction Peter B. Ladkin, Roger D. Maddux tr-89-045 1989 08 __ 000006 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. 000545 On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials over Finite Fields Michael Clausen, Andreas Dress, Johannes Grabmeier, Marek Karpinski tr-89-046 1989 07 __ 000006 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. 000546 The Transitive Closure of a Random Digraph; Richard M. Karp tr-89-047 1989 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1989/tr-89-047.pdf 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. 000547 Parallel Heuristics for the Steiner Tree Problem in Images without Sorting or Routing Susanne Hambrusch, Lynn TeWinkel tr-89-048 1989 08 __ 000006 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. 000548 Spatial Reasoning Based on Allen's Temporal Logic Hans Werner Guesgen tr-89-049 1989 07 __ 000006
"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. 000549 Learning Read-Once Formulas with Queries Dana Angluin, Lisa Hellerstein, Marek Karpinski tr-89-050 1989 07 __ 000006 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. 000550 A Note on Computational Indistinguishability Oded Goldreich tr-89-051 1989 07 __ 000006 We show that the following two conditions are equivalent:
000551 An Efficient Parallel Algorithm for the 3MIS Problem Elias Dahlhaus, Marek Karpinski tr-89-052 1989 09 __ 000006 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. 000552 Supporting Formal Program Developments: the DEVA Environment Stefan Jahnichen, Robert Gabriel, Matthias Weber, Matthias Anlauff tr-89-053 1989 09 __ 000006 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. 000553 Fast Evaluation of Boolean Formulas by CREW-PRAMs Rudiger Reischuk tr-89-054 1989 09 __ 000006 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. 000554 On the Theory of Average Case Complexity (Revised Edition) Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby tr-89-055 1989 09 __ 000006 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. 000557 Controlled Gradual Disclosure Schemes for Random Bits and Their Applications Richard Cleve tr-89-058 1989 10 __ 000006 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. 000558 Accessing and Customizing Services in Distributed Systems Ralf Guido Herrtwich, Uwe Wolfgang Brandenburg tr-89-059 1989 10 __ 000006 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. 000559 VC Dimension and Learnability of Sparse Polynomials and Rational Functions Marek Karpinski, Thorsten Werther tr-89-060 1989 11 __ 000006 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). 000560 On Space-bounded Learning and the Vapnik-Chervonenkis Dimension (Thesis) Sally Floyd tr-89-061 1989 12 __ 000006 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. 000561 The Asynchronous PRAM: A Semi-Synchronous Model for Shared Memory MIMD Machines (Thesis) Phillip Baldwin Gibbons tr-89-062 1989 12 __ 000006 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. 000562 Five Balltree Construction Algorithms; Stephen M. Omohundro tr-89-063 1989 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1989/tr-89-063.pdf 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. 000563 Program Checkers for Algebraic Problems (Thesis) Sampath Kanan tr-89-064 1989 02 __ 000006 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. 000564 Lectures on a Theory of Computation and Complexity over the Reals (or an Arbitrary Ring) Lenore Blum tr-89-065 1989 12 __ 000006 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. 000565 The Delaunay Triangulation and Function Learning; Stephen M. Omohundro tr-90-001 1990 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-001.pdf 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. 000566 Speech Segmentation and Labeling on the NeXT Machine Chuck Wooters, Nelson Morgan tr-90-002 1990 01 __ 000006 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. 000567 Considerations for the Electronic Implementation of Artificial Neural Networks Nelson Morgan tr-90-003 1990 01 __ 000006 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. 000568 On the Complexity of Genuinely Polynomial Computation Marek Karpinski, Friedhelm Meyer auf der Heide tr-90-004 1990 01 __ 000006 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]. 000569 Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents Dima Y. Grigoriev, Marek Karpinski, Michael F. Singer tr-90-005 1990 01 __ 000006 We present the first algorithm for the (black box) interpolation of t-sparse rational functions without knowing bounds on exponents of their sparse representations. 000570 A Resource Reservation Protocol for Guaranteed-Performance Communication in the Internet David P. Anderson, Ralf Guido Herrtwich, Carl Schaefer tr-90-006 1990 02 __ 000006 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. 000571 Client Requirements for Real-Time Communication Services Domenico Ferrari tr-90-007 1990 03 __ 000006 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. 000572 An Algebraic Approach to General Boolean Constraint Problems Hans W. Guesgen, Peter B. Ladkin tr-90-008 1990 03 __ 000006 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. 000573 Miniature Language Acquisition: A touchstone for cognitive science; Jerome A. Feldman, George Lakoff, Andreas Stolcke, Susan Hollbach Weber tr-90-009 1990 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-009.pdf 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. 000574 L0: A Testbed for Miniature Language Acquisition; Susan Hollbach Weber, Andreas Stolcke tr-90-010 1990 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-010.pdf 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. 000575 A Network for Extracting the Locations of Point Clusters Using Selective Attention; Subutai Ahmad, Stephen Omohundro tr-90-011 1990 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-011.pdf 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. 000576 A Connectionist Unification Algorithm Steffen Hoelldobler tr-90-012 1990 03 __ 000006 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. 000577 Towards Optimal Simulations of Formulas by Bounded-Width Programs Richard Cleve tr-90-013 1990 03 __ 000006 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. 000578 Dynamic Constraints Hans Werner Guesgen, Joachim Hertzberg tr-90-014 1990 04 __ 000006 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. 000579 Learning Feature-based Semantics with Simple Recurrent Networks; Andreas Stolcke tr-90-015 1990 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-015.pdf 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. 000580 Temporal Reasoning Based on Semi-Intervals (Revised Version) Christian Freksa tr-90-016 1990 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-016.pdf 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.]
000581 Time Dated Streams in Continuous-Media Systems Ralf Guido Herrtwich tr-90-017 1990 05 __ 000006 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.
000582 A Connectionist Approach to Symbolic Constraint Satisfaction Hans Werner Guesgen tr-90-018 1990 04 __ 000006 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. 000583 Applications of Topology to Lower Bound Estimates in Computer Science Michael D. Hirsch tr-90-019 1990 05 __ 000006 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. 000585 Structure and Schedulingin Real-Time Protocol Implementations David P. Anderson, Luca Delgrossi, Ralf G. Herrtwich tr-90-021 1990 06 __ 000006 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. 000586 Buffer Space Allocation for Real-Time Channels in a Packet-Switching Network Domenico Ferrari, Dinesh C. Verma tr-90-022 1990 06 __ 000006 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. 000587 On the Power of Randomization in Online Algorithms; S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson tr-90-023 1990 06 __ 000006 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. 000588 An Introduction to Randomized Algorithms; Richard M. Karp tr-90-024 1990 06 __ 000006 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. 000589 Approximating the Number of Solutions of a GF[2] Polynomial Marek Karpinski, Michael Luby tr-90-025 1990 07 __ 000006 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. 000590 Audio and Video in Distributed Computer Systems: Why and How? Ralf Guido Herrtwich tr-90-026 1990 07 __ 000006 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. 000591 Complexity Theoretic Issues Concerning Block Ciphers Related to D.E.S. Richard Cleve tr-90-027 1990 07 __ 000006 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. 000592 Temporal Resoning with Intervals in Branching Time Peter B. Ladkin, Frank D. Anger, Rita V. Rodriguez tr-90-028 1990 07 __ 000006 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. 000593 On Location: Points About Regions Peter B. Ladkin, Judith S. Crow tr-90-029 1990 07 __ 000006 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]. 000594 On the Magnification of Exchange Graphs with Applications to Enumeration Problems (Thesis) Paul Dagum tr-90-030 1990 07 __ 000006 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. 000595 Fault Tolerance in Feed-foward Artificial Neural Networks Carlo H. Sequin, Reed D. Clay tr-90-031 1990 07 __ 000006 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. 000596 A Note on Self-Testing/Correcting Methods for Trigonometric Functions Richard Cleve, Michael Luby tr-90-032 1990 07 __ 000006 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. 000597 The Computational Complexity of (XOR, AND)-Counting Problems Andrzej Ehrenfeucht, Marek Karpinski tr-90-033 1990 07 __ 000006 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. 000598 Finite Representations of Deformable Functions Peitro Perona tr-90-034 1990 07 __ 000006 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. 000599 An Introduction to Real-Time Scheduling Ralf Guido Herrtwich tr-90-035 1990 07 __ 000006 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. 000600 The Goedel Incompleteness Theorem and Decidability over a Ring Lenore Blum tr-90-036 1990 08 __ 000006 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. 000601 Two Results on the List Update Problem; Sandy Irani tr-90-037 1990 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-037.pdf 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. 000602 Information-Based Complexity: New Questions for Mathematicians J. F. Traub, H. Woznaikowski tr-90-038 1990 08 __ 000006 [No Abstract] 000603 The Monte Carlo Algorithm with a Pseudo-Random Generator J. F. Traub, H. Woznaikowski tr-90-039 1990 08 __ 000006 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. 000604 Designing Checkers for Programs that Run in Parallel Ronitt Rubinfeld tr-90-040 1990 08 __ 000006 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. 000605 Self-Testing/Correcting with Applications to Numerical Problems Manuel Blum, Michael Luby, Ronitt Rubinfeld tr-90-041 1990 08 __ 000006 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. 000606 CHCL - A Connectionist Inference System for Horn Logic based on the Connection Method and using Limited Resources Steffen Hoelldobler tr-90-042 1990 08 __ 000006 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. 000607 ODA-Based Data Modeling in Multimedia Systems Ralf Guido Herrtwich, Luca Delgrossi tr-90-043 1990 08 __ 000006 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 modeling aspects. In this paper, we are concerned with data modeling only. We present a proposal to extend the ISO Office Document Architecture (ODA) to accommodate continuous media. To provide media flexibility, the needs for new ODA content architectures are identified. To take into account the timing requirements of continuous-media data, attributes for temporal synchronization are introduced for the logical and layout structure of an ODA document. To consider that multimedia information does not only appeal to the sense of vision, the layout structure is extended from two-dimensional visual space to arbitrary "presentation space". In addition, the inclusion of live information and hypertext features into ODA documents is proposed. 000608 Continuous Speech Recognition on the Resource Management Database Using Connectionist Probability Estimation N. Morgan, C. Wooters, H. Bourlard, M. Cohen tr-90-044 1990 09 __ 000006 Previous work has shown the ability of Multilayer Perceptrons (MLPs) to estimate emission probabilities for a Hidden Markov Model (HMM). The advantage to this approach is the ability to incorporate multiple sources of evidence (features, temporal context) without restrictive assumptions of distribution or statistical independence.
In our earlier publications on this topic, a hybrid MLP/HMM continuous speech recognition algorithm was tested on the SPICOS German-language data base. In our recent work, we have shifted to the speaker-dependent portion of DARPA's English language Resource Management (RM) data base. Both consist of continuous utterances (sentences) and incorporate a lexicon of roughly 1000 words. Preliminary results appear to support the previously reported utility of MLP probability estimation for continuous speech recognition (at least for the case of this simple form of HMM). 000609 SPOONS '90: The SPeech recOgnition frOnt eNd workShop N. Morgan H. Hermansky, C. Wooters tr-90-045 1990 09 __ 000006 An appropriate input representation is crucial for pattern classification. In spite of this, we find that feature extraction, transformation, and selection tend to be under-represented aspects of the speech recognition literature. Therefore, the authors decided to gather together a group of interested parties for a dialog on the subject. We ultimately invited a group of about 30 researchers, and on July 6, 1990, held a 1-day workshop which we called SPOONS. This document is a brief summary of that day, including the abstract for each talk. 000610 Space-Frequency Distributions in the Analysis and Modeling of Early Vision Gabriel Cristobal tr-90-046 1990 09 __ 000006 The use of the joint space-spatial frequency representations has recently received considerable attention; especially in those areas of science and engineering where nonstationary signals appear. In that case, local energy distribution representations based in the local spectra computation would be more appropriate. The Wigner Distribution (WD) which gives a joint representation in the space and spatial frequency domain entails a rigorous mathematical framework in the study of these local representations. In this paper, texture recognition is performed through the extraction of features from the WD and a comparative study with other methods is presented. A review of the state-of-the-art of the joint representations in different areas of research namely signal, speech and vision processing is presented. Afterwards, the importance of these distributions in the modeling of early vision processes is considered, and a brief review about the physiological findings is presented in order to have a quantitative measure of the degree of biological plausibility. 000611 The Ring Array Processor (RAP): Algorithms and Architecture Nelson Morgan tr-90-047 1990 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-047.pdf We have designed and implemented a Ring Array Processor (RAP) for fast implementation of our continuous speech recognition training algorithms which are currently dominated by layered neural network calculations. The RAP is a multi-DSP system with a low-latency ring interconnection scheme using programmable gate array technology and a significant amount of local memory per node (4-16 MBytes of dynamic memory and 256 KByte of fast static RAM). Theoretical peak performance is 128 MFlops/board, and test runs with the first working board show a sustained throughput of roughly 30-90 percent of this for algorithms of current interest.
This report describes the motivation for the RAP design, and shows how the architecture matches the target algorithm. Technical reports from other members of the RAP team focus on the hardware and software specifics for the system. 000612 The Ring Array Processor (RAP): Hardware; J. Beck tr-90-048 1990 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-048.pdf The ICSI Ring Array Processor, or RAP, is a system of hardware and software specifically designed for our research in speech processing using neural networks. This technical report describes the RAP hardware, paying particular attention to the features that may be unusual in a system of this type. Other features and design decisions that facilitated realization of the RAP are also described. Technical reports from other members of the RAP team focus on the architecutre and algorithms of the RAP, and the software specifics for the system. 000613 Ring Array Processor (RAP): Software User's Manual Version 1.0; P. Kohn, J. Bilmes tr-90-049 1990 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-049.pdf The RAP machine is a high performance parallel processor developed at ICSI as described in previous technical reports. This report documents the RAP software environment. It is intended for the moderately experienced C programmer who wishes to program the RAP. The RAP software environment is very similar to the UNIX C programming environment. However, there are some differences arising from the hardware that the programmer must keep in mind. Also described is the RAP library which contains hand-optimized matrix, vector and inter-processor communications routines. Single Program Multiple Datastream (SPMD) programs can be developed under UNIX with a simulated RAP library and then recompiled to run on the RAP. 000614 Ring Array Processor (RAP): Software Architecture; Jeff Bilmes, Phil Kohn tr-90-050 1990 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1990/tr-90-050.pdf The design and implementation of software for the Ring Array Processor (RAP), a high performance parallel computer, involved development for three hardware platforms: Sun SPARC workstations, Heurikon MC68020 boards running the VxWorks real-time operating system, and Texas Instruments TMS320C30 DSPs. The RAP now runs in Sun workstations under UNIX and in a VME based system using VxWorks. A flexible set of tools has been provided both to the RAP user and programmer. Primary emphasis has been placed on improving the efficiency of layered artificial neural network algorithms. This was done by providing a library of assembly language routines, some of which use node-custom compilation. An object-oriented RAP interface in C++ is provided that allows programmers to incorporate the RAP as a computational server into their own UNIX applications. For those not wishing to program in C++, a command interpreter has been built that provides interactive and shell-script style RAP manipulation. 000615 Characterizing the Variability of Arrival Processes with Indices of Dispersion Riccardo Gusella tr-90-051 1990 09 __ 000006 We propose to characterize the burstiness of packet arrival processes with indices of dispersion for intervals and for counts. These indices, which are functions of the variance of intervals and counts, are relatively straightforward to estimate and convey much more information than simpler indices, such as the coefficient of variation, that are often used to describe burstiness quantitatively.
We define and evaluate the indices of dispersion for some of the simple analytical models that are frequently used to represent highly variable processes. We then estimate the indices for a number of measured point processes which were generated by workstations communicating to file servers over a local-area network.
We show that nonstationary components in the measured packet arrival data distort the shape of the indices and propose ways to handle nonstationary data. Finally, to show how to incorporate measures of variability into analytical models and to offer an example of how to model our measured packet arrival processes, we describe a fitting procedure based on the index of dispersion for counts for the Markov-modulated Poisson process. 000616 On Semi-Algebraic Decision Complexity Thomas Lickteig tr-90-052 1990 09 __ 000006 The topic of this paper is the lower bound question for composition trees that solve certain semialgebraic decision problems. 000617 A Pipelining Model Which Pipelines Blocks of Code Joachim Beer tr-90-053 1990 10 __ 000006 This paper presents a new technique of software pipelining and an architecture to support this technique. Rather than attempting to pipeline a sequence of individual instructions, the presented technique tries to pipeline entire blocks of code, i.e. the units to be pipelined are chunks of code, instructions within each code block might or might not be pipelined themselves. In this model blocks of code are identified which can be executed in a pipelined fashion. Neighboring blocks of code do not need to be data independent; pipeline stages can feed results and/or synchronization markers on to the next pipeline stage. The architecture can be seen as an attempt to use classical pipelining techniques in a multiprocessor system. The architecture consists of a circular pipeline of ordinary microprocessors. Advantages of the architecture are: unlike supercomputers and VLIW architectures the system can be based on commercial micro-processors, it avoids the high overhead of process startup, and it is not restricted to vectorizing only inner-loops. Simulation studies show the viability of the architecture and the associated execution model. 000618 A Mathematical Theory of Self-Checking, Self-Testing and Self-Correcting Programs (Thesis) Ronitt Rubinfeld tr-90-054 1990 10 __ 000006 Suppose someone gives us an extremely fast program P that we can call as a black box to compute a function f. Rather than 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) require only a small multiplicative overhead (usually constant) over the running time of P. A program result checker for f (as introduced by Manuel Blum) allows us to check that on particular input x, P(x) = f(x).
We present general techniques for constructing simple to program self-testing/correcting pairs for a variety of numerical functions. The self-testing/correcting pairs introduced for many of the problems are based on the property that the solution to a particular instance of the problem can be expressed as the solution to a few random instances of the same size. An important idea is to design self-testing/correcting pairs for an entire library of functions rather than for each function individually.
We extend these notions and some of the general techniques to check programs for some specific functions which are only intended to give good approximations to f(x). We extend the above models and techniques of program result checking and self-testing/correcting to the case where the behavior of the program is modelled as being adaptive, i.e., the program may not always give the same answer on a particular input. These stronger checkers provide multi-prover interactive proofs for these problems.
The theory of checking is also extended to parallel programs [Rubinfeld]. We construct parallel checkers for many basic problems in parallel computation.
We show that for some problems, result checkers that are much more efficient can be constructed if the answers are checked in batches, i.e., many answers are checked at the same time. For these problems, the multiplicative overhead of checking the result can be made arbitrarily small. 000619 ICSIM: Initial Design of An Object-Oriented Net Simulator Heinz W. Schmidt tr-90-055 1990 10 __ 000006 ICSIM is a connectionist net simulator being developed at ICSI. It is object-oriented to meet the requirements for flexibility and reuse of models and to allow the user to encapsulate efficient customized implementations perhaps running on dedicated hardware. Nets are composed by combining off-the-shelf library classes and, if necessary, by specializing some of their routines.
The report gives an overview of the simulator. The class structure and some important design decisions are sketched and a number of example nets are used to illustrate how net structure, connectivity and behavior are defined. 000620 How Fast Can A Threshold Gate Learn? Wolfgang Maass, Gyoergy Turan tr-90-056 1990 10 __ 000006 It is shown that a threshold gate with d Boolean input variables can learn any halfspace in polynomially in d many steps in the common on-line learning model (worst case analysis). This is achieved by a computationally feasible learning algorithm that exploits geometrical properties in the version space. This positive result can be extended to the case of input variables that range over {0,...,n-1}, and to threshold gates with more than two different output values (these gates can learn arbitrary discrete approximations to sigmoid threshold functions).
On the other hand we show that all known distributed learning algorithms for threshold gates (delta-rule, WINNOW 1, WINNOW 2) are inherently slow. 000621 Learning Spatial Terms without Explicit Negative Instances Terry Regier tr-90-057 1990 10 __ 000006 A method is presented for learning to associate scenes with spatial terms, in the absence of explicit negative instances, using error back-propagation. A straightforward approach, in the learning of a given term, is to take all positive instances for any other term to be implicit negative instances for the term in question. While this approach is inadequate, a variation on it is shown to work well: error signals from implicit negative instances are attenuated, so that an implicit negative instance will have less effect on the network's weights than will a positive instance of the same error magnitude. It is also shown that "a priori" knowledge of which pairs of spatial terms are antonyms facilitates the learning process. 000622 A Theory of Computation and Complexity over the Real Numbers Lenore Blum tr-90-058 1990 10 __ 000006 The classical theory of computation and complexity presupposes all underlying spaces are countable and hence ipso facto cannot handle arbitrary sets of real or complex numbers. Thus e.g., Penrose (1990) acknowledges the difficulty of formulating classically his question: Is the Mandelbrot set recursive? On the other hand, this as well as a number of other inherent questions of decidability and computability over the reals or complex number can be naturally posed and settled within the framework presented in this paper. 000623 Constraint Reasoning With Intervals: A Tutorial, Survey and Bibliography Peter B. Ladkin tr-90-059 1990 11 __ 000006 A version of this work was presented at the 1990 Berkeley Workshop on Temporal and Real-Time Specification, held at ICSI, Berkeley. In Part I, we present a short tutorial on constraint reasoning with time intervals, of the sort initially introduced by James Allen, and continued by many others. The tutorial concentrates on the general mathematical expression of common algorithms, in particular path-consistency algorithms, for constraint satisfaction using the thirteen interval relations. We use the relation algebra of Tarski to express the important concepts. In Part II, we survey important research in this field to date, focusing on mathematical results and algorithms for reasoning directly with intervals, although we do attempt to include as much literature as the author is aware of. Part III is a select bibliography. Three appendices include the mathematical background, and the operation tables for the Point Algebra and Interval Algebra, which form the focus of Part I. 000624 Proceedings of the Berkeley Workshop on Temporal and Real-Time Specification, August 9-10, 1990 P. B. Ladkin, F. H. Vogt tr-90-060 1990 11 __ 000006 This report contains papers presented by participants at the workshop, with an introduction, a participant list, a synopsis of the workshop, and a short summary of the problem session discussion. The workshop brought together practitioners with different interests in temporal and real-time specification, from simulation, testing and verification to theoretical issues such as relative strengths of theories. The papers concern interval logic, theories of intervals, real-time temporal logic and automata, a real-time systems simulation language, and a causality problem in robot motion planning. 000625 Stochastic Model-Based Image Segmentation Using Markov Random Fields and Multi-layer Perceptrons Jun Zhang, Nelson Morgan tr-90-061 1990 11 __ 000006 Recently, there has been much interest in Markov random field (MRF) model-based techniques for image (texture) segmentation. MRF models are used to enforce reasonable physical constraints on segmented regions, such as the continuity of the regions, and have been shown to improve segmentation results. However, in these techniques, parametric probability models which do not have sufficient physical justifications are often used to model observed image data because they are computationally tractable. In this paper, we outline an MRF approach to image segmentation in which the probability distribution of observed image data is modeled by using a multi-layer perceptron (MLP) which can "learn" the distribution from training data. Furthermore, we propose a technique to achieve unsupervised image segmentation using this approach. We hope that this will improve the current MRF image segmentation techniques by providing a better model for observed image data. 000626 Proceedings of the First International Workshop on Network Operating System Support for Digital Audio and Video [Proceedings Editor] tr-90-062 1990 11 __ 000006 Held at the International Computer Science Institute November 8-9, 1990. 000627 A Monte-Carlo Algorithm for Estimating the Permanent; N. Karmarkar, R. Karp, R. Lipton, L. Lovasz, M. Luby tr-90-063 1990 11 __ 000006 Let $A$ be an $n \times n$ matrix with 0-1 valued entries, and let $\PER(A)$ be the permanent of $A$. We describe a Monte-Carlo algorithm which produces a ``good in the relative sense'' estimate of $\PER(A)$ and has running time $\POLY(n) 2^{n/2}$, where $\POLY(n)$ denotes a function that grows polynomially with $n$.
Key Words: permanent, matching, Monte-Carlo algorithm, algorithm, bipartite graph, determinant. 000628 Quality of Service in ATM Networks Domenico Ferrari, Dinesh Verma tr-90-064 1990 12 __ 000006 B-ISDN networks of the future will have to handle traffic with a wide range of traffic characteristics and performance requirements. In view of the high bandwidth of these networks and the relatively large propagation delays involved in wide-area B-ISDN networks, the performance requirements can only be provided by reserving resources to communicating clients at the connection establishment time. However, reservation mechanisms for heterogenous bursty traffic usually result in a rather poor utilization of network resources.
In this paper, we propose a simple admission control criterion that can be used to reserve resources for bursty as well as smooth traffic with delay and loss sensitivities. Our scheme leads to a reasonable value of the maximum utilization of network bandwidth (about 40 percent) for delay sensitive traffic with moderate burstiness (peak-to-average bandwidth ratios of about 4), even under the worst possible conditions. Actual utilizations can be higher if there is smooth traffic or traffic which is not delay-sensitive. Our admission control algorithm uses a well-defined traffic specification scheme which is easy to enforce and verify, and able to accommodate arbitrary degrees of burstiness. Extensive simulation experiments failed to show that our admission control criterion are incorrect, in the sense that the quality of service requirements of the traffic was always met,even in the worst case. Moreover, the scheme is simple and feasible at the high speeds required of B-ISDN networks. 000629 Developments in Digital VLSI Design for Artificial Neural Networks Nelson Morgan, Krste Asanovic, Brian Kingsbury, John Wawrzynek tr-90-065 1990 12 __ 000006 Artificial Neural Networks (ANNs) have been heralded as a form of massive parallelism that may significantly advance the state of the art in machine intelligence and perception. While these expectations may or may not be realistic, this class of algorithms has already been useful for difficult problems in signal processing and pattern recognition over the last 25 years. However, for extension to a wider class of problems, a key requirement is the parallel hardware implementation of such systems, since ANN implementation on conventional Von Neumann machines is often prohibitively slow. While the ANN mainstream has focused on analog VLSI ANNs, some projects have shown the potential of a fully digital approach. We report here on progress in developing a methodology for digital ANN design, including a new object-oriented CAD interface, and a set of ANN-specific library cells. A new measure for efficiency of silicon ANNs is also described. 000630 Automatic Worst Case Complexity Analysis of Parallel Programs Wolf Zimmermann tr-90-066 1990 12 __ 000006 This paper introduces a first approach for the automatic worst case complexity analysis. It is an extension of previous work on the automatic complexity analysis of functional programs. The language is a first order parallel functional language which allows the definition of indexed data types and parallel execution of indexed terms. The machine model is a parallel reduction system based on eager evaluation. It is shown how parallel programs based on the basic design principles balanced binary tree technique, divide-and-conquer technique and pointer jumping technique can be analyzed automatically. The analysis techniques are demonstrated by various examples. Finally it is shown that an average case analysis of parallel programs is difficult. 000631 The Mean Field Theory in EM Procedures for Markov Random Fields Jun Zhang tr-91-001 1991 01 __ 000006 The EM (expectation maximization) algorithm is a maximum-likelihood parameter estimation procedure for incomplete data problems in which part of the data is hidden, or unobservable. In many signal processing and pattern recognition applications, the hidden data are modeled as Markov processes and the main difficulty of using the EM algorithm for these applications is the calculation of the condition expectations of the hidden Markov processes. In this paper, we show how the mean field theory from statistical mechanics can be used to efficiently calculate the conditional expectations for these problems. The efficacy of the mean field theory approach is demonstrated on the parameter estimation for one-dimensional mixture data and two-dimensional unsupervised stochastic model-based image segmentation. Experimental results indicate that in the 1-D case, the mean field theory approach provides comparable results to those obtained by Baum's algorithm, which is known to be optimal. In the 2-D case, where Baum algorithm can no longer be used, the mean field theory provides good parameter estimates and image segmentation for both synthetic and real-world images. 000632 Protocols for Providing Performance Guarantees in a Packet Switching Internet Carlyn M. Lowery tr-91-002 1991 01 __ 000006 As advances in technology enable us to implement very high speed computer networks, we expect to use our networks for more diverse applications. While the Internet was designed with textual data processing in mind, future networks will carry information such as voice, music, images, and video, along with textual data. Many new applications will have real-time performance requirements, where the timing of data arrival is crucial to its usefulness.
This paper describes a methodology developed at the University of California at Berkeley to support such applications, reviews related research work, and proposes a real-time delivery system, composed of a new protocol for administration of real-time connections, combined with modifications to the Internet Protocol (IP) to support such connections. Transport protocol requirements are also discussed. This work is intended to facilitate experiments with real-time communication over the Experimental University Network (XUNET). 000633 On-Line Learning with an Oblivious Environment and the Power of Randomization Wolfgang Maass tr-91-003 1991 01 __ 000006 A new model for on-line learning is introduced. In this model the environment is assumed to be "oblivious" to the learner: it supplies an arbitrary (not necessarily random) sequence of examples for the target concept which does not depend on the sequence of hypotheses of the learner. This model provides a framework for the design and analysis of on-line learning algorithms which acquire information not just from counter examples, but also from examples which "support" their current hypothesis. It is shown that for various concept classes C an arbitrary target concept from C can be learned in this model by a randomized learning algorithm (which uses only hypotheses from C) with substantially fewer prediction errors than in Angluin's classical model for on-line learning with an adaptive worst-case environment. In particular any target-setting of weights and threshholds in a feed forward neural net can be learned by a randomized learning algorithm in this model with an expected number of prediction errors that is polynomial in the number of units of the neural net.
For comparison we also examine the power of randomization for Angluin's model for learning with an adaptive environment. 000634 Real-Time Transmission and Software Decompression of Digital Video in a Workstation K. Umemura, A. Okazake tr-91-004 1991 01 __ 000006 This paper describes an experiment in which compressed video data is transformed via Ethernet to a workstation, and uncompressed and displayed on the workstation. The workstation has no special hardware. The video data is 192x114 pixel gray scale, 30 frames per second. The data consists of a human speaker with a static background. It is displayed on monochrome display, with dithering, in a 768x576 rectangle. This decompression and display uses about 10 MIPS. The quality of output is suitable for applications such as conferencing, telephony, and presentations. 000635 Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication Peter Buergisser, Marek Karpinski, Thomas Lickteig tr-91-005 1991 01 __ 000006 We define the complexity of a computational problem given by a relation using the model of a computation tree with Ostrowski complexity measure. To a sequence of problems we assign an exponent similar as for matrix multiplication. For the complexity of the following computational problems in linear algebra:
In this paper, we study the feasibility of bounding the delay jitter for real-time channels in a packet-switched store-and-forward wide-area network with general topology, extending the scheme proposed in the previous papers. We prove the correctness of our solution, and study its effectiveness by means of simulations. The results show that the scheme is capable of providing a significant reduction in delay jitter, that there is no accumulation of jitter along the path of a channel, and that jitter control reduces the buffer space required in the network significantly. 000638 A Study of I/O Architecture for High Performance Next Generation Computers Anurag Sah, Vojin G. Oklobdjiza, Dinesh C. Verma tr-91-008 1991 01 __ 000006 We describe an I/O architecture for a high performance next generation computer. The architecture proposed in this paper makes special provisions for communication networks. In order to allow for the expected multi-media and time-critical components of future computer usage, we propose the concept of "Illogical buses" which gives the illusion that there are a number of dedicated buses between the components of a system. A logical bus has a number of performance parameters associated with it, and the system architecture ensures that the performance parameters for each logical bus are satisfied during the operation of the system. 000639 Bumptrees for Efficient Function, Constraint, and Classification Learning Stephen M. Omohundro tr-91-009 1991 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-009.pdf A new class of data structures called "bumptrees" is described. These structures are useful for efficiently implementing a number of neural network related operations. An empirical comparison with radial basis functions is presented on a robot arm mapping learning task. Applications to density estimation, classification, and constraint representation and learning are also outlined. 000640 How Receptive Field Parameters Affect Neural Learning Stephen M. Omohundro, Bartlett W. Mel tr-91-010 1991 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-010.pdf We identify the three principle factors affecting the performance of learning by networks with localized units: unit noise, sample density, and the structure of the target function. We then analyze the effect of unit receptive field parameters on these factors and use this analysis to propose a new learning algorithm which dynamically alters receptive field properties during learning. 000641 Algorithms for Sparse Rational Interpolation Dima Grigoriev, Marek Karpinski tr-91-011 1991 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-011.pdf We present two algorithms on sparse rational interpolation. The first is the interpolation algorithm in a sense of the sparse partial fraction representation of rational functions. The second is the algorithm for computing the entier and the remainder of a rational function. The first algorithm works without apriori known bound on the degree of a rational function, the second one is in the class NC provided the degree is known. The presented algorithms complement the sparse interpolation results of [Grigoriev, Karpinski, and Singer (1990)].
Keywords: Algorithms, NC-Class, Sparse Rational Interpolation, Fraction Representation. 000642 On Distributed Representation in Word Semantics Burghard B. Rieger tr-91-012 1991 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-012.pdf The dualism of the rationalistic tradition of thought is sketched in view of the "semiotic problem" of meaning constitution. Being a process of cognition which is based upon communicative interaction by signs, their usages (in linear order and selective combination), constitute language structures. Other than "symbolic" representational formats employed so far in natural language processing by machine, it is argued here that "distributional" representations correspond directly to the way word meanings are constituted and understood (as fuzzy structures of world knowledge) by (natural and artificial) information processing systems. Based upon such systems' theoretical performance in general and the pragmatics of communicative interaction by real language users in particular, the notions of "situation" and "language game" as introduced by Barwise/Perry and Wittgenstein respectively are combined to allow for a numerical reconstruction of processes that simulate the constitution of meaning and the interpretation of signs. This is achieved by modelling the linear or "syntagmatic" and selective or "paradigmatic" constraints which natural language structure imposes on the formation of (strings of) linguistic entities. A formalism, a related algorithm, and test results of its implementation are given in order to substantiate the claim for an artificial "cognitive information processing system" (CIPS) that operates in a linguistic environment as some meaning acquisition and understanding device. 000643 Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko tr-91-013 1991 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-013.pdf Symbolic manipulation of sparse polynomials, given as lists of exponents and nonzero coefficients, appears to be much more complicated than dealing with polynomials in dense encoding (see e.g. [GKS 90, KT 88, P 77a, P 77b]). The first results in this direction are due to Plaisted [P 77a, P 77b], who proved, in particular, the NP-completeness of divisibility of a polynomial x**n-1 by a product of sparse polynomials. On the other hand, essentially nothing nontrivial is known about the complexity of the divisibility problem of two sparse integer polynomials. (One can easily prove that it is in PSPACE with the help of [M 86].) Here we prove that nondivisibility of two sparse multivariable polynomials is in NP, provided that the Extended Riemann Hypothesis (ERH) holds (see e.g. [LO 77]).
The divisibility problem is closely related to the rational interpolation problem (whose decidability and complexity bound are determined in [GKS 90]). In this setting we assume that a rational function is given by a black box for evaluating it. We prove also that the problem of deciding whether a rational function given by a black box equals a polynomial belongs to the parallel class NC, provided the ERH holds and moreover, that we know the degree of some sparse rational representation of it.
Keywords: Algorithms, NC-Class, Symbolic Manipulation, Nondivisibility, Short Proofs, Extended Riemann Hypothesis. 000644 Computational Complexity of Learning Read-Once Formulas over Different Bases Lisa Hellerstein, Marek Karpinski tr-91-014 1991 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-014.pdf We study computational complexity of learning read-once formulas over different boolean bases. In particular we design a polynomial time algorithm for learning read-once formulas over a threshold basis. The algorithm works in time O(n**3) using O(n**3) membership queries. By the result of [Angluin, Hellerstein, Karpinski, 1989] on the corresponding unate class of boolean functions, this gives a polynomial time learning algorithm for arbitrary read-once formulas over a threshold basis with negation using membership and equivalence queries. Furthermore we study the structural notion of nondegeneracy in the threshold formulas generalizing the result of [Heiman, Newman, Wigderson, 1990] on the uniqueness of read-once formulas over different boolean bases and derive a negative result on learnability of nondegenerate read-once formulas over the basis (AND, XOR).
Keywords: Computational Complexity, Learning Algorithms, Read-Once Formulas, Queries. 000645 A Control-Theoretic Approach to Flow Control Srinivasan Keshav tr-91-015 1991 03 __ 000006 This paper presents a control-theoretic approach to reactive flow control in networks that do not reserve bandwidth. We assume a round-robin-like queue service discipline in the output queues of the network's switches, and propose deterministic and stochastic models for a single conversation in a network of such switches. We then construct a standard time-invariant linear model for the simplified dynamics of the system. This is used to design an optimal (Kalman) state estimator, a heuristic second-order state estimator as well as a provably stable rate-based flow control scheme. Finally, schemes for correcting parameter drift and for coordination with window flow control are described. 000646 Parallel Priority Queues Maria Cristina Pinotti, Geppino Pucci tr-91-016 1991 03 __ 000006 This paper introduces the Parallel Priority Queue (PPQ) abstract data type. A PPQ stores a set of integer-valued items and provides operations such as insertion of n new items or deletion of the n smallest ones. Algorithms for realizing PPQ operations on an n-processor CREW-PRAM are based on two new data structures, the n-Bandwidth-Heap (n-H) and the n-Bandwidth-Leftist-Heap (n-L), that are obtained as extensions of the well known sequential binary-heap and leftist-heap, respectively. Using these structures, it is shown that insertion of n new items in a PPQ of m elements can be performed in parallel time O(h+logn), where h=log(m/n), while deletion of the n smallest items can be performed in time O(h+loglogn). 000647 Optimal Adaptive K-means Algorithm with Dynamic Adjustment of Learning Rate Chedsada Chinrungrueng, Carlo Sequin tr-91-017 1991 03 __ 000006 Adaptive k-means clustering algorithms have been used in several artificial neural network architectures, such as radial basis function networks or feature-map classifiers, for a competitive partitioning of the input domain. This paper presents a modification of the traditional k-means algorithm. In approximates an optimal clustering solution with an efficient adaptive learning rate, which renders it usable even in situations where the statistics of the problem task slowly varies with time. This modification is based on the optimality criterion for the k-means partition stating that all of the region in the optimal k-means partition have the same "within- cluster variation" when the number of regions in the partition is large and the underlying distribution for generating input patterns is smooth. The within-cluster variation of any cluster is defined as the expectation of the squared Euclidean distance between pattern vectors in that cluster and the center of that cluster. Simulations comparing this improved adaptive k-means algorithm with other k-means variants are presented. 000648 Computational Complexity of Sparse Rational Interpolation Dima Grigoriev, Marek Karpinski, Michael F. Singer tr-91-018 1991 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-018.pdf We analyze the computational complexity of sparse rational interpolation, and give the first genuine time (arithmetic complexity does not depend on the size of the coefficients) algorithm for this problem.
Keywords: Computational Complexity, Algorithms, Arithmetic Complexity, Sparse Rational Interpolation. 000649 Probabilistic Recurrence Relations Richard M. Karp tr-91-019 1991 03 __ 000006 This paper is concerned with recurrence relations that arise frequently in the analysis of divide-and-conquer algorithms. In order to solve a problem instance of size $x$, such an algorithm invests an amount of work $a(x)$ to break the problem into subproblems of sizes $h_1(x),h_2(x),\ldots,h_k(x)$, and then proceeds to solve the subproblems. Our particular interest is in the case where the sizes $h_i(x)$ are random variables; this may occur either because of randomization within the algorithm or because the instances to be solved are assumed to be drawn from a probability distribution. When the $h_i$ are random variables the running time of the algorithm on instances of size $x$ is also a random variable $T(x)$. We give several easy-to-apply methods for obtaining fairly tight bounds on the upper tails of the probability distribution of $T(x)$, and present a number of typical applications of these bounds to the analysis of algorithms. The proofs of the bounds are based on an interesting analysis of optimal strategies in certain gambling games. 000650 The Design of a File System that Supports Multimedia Vassilios G. Polimenis tr-91-020 1991 03 __ 000006 A multimedia file system is one that can support real-time sessions as well as normal disk traffic. When a request for a real-time session is accepted, the file system guarantees that, as long as the system does not crash and the user process reads or writes data at most as fast as the initially specified rate, starvation will never occur.
It is shown that the only hard requirement for the acceptance of a set of real-time sessions are that there is enough disk bandwidth and buffer space. A rigorous discussion of these requirements as well as the various parameters that affect the system's behaviors are presented.
Finally and most importantly, a scheduler that uses this theory to schedule the various disk transfers is designed. The scheduler guarantees the non-starvation for multimedia sessions and also that interactive (non-real-time) jobs will experience acceptable response delays. 000651 Generalized Compact Multigrid (REVISED) Victor Pan, John Reif tr-91-021 1992 12 __ 000006 Extending our recent work, based on the ideas of the multigrid iteration, we decrease the storage space for a smooth solution of a nonlinear PDE and, furthermore, for any smooth function on a multidimensional grid and on discretization sets other than grids. 000652 An (epsilon, delta)--Approximation Algorithm of the Number of Zeros for a Multilinear Polynomial over GF[q] Marek Karpinski, Barbara Lhotzky tr-91-022 1991 03 __ 000006 We construct a polynomial time (epsion, delta)-approximation for estimating the number of zeros of an arbitrary multi-linear polynomial f((x subscript 1), ..., (x subscript n)) over GF[q]. This extends the recent result of Karpinski/Luby [KL90] on approximating the number of zeros of polynomials over the field GF[2]. 000653 On the Average Case Complexity of Parallel Sublist Selection Geppino Pucci, Wolf Zimmerman tr-91-023 1991 03 __ 000006 The "Sublist Selection Problem" (SSP) is the following: Given an input list of nodes labelled True or False, extract the sublist of nodes labelled True. This paper analyzes the average case complexity of a parallel algorithm that solves SSP on the PRAM model of computation. The algorithm is based on the well-known "recursive doubling" technique. Doubly logarithmic upper and lower bounds are derived for the average number of iterations needed to produce the output list, under the assumption that all the nodes of the input list are marked False with prabability p, independently of the other nodes. Finally, the exact number of iterations (up to lower order terms) is established in the case that the input list is drawn from the uniform distribution over all possible labelings. 000654 Large Comparison of Rate-Based Service Disciplines Hui Zhang, Srinivasan Kesahv tr-91-024 1991 04 __ 000006 This paper compares six new queue service disciplines that are implemented at the output queues of switches in a connection-oriented packet switched data network. These are Virtual Clock, Fair Queueing, Delay-Earliest-Due-Date, Jitter-Earliest-Due-Date, Stop-and-Go and Hierarchical Round Robin. We describe their mechanisms, their similarities and differences, and some implementation strategies. In particular, we show why each discipline can or cannot provide bandwidth, delay and delay jitter guarantees. This leads to some interesting conclusions about the relative strengths and weaknesses of each approach. 000655 Limiting Fault-Induced Output Errors In ANNs Reed D. Clay, Carlo H. Sequin tr-91-025 1991 04 __ 000006 The worst case output errors produced by the failure of a hidden neuron in layered feed-forward ANNs are investigated. These errors can be much worse than simply the loss of the contribution of a neuron whose output goes to zero. A much larger erroneous signal can be produced when the failure sets the value of the hidden neuron to one of the power supply voltages.
A new method is investigated that limits the fractional error in the output signal of a feed-forward net due to such saturated hidden unit faults in analog function approximation tasks. The number of hidden units is significantly increased, and the maximal contribution of each unit is limited to a small fraction of the net output signal. To achieve a large localized output signal, several Gaussian hidden units are moved into the same location in the input domain and the gain of the linear summing output unit is suitably adjusted. Since the contribution of each unit is equal in magnitude, there is only a modest error under any possible failure mode. 000656 [REVISED:] New Resultant Inequalities and Complex Polynomial Factorization (formerly known as "Randomized Incomplete Numerical Factorization of a Polynomial Over the Complex Field") Victor Pan tr-91-026 1992 12 __ 000006 We deduce some new probabilistic estimates on the distances between the zeroes of a polynomial p(x) by using some properties of the discriminant of p(x) and apply these estimates to improve the fastest deterministic algorithm for approximating polynomial factorization over the complex field. 000657 An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] Dima Grigoriev, Marek Karpinski tr-91-027 1991 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-027.pdf We design the first polynomial time (for an arbitrary and fixed field GF[q]) (epsilon,delta)-approximation algorithm for the number of zeros of arbitrary polynomial f(x_1, ... ,x_n) over GF[q].It gives the first efficient method for estimating the number of zeros and nonzeros of multivariate polynomials over small finite fields other than GF[2] (like GF[3]), the case important for various circuit approximation techniques. The algorithm is based on the estimation of the number of zeros of an arbitrary polynomial f(x_1, ... ,x_n) over GF[q] in the function on the number m of its terms. The bounding ratio number is proved to be m**((q-1) log q) which is the main technical contribution of this paper and could be of independent algebraic interest.
Keywords: Approximation Algorithms, Counting Problems, Multivariate Polynomials, Finite Fields. 000658 The Packet Pair Flow Control Protocol Srinivasan Keshav tr-91-028 1991 05 __ 000006 This paper presents a reactive flow control mechanism for networks that do not reserve bandwidth. We assume a round-robin-like Fair Queueing service discipline in the output queues of switches and routers, which enables us to model a conversation as a sequence of D/D/1 queues. This model is used to derive a rate-based flow control protocol called Packet-pair, or 2P. 2P uses short packet bursts to estimate the service rate of a conversation at its bottleneck, and to adapt its sending rate to the network state. We describe the design and impementation of 2P in detail. Simulations compare the scheme with some well known flow control schemes in deterministic as well as stochastic scenarios. Anaysis and simulations indicate that 2P is able to use available bandwidth efficiently and to achieve low queueing delays, particulary in networks where the bandwidth-delay product is large. Further, 2P responds quickly and correctly to dynamic changes in the network. 000659 On the Decidability Problem for a Topological Syllogistic Involving the Notion of Topological Product Domenico Cantone, Vincenzo Cutello tr-91-029 1991 05 __ 000006 A two-level, multi-sorted language of sets with cartesian product is introduced. The solvability of the satisfiability problem for the corresponding class of unquantified formulae is shown to be useful in order to automatically verify the validity of certain topological statements involving the notion of product of spaces.
The underlying motivation for this study is to enrich the class of theoretical results that can be used for a set-theoretic proof verifier. 000660 Probability estimation by feed-forward networks in continuous speech recognition Steve Renals, Nelson Morgan, Herve Bourlard tr-91-030 1991 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-030.pdf We review the use of feed-forward networks as estimators of probability densities in hidden Markov modelling. In this paper we are mostly concerned with radial basis functions (RBF) networks. We note the isomorphism of RBF networks to tied mixture density estimators; additionally we note that RBF networks are trained to estimate posteriors rather than the likelihoods estimated by tied mixture density estimators. We show how the neural network training should be modified to resolve this mismatch. We also discuss problems with discriminative training, particularly the problem of dealing with unlabelled training data and the mismatch between model and data priors. 000661 pSather monitors: Design, Tutorial, Rationale and Implementation Jerome A. Feldman, Chu-Cheow Lim, Franco Mazzanti tr-91-031 1989 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1989/tr-91-031.pdf Sather is a new object-oriented programming language under development at the International Computer Science Institute. The initial beta test release of the language was in June, 1991. From the outset, one goal of the Sather project has been the incorporation of constructs to support parallel programming. pSather is a parallel extension of Sather aimed at shared memory parallel architectures. A prototype of the language is currently being implemented on a Sequent Symmetry and on SUN Sparc-Stations. pSather monitors are one of the basic new features introduced in the language to deal with parallelism. The current design is presented and discussed in detail. 000662 GAL: Networks that grow when they learn and shrink when they forget Ethem Alpaydin tr-91-032 1991 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-032.pdf Learning when limited to modification of some parameters has a limited scope; the capability to modify the system structure is also needed to get a wider range of the learnable. In the case of artificial neural networks, learning by iterative adjustment of synaptic weights can only succeed if the network designer predefines an appropriate network structure, i.e., number of hidden layers, units, and the size and shape of their receptive and projective fields. This paper advocates the view that the network structure should not, as usually done, be determined by trial-and-error but should be computed by the learning algorithm. Incremental learning algorithms can modify the network structure by addition and/or removal of units and/or links. A survey of current connectionist literature is given on this line of thought. ``Grow and Learn'' (GAL) is a new algorithm that learns an association at one-shot due to being incremental and using a local representation. During the so-called ``sleep'' phase, units that were previously stored but which are no longer necessary due to recent modifications are removed to minimize network complexity. The incrementally constructed network can later be finetuned off-line to improve performance. Another method proposed that greatly increases recognition accuracy is to train a number of networks and vote over their responses. The algorithm and its variants are tested on recognition of handwritten numerals and seem promising especially in terms of learning speed. This makes the algorithm attractive for on-line learning tasks, e.g., in robotics. The biological plausibility of incremental learning is also discussed briefly.
Keywords: Incremental learning, supervised learning, classification, pruning, destructive methods, growth, constructive methods, nearest neighbor. 000663 Polymorphic Processor Arrays Massimo Maresca tr-91-033 1991 05 __ 000006 A Polymorphic Processor Array (PPA) is a two-dimensional mesh- connected array of processors, in which each processor is equipped with a switch able to interconnect its four NEWS ports. PPA is an abstract architecture based upon the experience acquired in the design and in the implementation of a VLSI chip, namely the Polymorphic Torus (PT) chip, and, as a consequence, it only includes capabilities that have been proved to be supported by cost-effective hardware structures. The main claims of PPA are that 1) it models a realistic class of parallel computers, 2) it supports the definition of high level programming models, 3) it supports virtual parallelism and 4) it supports low complexity algorithms in a number of application fields. In this paper we present both the PPA computation model and the PPA programming model; we show that the PPA computation model is realistic by relating it to the design of the PT chip and show that the PPA programming model is scalable by demonstrating that any algorithm having 0(p) complexity on a virtual PPA of size (square root m) X (square root m), has 0(kp) complexity on a PPA of size (square root n) X (square root n), with m=kn and k integer. We finally show some application algorithms in the area of numerical analysis and graph processing. 000664 Sather Language Design and Performance Evaluation Chu-Cheow Lim, Andreas Stolcke tr-91-034 1991 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-034.pdf Sather is an object-oriented language recently designed and implemented at the International Computer Science Institute in Berkeley. It compiles into C and is intended to allow development of object-oriented, reusable software while retaining C's efficiency and portability. We investigate to what extent these goals were met through a comparative performance study and analysis of Sather and C programs on a RISC machine. Several language design decisions in Sather are motivated by the goal of efficient compilation to standard architectures. We evaluate the reasoning behind these decisions, using instruction set usage statistics, cache simulations, and other data collected by instrumented Sather-generated code.
We conclude that while Sather users still pay a moderate overhead for programming convenience (in both run time and memory usage) the overall CPU and memory usage profiles of Sather programs are virtually identical to those of comparable C programs. Our analysis also shows that each of the choices made in Sather design and implementation is well justified by a distinctive performance advantage. It seems, then, that Sather proves the feasibility of its own design goal of making object-oriented programming efficient on standard architectures using a combination of judicious language design and efficient implementation. 000665 HiPNeT-1: A Highly Pipelined Architecture for Neural Network Training Krste Asanovic, Brian E. D. Kingsbury, Nelson Morgan, John Wawrzynek tr-91-035 1991 06 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-035.pdf Current artificial neural network (ANN) algorithms require extensive computational resources. However, they exhibit massive fine-grained parallelism and require only moderate arithmetic precision. These properties make possible custom VLSI implementations for high performance, low cost systems. This paper describes one such system, a special purpose digital VLSI architecture to implement neural network training in a speech recognition application.
The network algorithm has a number of atypical features. These include: shared weights, sparse activation, binary inputs, and a serial training input stream. The architecture illustrates a number of design techniques to exploit these algorithm-specific features. The result is a highly pipelined system which sustains a learning rate of one pattern per clock cycle. At a clock rate of 20MHz each "neuron" site performs 200 million connection updates per second. Multiple such neurons can be integrated onto a modestly sized VLSI die. 000666 Experimental Determination of Precision Requirements for Back-Propagation Training of Artificial Neural Networks Krste Asanovic, Nelson Morgan tr-91-036 1991 06 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-036.pdf The impact of reduced weight and output precision on the back-propagation training algorithm is experimentally determined for a feed-forward multi-layer perceptron. In contrast with previous such studies, the network is large with over 20,000 weights, and is trained with a large, real-world data set of over 130,000 patterns to perform a difficult task, that of phoneme classification for a continuous speech recognition system.
The results indicate that 16b weight values are sufficient to achieve training and classification results comparable to 32b floating point, provided that weight and bias values are scaled separately, and that rounding rather than truncation is employed to reduce the precision of intermediary values. Output precision can be reduced to 8 bits without significant effects on performance. 000667 A Brief History of the Association for Women in Mathematics: The Presidents' Perspectives Lenore Blum tr-91-037 1991 06 __ 000006 A talk with transparencies presented at the 20th anniversary celebration of the Association for Women in Mathematics, January, 1991. 000668 Test Complexity of Generic Poynomials Peter Buergisser, Thomas Lickteig, Michael Shub tr-91-038 1991 07 __ 000006 We investigate the complexity of algebraic decision membership in a hypersurface X propersubset (C superscript m). We prove an optimal lower bound on the number of additions, subtractions and comparisons and an asymptotically optimal lower bound on the number of multiplications, divisions and comparisons that are needed to decide membership in a generic subsurface X propersubset (C superscript m).
In the situation over the reals where in addition to equality branching also \leq-branching allowed, we prove an analogous statement for irreducible "generic" hypersurfaces X propersubset (R superscript m). In the case m=1 we give also a lower bound for finite subsets of X propersubset R. 000669 Verification Complexity of Linear Prime Ideals Peter Buergisser, Thomas Lickteig tr-91-039 1991 07 __ 000006 The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset X propersubset (R superscript m) where R is a real or algebraically closed field). We define a notion of verification complexity of a (real) prime ideal (in a prime cone) which gives a lower bound on the decision complexity. We exactly determine the verification complexity of some prime ideals of lineary type generalizing a result by Winograd [Win-70]. As an application we show uniform optimality with respect to the number of multiplications and divisions needed for two algorithms:
We find that networks using standard ATM procedures are dismally inefficient in carrying traditional data traffic -- depending on the protocols used, efficiency as seen by an application program ranges between 40 and 53 percent. Moreover, due to interaction between TCP- IP datagram lengths and ATM cell padding, efficiency responds abruptly to changes in certain protocol parameters -- for example, a 4-byte increase in ATM cell payload size can yield a 10 percent increase in efficiency. Using one compression technique in isolation can improve efficiency by 12 percent, and simultaneously using three techniques can improve it by 34 percent. These issues should be considered when designing future ATM networks. 000674 VC Dimension and Sampling Complexity of Learning Sparse Polynomials and Rational Functions Marek Karpinski, Thorsten Werther tr-91-044 1991 08 __ 000006 This paper presents the recent results on the VC dimension and the sampling complexity of learning sparse polynomials and rational functions. Some of the direct applications of these results have also been presented. 000675 The Automatic Worst Case Analysis of Parallel Programs: Single Parallel Sorting and Algorithms on Graphs Wolf Zimmerman tr-91-045 1991 08 __ 000006 No Abstract. 000676 A Characterization of Space Complexity Cases and Subexponential Time Classes as Limiting Polynomially Decidable Sets Giorgio Ausiello, Marco Protasi, Michele Angelaccio tr-91-046 1991 08 __ 000006 The concept of limiting approximation, originally introduced by Gold for recursive functions, has been previously adapted by the authors to the polynomial level of complexity in order to study complexity classes of sets polynomially computable in the limit. In this paper new results concerning the characterization of space complexity classes (from PSPACE to Grzegorczyk classes) as classes of sets polynomially decidable in the limit are presented. Besides tight trade-offs between the rate of convergence of the approximating sequences and the constants of their polynomially running time are shown. Finally the limiting polynomial approximation for classes of sets between P and PSPACE is investigated under the hypothesis that P is different from PSPACE. 000677 CLOS, Eiffel, and Sather: A Comparison Heinz W. Schmidt, Stephen M. Omohundro tr-91-047 1991 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-047.pdf The Common Lisp Object System defines a powerful and flexible type system which builds on more than 15 years of experience with object-oriented programming. Most current implementations include a comfortable suite of Lisp support tools including an Emacs lisp editor, an interpreter, an incremental compiler, a debugger, and an inspector which together promote rapid prototyping and design. What else might one want from a system? We argue that static typing yields earlier error detection, greater robustness, and higher efficiency and that greater simplicity and more orthogonality in the language constructs leads to a shorter learning curve and more intuitive programming. These elements can be found in Eiffel and a new object-oriented language, Sather, that we are developing at ICSI. Language simplicity and static typing are not for free, though. Programmers have to pay with loss of polymorphism and flexibility in prototyping. We give a short comparison of CLOS, Eiffel and Sather, addressing both language and environment issues.
The different approaches taken by the languages described in this paper have evolved to fulfill different needs. While we have only touched on the essential differences, we hope that this discussion will be helpful in understanding the advantages and disadvantages of each language. 000678 ICSIM: An Object-Oriented Connectionist Simulator Heinz W. Schmidt, Benedict Gomes tr-91-048 1991 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-048.pdf ICSIM is a connectionist net simulator under development at ICSI and written in Sather. It is object-oriented to meet the requirements for flexibility and reuse of homogeneous and structured connectionist nets and to allow the user to encapsulate efficient customized implementations perhaps running on dedicated hardware. Nets are composed by combining off-the-shelf library classes and, if necessary, by specializing some of their behaviour. General user interface classes allow a uniform or customized graphic presentation of the nets being modeled.
The report gives an overview of the simulator. Its main concepts, the class structure of its library and some of the design decisions are sketched and a number of example nets are used to illustrate how net structure, interconnection and behavior are defined. 000679 VISIT: An Efficient Computational Model Of Human Visual Attention Subutai Ahmad tr-91-049 1991 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-049.pdf Thesis One of the challenges for models of cognitive phenomena is the development of efficient and flexible interfaces between low level sensory information and high level processes. For visual processing, researchers have long argued that an attentional mechanism is required to perform many of the tasks required by high level vision. This thesis presents VISIT, a connectionist model of covert visual attention that has been used as a vehicle for studying this interface. The model is efficient, flexible, and is biologically plausible. The complexity of the network is linear in the number of pixels. Effective parallel strategies are used to minimize the number of iterations required. The resulting system is able to efficiently solve two tasks that are particularly difficult for standard bottom-up models of vision: computing spatial relations and visual search. Simulations show that the network's behavior matches much of the known psychophysical data on human visual attention. The general architecture of the model also closely matches the known physiological data on the human attention system. Various extensions to VISIT are discussed, including methods for learning the component modules. 000680 Learning Spatial Concepts Using a Partially-Structured Connectionist Architecture Terry Regier tr-91-050 1991 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-050.pdf This paper reports on the learning of spatial concepts in the L0 project. The challenge of designing an architecture capable of learning spatial concepts from any of the world's languages is first highlighted by reviewing the spatial systems of a number of languages which differ strikingly from English in this regard. A partially structured connectionist architecture is presented which has successfully learned concepts from the languages outlined. In this architecture, highly structured subnetworks, specialized for the spatial concept learning task, feed into an unstructured, fully-connected upper subnetwork. The system's success at the learning task is attributed on the one hand to the constrained search space which results from structuring, and on the other hand to the flexibility afforded by the unstructured upper subnetwork. 000681 Evaluation of Overflow Probabilities in Resource Management Dinesh Chandra Verma, Domenico Ferrari tr-91-051 1991 10 __ 000006 In a number of network and database management applications, we need to evaluate an overflow probability, which is an upper bound on the probability that the capacity of a server will be exceeded. The problem can be essentially reduced to evaluating the probability that the sum of N independent random variables exceed a given threshold. Evaluation of this probability by brute-force enumeration requires exponential time, so attempts have been made to approximate the overflow probability by using Chernoff bounds. This paper presents a simple scheme that can be used to evaluate the overflow probability with a higher degree of accuracy and lower computational efforts than the Chernoff bound approach. 000682 CHCL--A Connectionist Inference System Steffen Hoelldobler, Franz Kurfess tr-91-052 1991 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-052.pdf CHCL is a "c"onnectionist inference system for "H"orn logic which is based on the "c"onnection method and uses "l"imited resources. This paper gives an overview of the system and its implementation. 000683 Unification with ICSIM Franz Kurfess tr-91-053 1991 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-053.pdf This document describes the implementation of a distributed unification algorithm using the connectionist simulator ICSIM. The algorithm is based on S. Hoelldobler's work, as described in [Hoelldobler, 1990b]. Unification problems are specified according to a simple language, describing the terms, functions, variables and constants occurring in such a problem; the terms to be unified are represented as less than term_1 = term_2 is greater than (e.g., less than f(x, x, x) = f(g(a), y, g(z)) is greater than).
A parser extracts relevant information and creates intermediate data structures needed for the construction of the connectionist network. Essential data structures describe the symbols occurring in the terms, the hierarchical structure of the terms (functions and their arguments), and the occurrences of the symbols in the terms. The connectionist unification network is constructed based on these intermediate structures. It is hierarchically organized, its top level NET consisting of POSITIONS, which correspond to the nodes in the term structure. A POSITION consists of a SYMBOL, either of type VARIABLE or CONSTANT. Symbols comprise a TERM UNIT and a number of UNIFICATION UNITS, depending on the number of positions in the terms to be unified. Initially, TERM UNITS are set according to the occurrences of their symbols in the term structure; based on the links within the network and the activation of UNIFICATION UNITS, more TERM UNITS are activated as required by the unification algorithm. The final set of active TERM UNITS is used to construct the most general unifier for the terms to be unified. The network can be easily extended to detect inconsistencies in the term structure or to perform an occur check. 000684 Knowledge Selection with ANNs Dimitris Karagiannis, Franz Kurfess, Heinz-Wilhelm Schmidt tr-91-054 1991 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-054.pdf (32 Pages) The access to information contained in possibly large knowledge bases is a crucial factor in the usability of such a knowledge base. In this paper, we present a method to select information relevant for a query in knowledge bases where the information is represented in a rule-based way. An approach based on artificial neural networks is used to pre-select the set of relevant rules, thus facilitating the task of the inference mechanism by restricting the search space to be traversed considerably. In addition to the information contained in the query itself, data derived from the environment in which the query is situated is used to further trim down the search space. Sources for this derivation process are data about the task under investigation as well as the history of user interactions.
We refer to the first way of diminishing the search space via the query as "identification"; the second one is referred to as "adaptation", since the selection process is adapted to the current task. The third one, taking into account the history of interactions between user and knowledge base, is called "prediction", aiming at a possible prediction of the next query, or a subset of rules relevant for the next query.
An implementation of the artificial neural networks used for these tasks is based on ICSIM, a connectionist simulator developed at ICSI. 000685 Potentiality of Parallelism in Logic Franz Kurfess tr-91-055 1991 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-055.pdf The processing of knowledge is becoming a major area of applications for computer systems. In contrast to data processing, the current stronghold of computer use, where well-structured data are manipulated through well-defined algorithms, the treatment of knowledge requires more intricate representation schemes as well as refined methods to manipulate the represented information. Among the many candidates proposed for representing and processing knowledge, logic has a number of important advantages, although it also suffers from some drawbacks. One of the advantages is the availability of a strong formal background with a large assortment of techniques for dealing with the representation and processing of knowledge. A considerable disadvantage so far is the amount and complexity of computation required to perform even simple tasks in the area of logic. One promising approach to overcome this problem is the use of parallel processing techniques, enabling an ensemble of processing elements to cooperate in the solution of a problem. The goal of this paper is to investigate the combination of parallelism and logic. 000686 Distributed Delay Jitter Control in Packet-Switching Internetworks Domenico Ferrari tr-91-056 1991 10 __ 000006 Delay jitter is the variation of the delays with which packets travelling on a network connection reach their destination. For good quality of reception, continuous-media (video, audio, image) streams require that jitter be kept below a sufficiently small upper bound. This paper proposes a distributed mechanism for controlling delay jitter in a packet-switching network. The mechanism can be applied to an internetwork that satisfies the conditions detailed in the paper, and can coexist with other schemes (including the absence of any scheme) for jitter control within the same network, the same node, and even the same real-time channel. The mechanism can guarantee small jitter bounds even when the clocks of the host systems and the gateways along a channel's route are only loosely synchronized; furthermore, it makes the distribution of buffer space requirements more uniform over the channel's route, and reduces by a non-neglible amount the total buffer space needed by a channel. The paper argues that, if these advantages are sufficient to justify the higher costs of the distributed jitter control mechanism with respect to a non-distributed one, it would be useful to offer to the network's users a jitter control service based on the mechanism proposed here. 000687 A Method for Obtaining Randomized Algorithms with Small Tail Probabilities H. Alt, L. Guibas, K. Mehlhorn, R. Karp, A. Wigderson tr-91-057 1991 09 __ 000006 We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities. 000688 Detecting Skewed Symmetries Stefan Posch tr-91-058 1991 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-058.pdf Many surfaces of objects in our world are bounded by planar bilaterally symmetric figures. When these figures are imaged under orthographic projection a skewed symmetric contour results. In this paper a new fast, local method to recover skewed symmetries from curve segments is proposed. It can be applied to complete as well as to occluded contours. Furthermore, the skewed symmetry property is employed to overcome fragmentation of a contour during segmentation. 000689 Line Labeling Using Markov Random Fields Terry Regier tr-91-059 1991 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-059.pdf The task of obtaining a line labeling from a greyscale image of trihedral objects presents difficulties not found in the classical line labeling problem. As originally formulated, the line labeling problem assumed that each junction was correctly pre-classified as being of a particular junction type (e.g. T, Y, arrow); the success of the algorithms proposed have depended critically upon getting this initial junction classification correct. In real images, however, junctions of different types may actually look quite similar, and this pre-classification is often difficult to achieve. This issue is addressed by recasting the line labeling problem in terms of a coupled probabilistic system which labels both lines and junctions. This results in a robust system, in which prior knowledge of acceptable configurations can serve to overcome the problem of misleading or ambiguous evidence. 000690 Oracle Computations in Parallel Numerical Linear Algebra B. Codenotti, M. Leoncini, G. Resta tr-91-060 1991 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-060.pdf We analyze the relative complexity of several numerical linear algebra problems, when errors in the computation occur. We show that the simple parallel complexity classes of the exact case do not seem to preserve under approximation. 000691 Combinatory Differential Fields: An Algebraic Approach to Approximate Computation and Constructive Analysis Karl Aberer tr-91-061 1991 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-061.pdf The algebraic structure of combinatory differential fields is constructed to provide a semantics for computations in analysis. In this setting programs, approximations, limits and operations of analysis are represented as algebraic terms. Analytic algorithms can be derived by algebraic methods. The main tool in this construction are combinatory models which are inner algebras of Engeler graph models. As an universal domain of denotational semantics the lattice structure of the graph models allows to give a striking simple semantics for computations with approximations. As models of combinatory algebra they provide all essential computational constructs, including recursion. Combinatory models are constructed as extensions of first order theories. The classical first order theory to describe analysis is the theory of differential fields. It turns out that two types of computational constructs, namely composition and piecewise definition of functions, are preferably introduced as extensions of the differential fields theory. Combinatory differential fields are then the combinatory models of these enriched differential fields. We show for basic algorithms of computational analysis how their combinatory counterparts are derived in the algebraic setting. We illustrate how these algorithms are suitable to be implemented in a computer algebra environment like mathematica. 000692 Self-Testing/Correcting with Applications to Numerical Problems (Revised Version) Manuel Blum, Michael Luby, Ronitt Rubinfeld tr-91-062 1991 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-062.pdf 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 {\em self-testing/correcting pair} for $f$ allows us to: (1) estimate the probability that $P(x) \not= f(x)$ when $x$ is randomly chosen; (2) on {\em 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. 000693 How to Solve Interval Constraint Networks: The Definitive Answer - Probably Peter Ladkin, Alexander Reinefeld tr-91-063 1991 11 __ 000006 We implemented and tested an algorithm for solving interval constraint problems which returned solutions in less than or equal to 0.5 seconds on the average, with the hardest problem taking less than or equal to 0.5 minutes on a RISC workstation. This is a surprising result considering the problem is known to be NP-complete. We conclude that our algorithm suffices for solving random interval constraint problems in practice.
Other conclusions are that path-consistency is an excellent pruning technique for solution search, which becomes almost a linear selection of atomic labels; also that path-consistency by itself is an excellent consistency heuristic for networks with fewer than six or greater than 15 nodes. We tested the algorithm on over two million randomly generated interval networks of various sizes, hence our title. 000694 Distortion Accumulation in Image Transform Coding/Decoding Cascades Michael Gilge tr-91-064 1991 12 __ 000006 With an increasing number of applications that employ transform coding algorithms for data reduction, the effect of distortion accumulation caused by multiple coding needs to be investigated. Multiple coding occurs when more than one coding system is connected in a cascade. From the second stage on, the coding algorithm operates on data that has been previously coded/decoded. First a generic image communication system is being modelled and situations that can lead to distortion accumulation are analyzed. These results show two main reasons for distortion accumulation, which are separately and jointly investigated using a JPEG-type compression algorithm. The first situation involves geometric operations between the decoding and next coding step. Measurements show however that these spatial manipulations are the main contributors to distortion accumulation. The second reason for distortion accumulation is a misalignment of the block segmentation reference point in subsequent transform operations. A block raster detection algorithm is derived that can find the position of the block raster that was introduced in a previous coding step. If this information is used in the block segmentation of the following coding step, distortion accumulation can be avoided. Simulation results are given for an extended algorithm that registers regions of homogeneous block raster in images consisting of several subimages. 000695 Motion Video Coding for Packet-Switching Networks -- An Integrated Approach Michael Gilge, Riccardo Gusella tr-91-065 1991 12 __ 000006 NOTE: This postscript file will preview just fine, but on most postscript printers it will refuse to print past page 4. Hence the .BAD tag. This file is offerred AS-IS, and will likely not ever be fixed. The advantages of packet video, constant image quality, service integration and statistical multiplexing, are overshadowed by packet loss, delay and jitter. By integrating network-control into the image data compression algorithm, the strong interactions between the coder and the network can be exploited and the available network bandwidth can be used best. In order to enable video transmission over today's networks without reservation or priorities and in the presence of high packet loss rates, congestion avoidance techniques need to be employed. This is achieved through rate and flow control, where feedback from the network is used to adapt coding parameters and vary the output rate. From the coding point of view the network is seen as data buffer. Analogously to constant bit rate applications, where a controller measures buffer fullness, we attempt to avoid network congestion (eq. buffer overflow) by monitoring the network and adapting the coding parameters in real-time. 000696 A Graph-Theoretic Game and its Application to the k-Server Problem Noga Alon, Richard M. Karp, David Peleg, Douglas West tr-91-066 1991 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-066.pdf This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree T and the edge player chooses an edge e. The payoff to the edge player is cost(T,e), defined as follows: If e lies in the tree T then cost(T,e)=0; if e does not lie in the tree then cost(T,e) = cycle(T,e)/w(e), where w(e) is the weight of edge e and cycle(T,e) is the weight of the unique cycle formed when edge e is added to the tree T. Our main result is that the value of the game on any n-vertex graph is bounded above by \exp(O(\sqrt{\log n \log\log n})).
The game arises in connection with the k-server problem on a road network; i.e., a metric space that can be represented as a multigraph G in which each edge e represents a road of length w(e). We show that, if the value of the game on G is Val(G,w), then there is a randomized strategy that achieves a competitive ratio of k(1 + Val(G,w)) against any oblivious adversary. Thus, on any n-vertex road network, there is a randomized algorithm for the k-server problem that is k\cdot\exp(O(\sqrt{\log n \log\log n}))-competitive against oblivious adversaries.
At the heart of our analysis of the game is an algorithm that, for any n-vertex weighted, connected multigraph, constructs a spanning tree T such that the average, over all edges e, of cost(T,e) is less than or equal to \exp(O(\sqrt{\log n \log\log n})). This result has potential application to the design of communication networks.
[The on-line copy of this technical report was created from a later version (1992). A revised and expanded version of the paper appeared in the SIAM J. on Computing, Volume 24, (1995), pages 78-100.] 000697 Probabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms Marek Karpinski, Wolf Zimmermann tr-91-067 1991 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-067.pdf We study two probabilistic recurrence relations that arise frequently in the analysis of parallel and sequential divide-and-conquer algorithms (cf. [Karp 91]). Suppose a problem of size x has to be solved. In order to solve it we divide it into subproblems of size h_1(x), ... ,h_k(x) and these subproblems are solved recursively. We assume that size(h_i(z)) are random variables. This occurs if either the break up step is randomized or the instances to be solved are drawn from a probability distribution. The running time T(z) of a parallel algorithm is therefore determined by the maximum of the running times T(h_i(z)) of the subproblems while the sequential algorithm is determined by the sum of the running times of the subproblems. We give a method for estimating tight upper bounds on the probability distribution of T(x) for these two kinds of recurrence relations, answering the open questions in [Karp 91].
Keywords: Probabilistic Recurrence Relations, Devide-and-Conquer Algorithms, Parallel Algorithms, Upper Bounds on Probability Distribution. 000698 Construction of a pseudo-random generator from any one-way function Johan Hastad, Russell Impagliazzo, Leonid A. Levin, Michael Luby tr-91-068 1991 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-068.pdf We show how to construct a pseudo-random generator from any one-way function. In contrast, previous works have constructed pseudo-random generators only from one-way functions with special structural properties. Our overall approach is different in spirit from previous work; we concentrate on extracting and smoothing entropy from a single iteration of the one-way function using universal hash functions. 000699 RASTA-PLP Speech Analysis Hynek Hermansky, Nelson Morgan, Aruna Bayya, Phil Kohn tr-91-069 1991 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-069.pdf Most speech parameter estimation techniques are easily influenced by the frequency response of the communication channel. We have developed a technique that is more robust to such steady-state spectral factors in speech. The approach is conceptually simple and computationally efficient. The new method is described, and experimental results are reported, showing a significant advantage for the proposed method. 000700 Connectionist Speech Recognition: Status and Prospects Steve Renals, Nelson Morgan, Herve Bourlard, Michael Cohen, Horacio Franco, Chuck Wooters, Phil Kohn tr-91-070 1991 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-070.pdf We report on recent advances in the ICSI connectionist speech recognition project. Highlights include:
000701 GDNN: A Gender-Dependent Neural Network for Continuous Speech Recognition Yochai Konig, Nelson Morgan, Claudia Chandra tr-91-071 1991 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-071.pdf Conventional speaker-independent speech recognition systems do not consider speaker-dependent parameters in the probability estimation of phonemes. These recognition systems are instead tuned to the ensemble statistics over many speakers. Most parametric representations of speech, however, are highly speaker dependent, and probability distributions suitable for a certain speaker may not perform as well for other speakers. It would be desirable to incorporate constraints on analysis that rely on the same speaker producing all the frames in an utterance. Our experiments take a first step towards this speaker consistency modeling by using a classification network to help generate gender-dependent phonetic probabilities for a statistical recognition system. Our results show a good classification rate for the gender classification net. Simple use of such a model to augment an existing larger network that estimates phonetic probabilities does not help speech recognition performance. However, when the new net is properly integrated in an HMM recognizer, it provides significant improvement in word accuracy. 000702 SPERT: A VLIW/SIMD Microprocessor for Artificial Neural Network Computations Krste Asanovic, James Beck, Brian E. D. Kingsbury, Phil Kohn, Nelson Morgan, John Wawrzynek tr-91-072 1991 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-072.pdf SPERT (Synthetic PERceptron Testbed) is a fully programmable single chip microprocessor designed for efficient execution of artificial neural network algorithms. The first implementation will be in a 1.2 micron CMOS technology with a 50MHz clock rate, and a prototype system is being designed to occupy a double SBus slot within a Sun Sparcstation.1. Experimental results showing that connectionist methods can improve the performance of a context independent maximum likelihood trained HMM system, resulting in a performance close to that achieved using state of the art context dependent HMM systems of much higher complexity;
2. Mixing (context independent) connectionist probability estimates with maximum likelihood trained context dependent models to improve the performance of a state of the art system;
3. The development of a network decomposition method that allows connectionist modelling of context dependent phones efficiently and parsimoniously, with no statistical independence assumptions.
SPERT will sustain over 300 million connections per second during pattern classification, and around 100 million connection updates per second while running the popular error backpropagation training algorithm. This represents a speedup of around two orders of magnitude over a Sparcstation-2 for algorithms of interest. An earlier system produced by our group, the Ring Array Processor (RAP), used commercial DSP chips. Compared with a RAP multiprocessor of similar performance, SPERT represents over an order of magnitude reduction in cost for problems where fixed-point arithmetic is satisfactory.
This report describes the current architecture, and gives the results of detailed simulations. The report also makes a short comparison to other high-performance digital neurocomputing chips. 000703 Connectionist Layered Object-Oriented Network Simulator (CLONES): User's Manual Phil Kohn tr-91-073 1991 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-073.pdf CLONES is an object-oriented library for constructing, training and utilizing layered connectionist networks. The CLONES library contains all the object classes needed to write a simulator with a small amount of added source code (examples are included). The size of experimental ANN programs is greatly reduced by using an object- oriented library; at the same time these programs are easier to read, write and evolve. The library includes database, network behavior and training procedures that can be customized by the user. It is designed to run efficiently on data parallel computers (such as the RAP [6] and SPERT [1]) as well as uniprocessor workstations. While efficiency and portability to parallel computers are the primary goals, there are several secondary design goals:
1. minimize the learning curve for using CLONES,
2. minimize the additional code required for new experiments,
3. allow heterogeneous algorithms and training procedures to be interconnected and trained together.
Within these constraints we attempt to maximize the variety of artificial neural network algorithms that can be supported. 000704 Recent Work in VLSI Elements for Digital Implementations of Artificial Neural Networks Brian E. D. Kingsbury, Bertrand Irissou, Krste Asanovic, John Wawrzynek, Nelson Morgan tr-91-074 1991 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-074.pdf A family of high-performance, area-efficient VLSI elements is being developed to simplify the design of artificial neural network processors. The libraries are designed around the MOSIS Scalable CMOS design rules, giving users the option of fabricating designs in 2.0um or 1.2um n-well processes, and greatly simplifying migration of the libraries to new MOSIS technologies. To date, libraries and generators have been created for saturating and nonsaturating adders, a two's-complement multiplier, and a triple-ported register file. The SPERT processor currently being designed at ICSI will be based upon these libraries, and is expected to run at 50 MHz when realized in a 1.2um CMOS technology. 000705 Incomplete Factorizations for Certain Toeplitz matrices C. Bernini, B. Codenotti, M. Leoncini, G. Resta tr-91-075 1991 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-075.pdf We propose some incomplete factorizations for banded Toeplitz matrices and we show their application to the direct and iterative solution of several special Toeplitz linear systems. 000706 Real-Time Communication in an Internetwork; Domenico Ferrari tr-92-001 1992 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-001.pdf Can end-to-end communication performance be guaranteed by a packet-switching internetwork? This paper addresses the question by examining the feasibility of extending to an internetwork the Tenet approach to real-time communication service design. The conditions to be satisfied by an internetwork so that the approach can be extended to it are investigated. These include conditions for the scheduling discipline to be used in the nodes of the internetwork.
The original Tenet approach to real-time communication applies to a network consisting of hosts, homogeneous nodes (or switches), and physical links connecting nodes and hosts in an arbitrary topology. The nodes are store-and-forward, and are scheduled by a multi-class version of the Earliest Due Date deadline-based policy.
The discussion presented in this paper results in extendibility conditions that are quite broad; hence, the Tenet approach may be used to establish and run real-time channels in a vast class of internetworks. A case study is also discussed, involving a simple network, whose nodes are scheduled by FCFS-based disciplines, and the connection of such a network to an internetwork with deadline-based and hierarchical round robin scheduling. 000707 Constraint Relaxation and Nonmonotonic Reasoning Gerhard Brewka, Hans Werner Guesgen, Joachim Hertzberg tr-92-002 1992 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-002.pdf The purpose of this paper is to bring together the two AI areas of constraint-based and nonmonotonic reasoning. In particular, we analyze the relation between different forms of constraint relaxation and a particular approach to nonmonotonic reasoning, namely, preferred subtheories. In effect, we provide formal semantics for the respective forms of constraint relaxation. 000708 Rate-Controlled Static Priority Queueing Hui Zhang, Domenico Ferrrari tr-92-003 1992 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-003.pdf We propose a new service discipline, called the Rate-Controlled Static-Priority (RCSP) queueing discipline, that can provide throughput, delay, delay jitter, and loss free guarantees in a connection-oriented packet-switching network. The proposed RCSP queueing discipline avoids problems in previous proposed solutions. It achieves flexibility in the allocation of delay and bandwidth, as well as simplicity of implementation. The key idea is to separate rate-control and delay-control functions in the design of the server. Applying this separation of functions will result in a class of service disciplines, of which RCSP is an instance. 000709 Best-First Model Merging for Dynamic Learning and Recognition Stephen M. Omohundro tr-92-004 1992 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-004.pdf "Best-first model merging" is a general technique for dynamically choosing the structure of a neural or related architecture while avoiding overfitting. It is applicable to both learning and recognition tasks and often generalizes significantly better than fixed structures. We demonstrate the approach applied to the tasks of choosing radial basis functions for function learning, choosing local affine models for curve and constraint surface modelling, and choosing the structure of a balltree or bumptree to maximize efficiency of access. 000710 New algorithmic results for lines-in-3-space problems Leonidas J. Guibas and Marco Pellegrini tr-92-005 1992 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-005.pdf In the first part of the report we consider some incidence and ordering problems for lines in 3-space. We solve the problem of detecting efficiently if a query simplex is collision-free among polyhedral obstacles. In order to solve this problem we develop new on-line data structures to detect intersections of query halfplanes with sets of lines and segments.
Then, we consider the nearest-neighbor problems for lines. Given a set of$n$ lines in 3-space, the shortest vertical segment between any pair of lines is found in randomized expected time $O(n^{8/5+\epsilon})$ for every $\eps>0$. The longest connecting vertical segment is found in time $O(n^{4/3+\eps})$. The shortest connecting segment is found in time $O(n^{5/3 + \epsilon})$.
Problems involving lines, points and spheres in 3-space have important applications in graphics, CAD and optimization. In the second part of the report we consider several problems of this kind. We give subquaratic algorithms to count the number of incidences between a set of lines and a set of spheres, and to find the minimum distance between a set of lines and a set of points. We show that the sphere of minimum radius intersecting every line in a set of $n$ lines can be found in optimal expected time $O(n)$. Given $m$ possibly intersecting spheres we solve ray-shooting queries in $O(\log^2 m)$ time using a data structure of size $O(m^{5+\eps})$.
This technical report collects part of the second author's work at ICSI from September 1991 to January 1992. 000711 The LOGIDATA+ Object Algebra Umberto Nanni, Silvio Salza, Mario Terranova tr-92-006 1992 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-006.pdf In this paper we present the LOGIDATA+ Object Algebra (LOA), an algebra for complex objects which has been developed within the LOGIDATA project funded by the Italian National Research Council (CNR). LOGIDATA+ is intended to provide a rule based language on a data model with structured data types, object identity and sharing. LOA is a set-oriented manipulation language which was conceived as an internal language for a prototype system supporting such a rich environment. The algebra refers to a data model that includes structured data types and object identity, thus allowing both classes of objects and value-based relations.
LOA must deal with a rule based language with possible recursive programs with limited forms of negation. LOA programs explicitly include a "fixpoint" operator over a set of algebraic equations. Figures are omitted in the ftp-able version of the paper. A complete version is available from ICSI. 000712 The LOGIDATA+ Prototype System Umberto Nanni, Silvio Salza, Mario Terranova tr-92-007 1992 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-007.pdf In this paper we present a prototype system developed within LOGIDATA+, a national project funded by the Italian National Research Council (CNR). The prototype supports a rule based language on a data model with structured data types, object identity and sharing. The system has an interactive user interface, with a unit of interaction consisting of a LOGIDATA+ program, to extract information from the knowledge base and/or modify the schema. A program consists of a set of rules, and of additional directives to handle the data output and/or the updates to the schema. The prototype handles a temporary (user) environment where updates are performed and a permanent one, updated on request. The system uses LOA (LOGIDATA+ Object Algebra) as an intermediate internal language (see ICSI tr-92-006.ps.gz). User programs are translated into LOA programs, i.e. sequences of fixpoint systems of algebraic equations. The prototype is built on the top of a relational DBMS, that handles SQL transactions and provides the basic support for the permanent storage of data as well as for concurrency control and recovery. A main memory database has been included in the architecture, to improve the performance in the evaluation of the fixpoint systems, by keeping in main memory the intermediate results. Figures are omitted in the ftp-able version of the paper. A complete version is available from ICSI. 000713 Linear Time Algorithms for Liveness and Boundedness in Conflict-free Petri Nets Paola Alimonti, Esteban Feuerstain, Umberto Nanni tr-92-008 1992 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-008.pdf In this paper we consider the problems of deciding the set of potentially firable transitions, the liveness and boundedness for the class of Conflict-Free Petri Nets. For these problems we propose algorithms which are linear in the size of the description of the net, dramatically improving the best previous known results for these problems. Moreover the algorithm for the first problem is incremental: it is possible to perform an arbitrary sequence of updates, introducing new transitions and increasing the initial marking of the net, and queries, asking whether any transition is firable or any place reachable. Queries are answered in constant time, and the total cost for all the modifications is still linear in the size of the final net. Our approach is based on a representation of conflict-free Petri nets by means of directed hypergraphs. Figures are omitted in the ftp-able version of the paper. A complete version is available from ICSI. 000714 Fish in Schools or Fish in Cans Evolutionary Thinking and Formalization Dirk Siefkes tr-92-009 1992 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-009.pdf Gregory Bateson maintains that individual development and natural evolution follow the same principles --he parallels learning and evolution. I try to establish the precise mechanism of human learning by attributing the role of genes to concepts. We develop our thoughts conceptually through selection, in the same way that living beings develop genetically. Thus, thoughts evolve in our mind like fish in a cove, thoughts yielding concepts as the genetic material from which new thoughts arise. 000715 A New Algorithm for Counting Circular Arc Intersections Marco Pellegrini tr-92-010 1992 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-010.pdf We discuss the following problem: given a collection $\Gamma$ of $n$ circular arcs in the plane, count all intersections between arcs of $\Gamma$. We present an algorithm whose expected running time is $O(n^{3/2+\eps})$, for every $\eps >0$. If the arcs have all the same radius the expected time bound is $O(n^{4/3+\eps})$, for every $\eps>0$. Both results improve on the time bounds of previously known asymptotically fastest algorithms. The technique we use is quite general and it is applicable to other counting problems. 000716 The Weighted List Update Problem and the Lazy Adversary Fabrizio d'Amore, Alberto Marchetti-Spaccamela, Umberto Nanni tr-92-011 1992 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-011.pdf The "List Update Problem" consists in maintaining a dictionary as an unsorted linear list. Any request specifies an item to be found by sequential scanning through the list. After an item has been found, the list may be rearranged in order to reduce the cost of processing a "sequence" of requests.
Several kinds of adversaries can be considered to analyze the behavior of heuristics for this problem. The "Move-to-Front" (MTF) heuristic is 2-competitive against a "strong" adversary, matching the deterministic lower bound for this problem [21].
But, for this problem, moving elements does not help the adversary. A "lazy" adversary has the limitation that he can use only a static arrangement of the list to process (off-line) the sequence of requests: still, no algorithm can be better than 2-competitive against the lazy adversary [3].
In this paper we consider the "Weighted List Update Problem" (WLUP) where the cost of accessing an item depends on the item itself. It is shown that MTF is not competitive by any consent factor for this problem against a lazy adversary. Two heuristics, based on the MTF strategy, are presented for WLUP: "Random Move-to- Front" is randomized and uses biased coins; "Counting Move-to- Front" is deterministic, and replaces coins by counters. Both are shown to be 2-competitive against a lazy adversary. This is optimal for the deterministic case.
We apply this approach for searching items in a tree, proving that any "c"-competitive heuristic for the weighted list update problem provides a "c"-competitive heuristic for the "Tree Update Problem". 000717 Towards a Complexity Theory for Approximation Karl Aberer, Bruno Codenotti tr-92-012 1992 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-012.pdf This paper presents a novel approach to the analysis of numerical problems, which is closely related to the actual nature of numerical algorithms. In fact, models of computation are introduced which take into account such issues as adaptivity and error. Moreover, complexity vs error bounds and examples regarding the role of adaptivity are provided. Finally, it is shown that the overall approach fits naturally into an algebraic framework. 000718 Competitive On-line Algorithms for Paging and Graph Coloring Sandy Irani tr-92-013 1992 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-013.pdf We analyze the competitiveness of on-line algorithms for two problems: paging and on-line graph coloring. In the first problem, we develop a refinement of competitive analysis for paging algorithms which addresses some of the areas where traditional competitive analysis fails to represent what is observed in practice. For example, traditional competitive analysis is unable to discern between LRU and FIFO, although in practice LRU performs much better than FIFO. In addition, the theoretical competitiveness of LRU is much more pessimistic than what is observed in practice. We also address the following important question: given some knowledge of a program's reference pattern, can we use it to improve paging performance on that program?
We address these concerns by introducing an important practical element that underlies the philosophy behind paging: locality of reference. We devise a graph-theoretical model, the access graph, for studying locality of reference.
The second problem that we consider is on-line graph coloring. In the spirit of competitiveness, we evaluate on-line graph coloring algorithms by their performance ratio which measures the number of colors the algorithm uses in comparison to the chromatic number of the graph. We consider the class of d-inductive graphs. A graph G is d-inductive if the vertices of G can be numbered so that each vertex has at most d edges to higher numbered vertices. We analyze the greedy algorithm and show that if G is d-inductive then FF uses O( d log n) colors on G. We show that this bound is tight. Since planar graphs are 5-inductive, and chordal graphs are c(G)-inductive, (where c(G) is the chromatic number of the graph G), our results yield bounds on the performance ratio of greedy on these important classes of graphs. We also examine on-line graph coloring with lookahead. An algorithm is on-line with lookahead l, if it must color vertex i after examining only the first l+i vertices. We show that for l < (n / log n) no on-line algorithm with lookahead l can perform better than First Fit on d-inductive graphs.
Keywords: on-line algorithms, competitive analysis, paging, locality of reference, on-line graph coloring, lookahead. 000719 Backwards Analysis of Randomized Geometric Algorithms Raimund Seidel tr-92-014 1992 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-014.pdf The theme of this paper is a rather simple method that has proved very potent in the analysis of the expected performance of various randomized algorithms and data structures in computational geometry. The method can be described as ``analyze a randomized algorithm as if it were running backwards in time, from output to input.'' We apply this type of analysis to a variety of algorithms, old and new, and obtain solutions with optimal or near optimal expected performance for a plethora of problems in computational geometry, such as computing Delaunay triangulations of convex polygons, computing convex hulls of point sets in the plane or in higher dimensions, sorting, intersecting line segments, linear programming with a fixed number of variables,and others. 000720 Queueing Delays in Rate Controlled Networks Anindo Banerjea, Srinivasan Keshav tr-92-015 1992 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-015.pdf This paper addresses the problem of finding the worst case end-to-end delay and buffer occupancy bounds in networks of rate-controlled, non-work conserving servers.
The calculations are based on a simple fluid model, but care is taken so that the computed delay and buffer occupancy values are upper bounds on actual values. A simple algorithm is presented to perform these calculations in linear time.
Simulation results compare the computed worst case delays with the actual delays obtained on some simple network topologies. The algorithm is found to predict node delays well for bursty input traffic, but poorly for smooth input traffic. Buffer requirements are predicted well in both cases. 000721 A Framework for the Study of Pricing in Integrated Networks Colin J. Parris, Srinivasan Keshav, Domenico Ferrari tr-92-016 1992 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-016.pdf Integrated networks of the near future are expected to provide a wide variety of services, which could consume widely differing resources. We present a framework for pricing services in integrated networks, and study the effect of pricing on user behavior and network performance. We first describe a network model that is simple, yet models details such as the wealth distribution in society, different classes of service, peak and off-peak traffic and call blocking due to budgetary constraints.
We then perform experiments to study the effect of setup, per packet, and peak load prices on the blocking probability of two classes of calls passing through a single node enforcing admission control. Some selected results are that a) increasing prices first increases the net revenue to a provider, then causes a decrease b) peak-load pricing spreads network utilization more evenly, raising revenue while simultaneously reducing call blocking probability.
Finally, we introduce a novel metric for comparing pricing schemes, and prove that for the most part, a pricing scheme involving setup prices is better than a pricing scheme with no setup cost. 000722 The Sather Language and Libraries Stephen Omohundro, Chu-Cheow Lim tr-92-017 1992 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-017.pdf Sather is an object-oriented language derived from Eiffel which is particularly well suited for the needs of scientific research groups. It is designed to be very efficient and simple while supporting strong typing, garbage collection, object-oriented dispatch, multiple inheritance, parameterized types, and a clean syntax. It compiles into portable C code and easily links with existing C code. The compiler, debugger and several hundred library classes are freely available by anonymous FTP. This paper describes aspects of the language design, implementation and libraries. 000723 A Resource Based Pricing Policy for Real-Time Channels in a Packet-Switching Network Colin J. Parris, Domenico Ferrari tr-92-018 1992 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-018.pdf In the packet switching networks of the future the need for guaranteed performance on a wide variety of traffic characteristics will be of paramount importance. The generation of revenue, to recover costs and provide profit, and the multiple type of services offered will require that new pricing policies be implemented.
This paper presents a resource based pricing policy for real-time channels ( ie., channels with guaranteed performance ) in a packet switching network. The policy is based on a set of specific criteria, and the charges for any channel are based on the resources reserved for use by the channel. This reservation charge is based on the type of service requested, the time of day during which the channel exists, and the lifetime of the channel. We argue that the traditional resources are not sufficient to determine a fair reservation charge for a channel offering guaranteed delay bounds, and we introduce the notion of a delay resource in our charging formula. The type of service requested is thus characterized by the amount of the bandwidth, buffer space, CPU, and delay resources reserved. The analysis of this pricing policy is reduced to the analysis of a single node of the network, assuming a homogeneous network. This single-node characteristic increases the scalability and flexibility of the policy. An example of an implementation of this policy is provided. 000724 Design of a Continuous Media Data Transport Service and Protocol Mark Moran, Bernd Wolfinger tr-92-019 1992 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-019.pdf Applications with real-time data transport requirements fall into two categories: those which require transmission of data units at regular intervals, which we call continuous media (CM) clients, e.g. video conferencing, voice communication, high-quality digital sound; and those which generate data for transmission at relatively arbitrary times, which we call real-time message-oriented clients. Because CM clients are better able to characterize their future behavior than message-oriented clients, a data transport service dedicated for CM clients can use this a priori knowledge to more accurately predict their future resource demands. Therefore, a separate transport service can potentially provide a more cost-effective service along with additional functionality to support CM clients. The design of such a data transport service for CM clients and its underlying protocol (within the BLANCA gigabit testbed project) will be presented in this document. This service provides unreliable, in-sequence transfer (simplex, periodic) of so-called stream data units (STDUs) between a sending and a receiving client, with performance guarantees on loss, delay, and throughput. 000725 Read-Once Threshold Formulas, Justifying Assignments, and Generic Tranformations Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski tr-92-020 1992 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-020.pdf We present a membership query (i.e. interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. Using a generic transformation from [Angluin, Hellerstein, Karpinski 89], this gives an algorithm using membership and equivalence queries for exactly identifying the class of read-once formulas over the basis of boolean threshold functions and negation. We also present a series of generic transfor- mations that can be used to convert an algorithm in one learning model into an algorithm in a different model.
Keywords: Learning Algorithms, Queries, Read-Once Formulas, Threshold Functions. 000726 Local Properties of Some NP-Complete Problems Bruno Codenotti, Luciano Margara tr-92-021 1992 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-021.pdf It has been shown that certain NP-complete problems, i.e. TSP, min cut, and graph partitioning, with specific notions of neighborhood, satisfy a simple difference equation. In this paper, we extend these results by proving that TSP with 2-change, 2+3-new-change, and 3-new-change notions of neighborhood satisfy such a difference equation, and we derive some properties of local search when performed with the above definitions of neighborhood. 000727 Petri Net Based Software Validation: Prospects and Limitations Monika Heiner tr-92-022 1992 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-022.pdf Petri net based software validation to check the synchronization structure against some data or control flow anomalies (like unboundednesss or non-liveness) has been a well-known and widely used approach for about ten years. To decrease the complexity problem and because the simpler the model, the more efficient the analysis, the validation is usually tried with the help of place transition Petri nets. However, the modelling with this Petri net class involves two important abstractions of actual software properties -- the time consumption of any action and the data dependencies among conflict decisions. Basically, this paper discusses some problems resulting from these abstractions in the models analyzed which are very often neglected and have therefore not been well understood up to now. Furthermore, discussing the pros and cons of the Petri net approach is done by offering a rough overview of the given background of dependable distributed software engineering. Suggestions for a related workstation supporting different net-based methods are outlined. 000728 Quality-of-Service Negotiation in a Real-Time Communication Network Jean Ramaekers, Giorgio Ventre tr-92-023 1992 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-023.pdf In the recent years new protocols and algorithms have been proposed to guarantee performance and reliability in exchanging data in real-time communication networks, and new services have been presented to allow cooperative office work, distributed conferencing, etc. Less attention has been paid to how applications and, more generally, clients of real-time communication services can interact with the network in order to specify and negotiate the quality-of-service of a connection. We believe that this problem is going to become a key issue for the success of future distributed systems, since it affects both client and network performances. In this paper we present a new mechanism for the establishment of real-time connections in a quality-of-service network developed for the Tenet real-time protocol suite. By improving the information exchanged between the network and the clients, the model allows to reduce the complexity and the time required to establish a real-time connection, and increases the network utilization. Additionally, we introduced a new class of real-time communication service to support adaptive quality-of-service, in order to enhance the possibilities of the network to face congestion situations. 000729 Communicating with Low-Diffraction Lasers and Mirrors Richard Beigel tr-92-024 1992 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-024.pdf Optical interconnection networks, in which each processor contains a set of lasers for communication with other processors, have long been studied. In the ``regular optics'' model of Murdocca a bounded number of planar mirrors are used to redirect light beams, and each processor has a bounded number of lasers directed at a fixed set of angles, independent of the processor.
It is theoretically interesting to ignore diffraction, and assume that lasers beams travel in a straight line. In the regular optical model, we present elegant layouts for processor networks including the shuffle, grids, and Margulis' expander graph. We also disprove the existence of a certain kind of 3-dimensional layout for shuffles.
Using slightly more complicated optical devices, such as beam splitters, we design a ``light guide,'' which allows simultaneous broadcasts, subject only to the limitations of light sensors. In particular, the light guide can perform single broadcasts. Given accurate enough clocks, it can perform arbitrary permutations. 000730 Tree Matching with Recursive Distributed Representations Andreas Stolcke, Dekai Wu tr-92-025 1992 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-025.pdf We present an approach to the structure unification problem using distributed representations of hierarchical objects. Binary trees are encoded using the recursive auto-association method (RAAM), and a unification network is trained to perform the tree matching operation on the RAAM representations. It turns out that this restricted form of unification can be learned without hidden layers and producing good generalization if we allow the error signal from the unification task to modify both the unification network and the RAAM representations themselves. 000731 On the Power of Discontinous Approximate Computations Karl Aberer, Bruno Codenotti tr-92-026 1992 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-026.pdf The set of operations S_1={+,-,*,/,>} is used in algebraic computations to avoid degeneracies (e.g., division by zero), but is also used in numerical computations to avoid huge roundoff errors (e.g., division by a small quantity). On the other hand, the classes of algorithms using operations from the set S_2={+,-,*,/} or from the set S_3={+,-,*} are the most studied in complexity theory, and are used, e.g., to obtain fast parallel algorithms for numerical problems. In this paper, we study, by using a simulation argument, the relative power of the sets S_1, S_2, and S_3 for computing with approximations. We prove that S_2 does very efficiently simulate S_1, while S_3 does not; this fact shows and measures the crucial role of division in computations introducing roundoff errors. We also show how to construct algorithms using operations {+,-,*,/} which achieve for most inputs the same error bounds as algorithms using operations {+,-,*,/,>}. To develop our simulation strategy we combine notions imported from approximation theory and topology with complexity and error bounds. More precisely, to find conditions under which this simulation can take place, we quantitatively describe the interplay between algebraic, approximation, topological, and complexity notions and we provide lower and upper bounds on the cost of simulation. 000732 The Quality of Separation Between NP and Exponential Time; Reducing the Cases Gerhard Lischke tr-92-027 1992 04 __ 000006 We consider three aspects of quality of separation between complexity classes: inclusion, immunity and sparseness in the differences. These aspects are discussed in general and investigated especially for the relationship between NP and deterministic exponential linear time, where we can reduce the number of possible cases from 24 to 8. Seven of the 8 cases are realizable in appropriate relativized worlds; one case remains open. Also, we found an error in former papers on this subject. 000733 Proposal of an External Processor Scheduling in Micro-Kernel Based Operating Systems Winfried Kalfa tr-92-028 1992 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-028.pdf Until now, the management of resources was a task of the operating systems kernel. The applications running on the operating system were in general, similiar to each other. Thus the limited policy of the resource manager could satisfy the demands of applications. With the advent of computer systems capable handling new applications such as multi-media and of new operating systems based on micro-kernels and supporting object paradigm in a distributed environment, an external resource manager became important for both traditional operating systems like UNIX with new applications and new object oriented and micro- kernel based operating systems. In this paper an approach to an external scheduling on the basis of the operating system BirliX is given. The proposal is based on a scheduler implemented in the user space. Problems of the implementation are described by means of the operating system BirliX as an example. Because the operating system is a distributed object oriented opera- ting system, our proposal deals with local and distributed managers. Coming from a system model of the BirliX, a resource mode, and a process model, the scheduling model is developed.
Keywords: Distributed Operating Systems, External Processor Scheduler, Micro-Kernel, BirliX 000734 Efficient Computation of Spatial Joins Oliver Günther tr-92-029 1992 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-029.pdf Spatial joins are join operations that involve spatial data types and operators. Due to some basic properties of spatial data, many conventional join processing strategies suffer serious performance penalties or are not applicable at all in this case. In this paper we explore which of the join strategies known from conventional databases can be applied to spatial joins as well, and how some of these techniques can be modified to be more efficient in the context of spatial data. Furthermore, we describe a class of tree structures, called generalization trees, that can be applied efficiently to compute spatial joins in a hierarchical manner. Finally, we model the performance of the most promising strategies analytically and conduct a comparative study. 000735 Checking Approximate Computations over the Reals Sigal Ar, Manuel Blum, Bruno Codenotti, Pete Gemmell tr-92-030 1992 05 __ 000006 This paper provides the first systematic investigation of checking approximate numerical computations, over subsets of the reals. In most cases, approximate checking is more challenging than exact checking. Problem conditioning, i.e., the measure of sensitivity of the output to slight changes in the input, and the presence of approximation parameters foil the direct transformation of many exact checkers to the approximate setting. We can extend exact checkers only if they have a very smooth dependence on the sensitivity of the problem. Furthermore, approximate checking over the reals is complicated by the lack of nice finite field properties such as the existence of a samplable distribution which is invariant under addition or multiplication by a scalar. We overcome the above problems by using such techniques as testing and checking over similar but distinct distributions, using functions' random and downward self-reducibility properties, and taking advantage of the small variance of the sum of independent identically distributed random variables. 000736 Decision Procedures for Flat Set-Theorectical Syllogistics.I. General Union, Powerset and Singleton Operators Domenico Cantone, Vincenzo Cutello tr-92-031 1992 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-031.pdf (Pages 30) In this paper we show that a class of unquantified multi-sorted set-theoretic formulae involving the notions of powerset, general union, and singleton has a solvable satisfiability problem. We exhibit a normalization procedure that given a model for a formula in our theory, it produces a simpler and "a priori" bounded model whose cardinality depends solely on the size of the given formula. 000737 A Model for Amalgamation in Group Decision Making Vincenzo Cutello, Javier Montero tr-92-032 1992 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-032.pdf (Pages 14) In this paper we present a generalization of the model proposed by Montero in [Mon87a, Mon87b, Mon92], by allowing non complete fuzzy binary relations for individuals. A degree of unsatisfaction can be defined in this case, suggesting that any democratic aggregation rule should take into account not only ethical conditions or some degree of rationality in the amalgamating procedure, but also a minimum support for the set of alternatives subject to the group analysis. 000738 A Characterization of Rational Amalgamation Operations Vincenzo Cutello, Javier Montero tr-92-033 1992 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-033.pdf (Pages 24) This paper deals with amalgamation of fuzzy opinions when a fixed number of individuals is faced with an unknown number of alternatives. The aggregation rule is defined by means of intensity aggregation operations that verify certain ethical conditions, and assuming fuzzy rationality as defined in [6, 7]. A necessary and sufficient condition for non-irrationality is presented, along with comments on the importance of the number of alternatives. 000739 Ambiguities in Object Specifications in View of Data Testing Dieter Richter tr-92-034 1992 06 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-034.pdf Checking data only relying on their specification is of importance when using neutral or standardized object models. Ambiguities arise during the tests because of specifications leaving a certain degree of freedom to the implementation. Based on an experimental background the observations and reflections about the reasons are systematically presented. It turns out that the transition (or mapping) from a specification of an object to a physical instance (or data set) has to take into consideration when defining neutral models. This transition which often has been seen as a technical question of the implementation or as the internal (hided) feature of a system appears as a particular point of the concept besides the specification of the semantics.
One crucial point is the instance handling with respect to assign and comparison operations. The mapping from a specification into a database can be realized in various manners which leads to interpretation defects when testing independently. Another point is the weak scope definition in specifications. Several ambiguities are caused by it. A very frequent reason of misunderstandings is the imprecise or wrong understanding of the different relations between objects, logical and physical instances. There are approaches for more clear specifications. The last point is the representation of failures or more generally of the state of instances. A concept based on multiple inheritance seems to increase the abstraction level of state specifications on the same level as the used specification language is of. 000740 Experiments with Noise Reduction Neural Networks for Robust Speech Recognition Michael Trompf tr-92-035 1992 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-035.pdf Speech recognition systems with small and medium vocabularies are used as natural human interface in a variety of real world applications. Though they work well in a laboratory environment, a significant loss in recognition performance can be observed in the presence of background noise. In order to make such a system more robust, the development of a neural network based noise reduction module is described in this paper. Based on function approximation techniques using multilayer feedforward networks (Hornik et al. 1990), this approach offers inherent nonlinear capabilities as well as easy training from pairs of corresponding noisy and noise-free signal segments. For the development of a robust nonadaptive system, information about the characteristics of the noise and speech components of the input signal and its past and future context is taken into account. Evaluation of each step is done by a word recognition task and includes experiments with changing signal parameters and sources to test the robustness of this neural network based approach. 000741 Efficient Clustering Techniques for the Geometric Traveling Salesman Problem Bruno Codenotti, Luciano Margara tr-92-036 1992 06 __ 000006 This paper presents some direct and iterative heuristic methods for the geometric Traveling Salesman Problem (TSP). All these methods are based on a particular notion of mass density, which can be used to construct a tour for the geometric TSP in an incremental fashion. In the iterative method, this technique is combined with the Lin-Kernighan method (LK), and this allows us to obtain better tours than those found by using LK itself. More precisely, the tour length we get is only 1.1% off the optimum. The direct method finds a solution passing through a sequence of subsolutions over progressively larger sets of points. These points are the relative maxima of the mass density obtained by using different parameter settings. The method has O(n^3) worst case running time and finds tours whose length is 9.2% off the optimal one. 000742 Measuring the Latency Time of Real-Time Unix-like Operating Systems Newton Faller tr-92-037 1992 06 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-037.pdf With the advent of continuous-media applications, real-time operating systems, once confined to process control and other specialized applications, are coming to the desktop. The popularity of UNIX made this operating system the first choice for use with such real-time desktop applications. However, since UNIX kernel does not provide real-time responsiveness, some software developers have been trying to adapt it to respond to this new requirements, while others have been proposing its total redesign. Though the evaluation of the performance of a real-time operating system depends on many factors, a predictable small latency time in responding to external events is always essential. In this paper, after a discussion about the probable sources of latency, it is presented a method for collecting information about context-switching and interrupt-acknowledge times in UNIX-like operating systems without requiring external measuring tools. It is also proposed, a form of presentation of these data aimed at facilitating the comparison with previously collected data obtained from the same or from other systems. The paper is illustrated with actual results obtained by the application of the method to TROPIX, a real-time UNIX-like operating system, running on a Motorola 68010-based computer. The impact of kernel preemption and some practical measurement interference considerations due to dynamic memory refresh, DMA operation and disk multiblock access are also discussed. 000743 Fuzzy Evolutionary Algorithms Hans-Michael Voigt tr-92-038 1992 06 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-038.pdf Evolutionary algorithms (EA) combine different approaches for solving complex problems based on principles, models, and mechanisms of natural evolution. Typical representatives of such algorithms are Genetic Algorithms (GA) and Evolution Strategies (ES), which are closely related in principle but show different emphasis on the representational and operational level. The basic ideas and concepts for GAs and ESs dates back to the early sixties. Central concepts of these approaches include the replication, recombination, mutation, selection, isolation-migration, and diffusion of individuals within or between populations or subpopulations, respectively. These algorithms do not take into account the development of an individual or organism from the gene level to the mature phenotype level. This development is a multistage decision process influenced by the environment and by interspecific as well as intraspecific competition and cooperation such that usually no inferences can be drawn from phenotype to genotype. The goal of this paper is to introduce a fuzzy representation and fuzzy operations to model the developmental process based on fuzzy decisions. Some first conclusions with respect to optimization will be stated.
The appendices include an up-to-date software survey for Evolutionary Algorithms and the description of "The Evolution Machine". 000744 Boot Algebras D. Schuett, U. Eckhardt, P. Suda tr-92-039 1992 06 __ 000006 The paper surveys our recent work in the field of Boolean algebra. It begins with an introduction into the theory of Boolean algebras and discusses problems related to the separation of an algebra into a family of factors so that the Cartesian product of the family is isomorphic to the given algebra. Such a product is called a "Boo"lean "t"uple algebra or for short a Boot algebra if each factor is completely contained in the original algebra. Some examples are taken from the field of digital circuit design and image processing. They demonstrate how Boot algebras can be applied. 000745 Robot Shaping: Developing Situated Agents through Learning Marco Colombetti, Marco Dorigo tr-92-040 1992 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-040.pdf 1993] Learning plays a vital role in the development of situated agents. In this paper, we explore the use of reinforcement learning to "shape" a robot to perform a predefined target behavior. We connect both simulated and real robots to Alecsys, a parallel implementation of a learning classifier system with an extended genetic algorithm. After classifying different kinds of Animat-like behaviors, we explore the effects on learning of different types of agent's architecture (monolithic, flat and hierarchical) and of training strategies. In particular, hierarchical architecture requires the agent to learn how to coordinate basic learned responses. We show that the best results are achieved when both the agent's architecture and the training strategy match the structure of the behavior pattern to be learned. We report the results of a number of experiments carried out both in simulated and in real environments, and show that the results of simulations carry smoothly to real robots. While most of our experiments deal with simple reactive behavior, in one of them we demonstrate the use of a simple and general memory mechanism. As a whole, our experimental activity demonstrates that classifier systems with genetic algorithms can be practically employed to develop autonomous agents.
Keywords: machine learning, adaptive systems, genetic algorithms, learning classifier systems, behavior-based robotics. 000746 The NC Equivalence of Integer Linear Programming and Euclidean GCD Victor Pan tr-92-041 1992 12 __ 000006 We show NC-reduction of integer linear programming with two variables to the evaluation of the remainder sequence arising in the application of the Euclidean algorithm to two positive integers. Due to the previous result of Deng, this implies NC-equivalence of both of these problems, whose membership in NC, as well as P-completeness, remain unresolved open problems. 000747 A Framework for Cumulative Default Logics Gehard Brewka tr-92-042 1992 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-042.pdf We present a framework for default reasoning which has its roots in Reiter's Default Logic. Contrary to Reiter, however, we do not consider defaults as inference rules used to generate extensions of a classical set of facts. In our approach defaults are elements of the logical language, and we will define inference rules on defaults. This has several advantages. First of all, we can reason about defaults, not just with defaults. This makes it easy to include different intuitions about the right behaviour of a default logic in an explicit form. Secondly, we can show how some of the problems of Reiter's logic and of some recent proposals to solve them can be handled adequately by exploiting the dependency information contained in derived defaults. 000748 A Symbolic Complexity Analysis of Connectionist Algorithms for Distributed-Memory Machines Jonathan Bachrach tr-92-043 1992 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-043.pdf This paper attempts to rigorously determine the computation and communication requirements of connectionist algorithms running on a distributed-memory machine. The strategy involves (1) specifying key connectionist algorithms in a high-level object-oriented language, (2) extracting their running times as polynomials, and (3) analyzing these polynomials to determine the algorithms' space and time complexity. Results are presented for various implementations of the back-propagation algorithm~\cite{Rumelhart-Hinton-Williams}. 000749 On-Line Algorithms Versus Off-Line Algorithms: How Much is it Worth to Know the Future? Richard M. Karp tr-92-044 1992 07 __ 000006 An "on-line algorithm" is one that receives a sequence of requests and performs an immediate action in response to each request. On-line algorithms arise in any situation where decisions must be made and resources allocated without knowledge of the future. The effectiveness of an on-line algorithm may be measured by its "competitive ratio", defined as the worst-case ratio between its cost and that of a hypothetical off-line algorithm which knows the entire sequence of requests in advance and chooses its actions optimally. In a variety of settings, we discuss techniques for proving upper and lower bounds on the competitive ratios achievable by on-line algorithms. In particular, we discuss the advantages of randomized on-line algorithms over deterministic ones. 000750 Persistence in the Object-Oriented Database Programming Language VML Wolfgang Klas, Volker Turau tr-92-045 1992 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-045.pdf In this paper the principles of handling persistent objects in the object-oriented database programming language VML is presented. The main design criteria of VML with respect to persistence were: persistence independent programming, data type completeness and operations manipulating the extension of a class. After defining the above mentioned concepts an example is used to compare the modelling and computational power of VML with the database programming languages Adaplex, PS-algol, and Galileo. The distinction of types and classes is the basis for defining persistence in VML. Instances of classes are always persistent and those of data types are always transient. All instances are referenced by object identifiers, values of datatypes are referenced independently of the fact whether they are attached to persistent objects (and are therefore persistent itself) or whether they are "stand alone". 000751 An Object-Oriented Approach to the Design of Graphical User Interface Systems Fabio Paterno tr-92-046 1992 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-046.pdf In this paper the problems concerning the design of graphical user interface systems composed of a set of interaction objects allowing users to interact with structured graphics are presented. Here we want to point out the problems and the requirements that are raised in performing such a design in an object-oriented environment. For this purpose the importance of task-oriented design of interaction objects in order to make the traslation from the user task to the system functions easier is addressed. The design of a hierarchy of interaction objects following this approach is proposed. This contrast with the current window systems toolkits design because it is mainly driven by the semantics of the interaction object rather than their appearance. Finally an example of common graphical interface performed by the proposed approach is presented. 000752 An Adaptive Classification Scheme to Approximate Decision Boundaries Using Local Bayes Criteria - The "Melting Octree" Network L. Miguel Encarnacao, Markus H. Gross tr-92-047 1992 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-047.pdf The following paper describes a new method to approximate the minimum error decision boundary for any supervised classification problem by means of a linear neural network consisting of simple neurons that use a local Bayes criterium and a next neighbor decision rule. The neurons can be interpreted as centroids in feature space or as a set of particles moving towards the classification boundary during training. In contrary to existing LVQ methods and RCE networks each neuron has a receptive field of an adjustable width e and the goal of the supervised training method is completely different. Furthermore, the network is able to grow in the sense of generating new entities in order to decrease the classification error after learning.
For this purpose we initialize the network via a multidimensional octree representation of the training data set. The neurons generated during initialization only depend on the maximum number of data in a single octree cell. The learning method introduced ensures that all neurons move towards the class boundaries by checking the local Bayes criterium in their receptive field. For this process can also be interpreted as a melting away of the initial octree, we called the network "The Melting Octree" network.
This report first describes the algorithms used for initialization, training as well as for growing of the net. The classification performance of the algorithm is then illustrated by some examples and compared with those of a Kohonen feature Map (LVQ) and of a backpropagated multilayered perceptron.
Note: The charts are page 39 of the techreport. I stored them under tr-92-047.charts.ps.Z. They're not absolutely necessary for the report; just to complete it. 000753 A Study of Perceptually Grounded Polysemy in a Spatial Microdomain Jordan Zlatev tr-92-048 1992 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-048.pdf This paper attempts to exemplify the advantages of perceptually grounded semantics with respect to traditional formalist approaches in elucidating the nature of the controversial notion of linguistic polysemy, or multiplicity of meaning. It is also suggested how some aspects of language typically associated with compositionality could be modeled, without there being a strictly ``compositional semantics''.
This is done through a series of experiments, using modifications of Terry Regier's connectionist system for learning spatial relations which constitutes a part of the L subscript 0 project concerned with associating descriptions in an arbitrary language with an analog environment, (sequences of) pictures of simple two-dimensional scenes.
The emphasis is above all on the English preposition `over', famous for its polysemy, and analyzed in detail by [Brugman, 1981] and [Lakoff, 1987], but some modeling has also been done of the meaning of `under', as well as some rudimentary semantics for simple verbs such as `be', `go' and `fly' that combine with the two prepositions.
Three kinds of connectionist architectures have been used in trying to capture what might be called a `polysemous over'. It is suggested that the first seems to treat polysemy like what has traditionally been regarded as generality, where distinctions are neutralized and senses are not distinct, while the second reduces polysemy to homonomy where they are distinct but not related. It is the third type of (structured) connectionist architecture that managed best in both learning different senses and reflecting the polysemous structure of the lexical item in analyses of the relevant hidden layers. In this architecture polysemy emerges as an effect of the combinatorics of words and their pairing with the environment.
The main theoretical claim is that polysemy is best regarded as a contextual rather than a purely lexical phenomenon. This on its part suggests support for the claim made in [Geeraerts, 1992] that the distinction between polysemy and generality is unstable, and for a semantics that is radically anti-reificational. The results from this study suggest that such a semantics can account for the generativity and systematicity of language, despite claims to the contrary made by formalists.
Keywords: computational linguistics, polysemy, perceptually grounded semantics, neural networks, partially structured connectionism. 000754 An Abductive Framework for Generalized Logic Programs: Preliminary Report Gerhard Brewka tr-92-049 1992 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-049.pdf We present an abductive semantics for generalized propositional logic programs which defines the meaning of a logic program in terms of its extensions. This approach extends the stable model semantics for normal logic programs in a natural way. The new semantics is equivalent to stable semantics for a logic program $P$ whenever $P$ is normal and has a stable model. The existence of extensions is guaranteed for all normal programs. The semantics can be applied without further modification to generalized logic programs where disjunctions and negation signs may appear in the head of rules. Our approach is based on an idea recently proposed by Konolige for causal reasoning. Instead of maximizing in abduction the set of used hypotheses alone we maximize the union of the used and refuted hypotheses. 000755 The Degrees of Discontinuity of some Translators between Representations of the Real Numbers Klaus Weihrauch tr-92-050 1992 07 __ 000006 Representations like decimal representation are used for defining computability on the set of real numbers. Translatability between different representations has been studied in the past by several authors. Most of the not computably solvable translation problems are not even continuously solvable. In this paper the degrees of discontinuity of translations between a number of common representations are compared and characterized. Mainly three degrees are considered: the first one with translations between the standard representation and the weak cut representations, the second one contains among others the translations between ``m''-adic and ``n''-adic representations, and the third one contains translations concerning proper cut representations and the iterated fraction representation. 000756 Improved Parallel Polynomial Division and Its Extensions Dario Bini, Victor Pan tr-92-051 1992 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-051.pdf We compute the first N coefficients of the reciprocal r(x) of a given polynomial p(x), (r(x)p(x)=1 mod x^N, p(0) not equal to 0), by using, under the PRAM arithmetic models, O(h log N) time-steps and O((N/h)(1+2^{-h}log^{(h)}N)), processors, for any h, h=1, 2,... log^*N, provided that O(log m) steps and m processors suffice to perform DFT on m points and that log^{(0), N=N, log^{(h)}N = log_2 log ^{(h-1)}N, h=1,...,log^*N, log^*N = max{h: \log^{(h)} N > 0. The same complexity estimates apply to some other computations, such as the division with a remainder of two polynomials of degrees O(N) and the inversion of an N times N triangular Toeplitz matrix. This improves the known estimates of Reif-Tate and Georgiev. We also show how to extend our techniques to parallel implementation of other recursive processes, such as the evaluation modulo x^N of the m^th root, p(x)^{1/m, of p(x) (for any fixed natural m), for which we need 0(log N log log N) time-steps and O(N/log log N) processors. The paper demonstrates some new techniques of supereffective slowdown of parallel algebraic computations, which we combine with a technique of stream contraction. 000757 Improved Parallel Computations with Toeplitz-like and Hankel-like Matrices Dario Bini, Victor Pan tr-92-052 1992 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-052.pdf The known parallel algorithms for computations with general Toeplitz, Hankel, Toeplitz-like, and Hankel-like matrices are inherently sequential. We develop some new techniques in order to devise fast parallel algorithms for such computations, including the evaluation of Krylov sequences for such matrices, traces of their power sums, characteristic polynomials and generalized inverses. This has further extensions to computing the solution or a least-squares solution to a linear system of equations with such a matrix and to several polynomial evaluations (such as computing gcd, lcm, Pade approximation and extended Euclidean scheme for two polynomials), as well as to computing the minimum span of a linear recurrence sequence. The algorithms can be applied over any field of constants, with the resulting dvantages of using modular arithmetic. The algorithms consist of imple computational blocks (mostly reduced to fast Fourier transforms, FFT's) and have potential practical value. We also develop the techniques for extending all our results to the case of matrices representable as the sums of Toeplitz-like and Hankel-like matrices and in addition show some more minor innovations, such as an improvement of the transition to the solution to a Toeplitz linear system Tx=b from two computed columns of T^-1. 000758 A Mechanism for Dynamic Re-routing of Real-time Channels Colin Parris, Hui Zhang, Domenico Ferrari tr-92-053 1992 08 __ 000006 Various solutions have been proposed to provide real-time services (i.e., services with guaranteed performance requirements) in packet-switched networks. These solutions usually require fixed routing and resource reservation for each conversation. The routing and reservation decisions, combined with load fluctuations, introduce the problems of network unavailability and loss of network management flexibility. We believe that these problems can be alleviated by properly balancing the network load. In this paper, we present a mechanism that dynamically reroutes a real-time channel without disruption of service to the clients. This mechanism is one component in a framework to investigate load balancing in a real-time internetwork. We show that the mechanism can be incorporated into the Tenet real-time protocol suite with minimal changes and overhead. 000759 Process Grammar Processor: An Architecture for a Parallel Parser Massimo Marino tr-92-054 1992 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-054.pdf A parallel architecture of a parser for Natural Language is described. A serial architecture has been already realized and is currently used in a system for the design and testing of Natural Language grammars and the generation of the corresponding parsers. This system works using a Process Grammar Processor running a model of grammar suited for the generation of Natural Language applications. The grammar model, named Process Grammar (PG), is an extension of an augmented context-free phrase-structure grammar, and the parser is designed to use such a grammar model. A PG is a set of rules that are treated by the processor as descriptors of processes that are scheduled and applied if the conditions for their execution hold: from this the name Process Grammar. In this report the PG model is extended in order to allow a more structured and modular construction of grammars, even of big dimensions, keeping separated parsing control, and syntactic and semantic specifications, partitioning a PG in clusters of rules, completely independent one from each other, carrying on their own dedicated recognition of specific parts of speech. The parallel architecture is composed by parallel processes cooperating and communicating by means of a message passing protocol. This allows the realization of some parsing strategies and the implementation of parsing mechanisms extending the recognition capacity of the parser that could not be possible in a standard and serial context-free parsing environment. Both serial and parallel versions of the parser are introduced and described, looking in greater detail the mechanisms of process scheduling and how they can be used and extended for implementing various cases of parsing strategies. 000760 A New Approach to Fast Polynomial Interpolation and Multipoint Evaluation Victor Pan tr-92-055 1992 08 __ 000006 The fastest known algorithms for the problems of polynomial evaluation and multipoint interpolation are devastatingly unstable numerically because of their recursive use of polynomial divisions. We apply a completely distinct approach to compute approximate sollutions to both problems equally fast but with improved numerical stability. Our approach relies on new techniques, so far not used in this area: we reduce the problems to Vandermonde matrix computations and then exploit some recent methods for improving computations with structured matrices. 000761 On-line Graph Algorithms for Incremental Compilation Alberto Marchetti-Spaccamela, Umberto Nanni, Hans Rohnert tr-92-056 1992 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-056.pdf Compilers usually construct various data structures which often vary only slightly from compilation run to compilation run. This paper gives various solutions to the problems of quickly updating these data structures instead of building them from scratch each time. All problems we found can be reduced to graph problems. Specifically, we give algorithms for updating data structures for the problems of topological order, loop detection, and reachability from the start routine. 000762 Describing and Recognizing Shape through Size Functions Claudio Uras, Alessandro Verri tr-92-057 1992 09 __ 000006 According to a recent mathematical theory the intuitive concept of shape can be formalized through functions, named "size functions", which convey information on both the topological and metric properties of the viewed shape. In this paper the main concepts and results of the theory are first reviewed in a somewhat intuitive fashion. Then, an algorithm for the computation of discrete size functions is presented. Finally, by introducing a suitable distance function, it is shown that size functions can be successfully used for both shape description and recognition from real images. 000763 Planar Passive Navigation: One Dimension is Better than Two Enrico De Micheli, Alessandro Verri tr-92-058 1992 11 __ 000006 This paper is based on the observation that if a viewing camera is appropriately mounted on a vehicle which moves on a planar surface, i.e. the image plane of the camera is orthogonal to the planar surface and the optical axis parallel to the instantaneous direction of translation, then the angular velocity is the only motion parameter to be computed. Consequently, the problem of motion and structure recovery from optical flow becomes linear and, in principle, can be solved locally. Elementary error analysis shows that the angular velocity can be robustly estimated by averaging the horizontal component of the optical flow along the vertical line through the center of the image. Once the angular velocity has been recovered, depth can be computed from one component only of the optical flow. It is shown that the accuracy in the estimation of depth from the vertical component is more accurate, increases with the distance from the horizontal liine through the center of the image, and is almost independent of the angular velocity. From the reported experiments on synthetic data and real images it can be concluded that in applications like autonomous robot navigation the computation of the two-dimensional (2D) optical flow over the entire 2D image plane can be probably avoided. 000764 Learning Topology-Preserving Maps Using Self-Supervised Backpropagation on a Parallel Machine Arnfried Ossen tr-92-059 1992 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-059.pdf Self-supervised backpropagation is an unsupervised learning procedure for feedforward networks, where the desired output vector is identical with the input vector. For backpropagation, we are able to use powerful simulators running on parallel machines. Topology-preserving maps, on the other hand, can be developed by a variant of the competitive learning procedure. However, in a degenerate case, self-supervised backpropagation is a version of competitive learning. A simple extension of the cost function of backpropagation leads to a competitive version of self-supervised backpropagation, which can be used to produce topographic maps. We demonstrate the approach applied to the Traveling Salesman Problem (TSP). The algorithm was implemented using the backpropagation simulator (CLONES) on a parallel machine (RAP). 000765 Ring Array Processor: Programmer's Guide to the RAP Libraries Michael C. Greenspon tr-92-060 1992 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-060.pdf The RAP machine is a high performance DSP-based distributed memory parallel processor developed at ICSI as described in previous technical reports. This report documents the application program interfaces to the high-level computational routines provided by the RAP class libraries corresponding to software release 1.0. It is intended as both an introductory guide and standard library reference for C++ and C programmers undertaking software development for the RAP machine. The RAP library classes and methods documented in this report transparently implement data-parallel operations on distributed memory objects. Thus client programs written to these interfaces automatically achieve scalability across different sized RAP machines. Additionally, the high-level interfaces provide a degree of general hardware independence, increasing the likelihood that client code will port easily to future parallel platforms under development at ICSI. This report also provides an introduction to the internals of the distributed object implementation with tips and examples for programmers wishing to extend the libraries in a structured fashion. 000766 Can we Utilize the Cancellation of the Most Significant Digits? Victor Pan tr-92-061 1992 12 __ 000006 If the sum of several positive and negative numbers has a small magnitude, relative to the magnitudes of the summands, then we show how to decrease the precision of the computation of this sum (without affecting the output precision). Furthermore, if the magnitude of the inner product of two vectors is small and if one of them is filled with "short" binary numbers, each represented with only a few bits, then we decrease the precision of the computation of such an inner product (without affecting the output precision), and we extend this result to the iterative improvement algorithm for a linear system of equations, whose coefficients are represented by "short" binary numbers. We achieve this by truncating both the least and the most significant digits of the operands, according to our new scheme of "backward binary segmentation". 000767 The Acquisition of Lexical Semantics for Spatial Terms: A Connectionist Model of Perceptual Categorization Terry Regier tr-92-062 1992 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-062.pdf This thesis describes a connectionist model which learns to perceive spatial events and relations in simple movies of 2-dimensional objects, so as to name the events and relations as a speaker of a particular natural language would. Thus, the model learns perceptually grounded semantics for natural language spatial terms. The design and construction of this system have resulted in several technical contributions. The first is a very simple but effective means of learning without explicit negative evidence. This thesis also presents the notion of partially-structured connectionism, a marriage of structured and unstructured network design techniques capturing the best of each paradigm. Finally, the idea of learning within highly specialized structural devices is introduced. Scientifically, the primary result of the work described here is a computational model of the acquisition of visually grounded semantics. This model successfully learns terms for spatial events and relations from a range of languages with widely differing spatial systems, including English, Mixtec (a Mexican Indian language), German, Bengali, and Russian. And perhaps most importantly, the model does more than just recapitulate the data; it also generates a number of falsifiable linguistic predictions regarding the sorts of semantic features, and combinations of features, one might expect to find in lexemes for spatial events and relations in the world's natural languages. 000768 Block Korkin-Zolotarev Bases and Successive Minima C. P. Schnorr tr-92-063 1992 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-063.pdf Using block Korkin--Zolotarev bases we improve Babai's construction of a nearby lattice point. Given a block Korkin--Zolotarev basis with block size beta of the lattice L and given a point x in the span of L, a lattice point v can be found in time beta^{O(beta)} satisfying |x-v|^2 less then or equal to m gamma^{2m/{beta-1}_beta min_u epsilon L} |x-u|. These results also bear improvements for the method of solving integer programming problems via basis reduction. 000769 Competitive Analysis of Financial Games R. El-Yaniv, A. Fiat, R. Karp, G. Turpin tr-92-064 1992 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-064.pdf In the unidirectional conversion problem an on-line player is given the task of converting dollars to yen over some period of time. Each day, a new exchange rate is announced, and the player must decide how many dollars to convert. His goal is to minimize the competitive ratio, defined as sup_E P_OPT(E)\P_{X}(E), where E ranges over exchange rate sequences, P_OPT(E) is the number of yen obtained by an optimal off-line algorithm, and P_{X}(E) is the number of yen obtained by the on-line algorithm X. We also consider a continuous version of the problem, in which the exchange rate varies over a continuous time interval. The on-line player's a priori information about the fluctuation of exchange rates distinguishes different variants of the problem. For three variants we show that a simple threat-based strategy is optimal for the on-line player and determine its competitive ratio. We also derive and analyze an optimal policy for the on-line player when he knows the probability distribution of the maximum value that the exchange rate will reach. Finally, we consider a bidirectional conversion problem, in which the player may trade dollars for yen or yen for dollars. 000770 The Impact of Multimedia Data on Database Management Systems Karl Aberer, Wolfgang Klas tr-92-065 1992 09 __ 000006 NOTE: Many have reported problems printing this file. Thus we have renamed it with a .BAD tag. We offer this techreport "as-is" and cannot offer help printing it. This paper analyzes the impact of multimedia data on database management systems and proposes some solutions which allow for a high degree of integrated handling of multimedia data by a multimedia database system. We first give a characterization of multimedia data with respect to issues like time dependency and amount of data. Then we derive major requirements which need to be satisfied in order to provide the integration. These requirements include e.g., dynamic data management, non-transparent parallelism, scheduling, several kinds of abstractions, resource distribution transparency, and advanced interaction models satisfying real time constraints. We show how some of the requirements can be met by exploiting concepts from the object-oriented paradigm and database systems. Then we discuss extensions needed with respect to data integration, scheduling, parallelism, and real time streams. 000771 Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology Farid Alizadeh, Richard M. Karp, Lee A. Newberg, Deborah K. Weisser tr-92-066 1993 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-92-066.pdf A fundamental tool for exploring the structure of a long DNA sequence is to construct a ``library'' consisting of many cloned fragments of the sequence. Each fragment can be replicated indefinitely and then ``fingerprinted'' to obtain partial information about its structure. A common type of fingerprinting is restriction fingerprinting, in which an enzyme called a restriction nuclease cleaves the fragment wherever a particular short sequence of nucleotides (letters `A', `G', `C', and `T') occurs, and the lengths of the resulting pieces are measured. An important combinatorial problem is to determine, from such fingerprint information, the most probable arrangement of the cloned fragments along the overall sequence. However, for a given arrangement, even the likelihood function involves a complicated multifold integral and therefore difficult to compute. We propose an approximation to the likelihood function and develop local search algorithms based on this approximate objective function. Our local search techniques are extensions of similar strategies for the travelling salesman problem. We provide some computational results which support our choice of objective function. We also briefly study alternative approaches based on pairwise probabilities that two fragments overlap. 000772 Integrating a Relational Database System into VODAK using its Metaclass Concept W. Klas, G. Fischer, K. Aberer tr-92-067 1992 08 __ 000006 This paper presents a specific approach of integrating a relational database system into a federated database system. The underlying database integration process consists of three steps: first, the external database systems have to be connected to the integrated database system environment and the external data models have to be mapped into a canonical data model. This step is often called syntactic transformation including structural enrichment and leads to component schemas for each external DBMS. Second, the resulting schemas from the first step are used to construct export schemas which are then integrated into global, individual schemas or views. In this paper we focus on the first step for relational databases, i.e., the connection of a relational database system and the mapping of the relational model into a canonical data model. We take POSTGRES as the relational database system and the object-oriented federated database system VODAK as the integration platform which provides the open, object-oriented data model as the canonical data model for the integration. We show different variations of mapping the relational model. By exploiting the metaclass concept provided by VML we show how to tailor VML such that the canonical data model meets the requirements of integrating POSTGRES into the global database system VODAK in an efficient way. 000773 Public Randomness in Cryptography Amir Herzberg, Michael Luby tr-92-068 1992 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-068.pdf The main contribution of this paper is the introduction of a formal notion of public randomness in the context of cryptography. We show how this notino affects the definition of the security of a cryptoigraphic primitive and the definition of how much security is preserved when one cryptographic primitive is reduced to another. Previous works considered the public random bits as a part of the input, and security was parameterized in terms of the total length of the input. We parameterize security solely in terms of the length of the private input, and treat the public random bits as a separate resource. This separation allows us to independently address the important issues of how much security is preserved by a reduction and how many public random bits are used in the reduction.
To exemplify these new definitions, we present reductions from weak one-way permutations to one-way permutations with strong security preserving properties that are simpler than previously known reductions. 000774 Inductive learning of compact rule sets by using effcient hypotheses reduction Thomas Koch tr-92-069 1992 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-069.pdf A method is described which reduces the hypotheses space with an efficient and easily interpretable reduction criteria called a - reduction. A learning algorithm is described based on a - reduction and analyzed by using probability approximate correct learning results. The results are obtained by reducing a rule set to an equivalent set of kDNF formulas. The goal of the learning algorithm is to induce a compact rule set describing the basic dependencies within a set of data. The reduction is based on criterion which is very flexible and gives a semantic interpretation of the rules which fulfill the criteria. Comparison with syntactical hypotheses reduction show that the a - reduction improves search and has a smaller probability of missclassification. 000775 On Randomized Algebraic Test Complexity Peter Buergisser, Marek Karpinski, Thomas Lickteig tr-92-070 1992 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-070.pdf We investigate the impact of randomization on the complexity of deciding membership in a (semi-)algebraic subset $X \subset \rr^m$. Examples are exhibited where allowing for a certain error probability $\epsilon$ in the answer of the algorithms the complexity of decision problems decreases. A randomized $(\Omega^k,\{=,\leq\})$-decision tree ($k \subseteq\rr$ a subfield) over $m$ will be defined as a pair $(T,\mu)$ where $\mu$ a probability measure on some $\rr^n$ and $T$ is a $(\Omega^k,\{=,\leq\})$- decision tree over $m+n$. We prove a general lower bound on the average decision complexity for testing membership in an irreducible algebraic subset $X \subset \rr^m$ and apply it to $k$-generic complete intersection of polynomials of the same degree, extending results in [4, 6]. We also give applications to nongeneric cases, such as graphs of elementary symmetric functions, $\mbox{SL}(m,\rr)$, and determinant varieties, extending results in \cite{Li:90}. 000776 An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3 Elias Dahlhaus, Marek Karpinski, Peter Kelsen tr-92-071 1992 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-071.pdf The paper considers the problem of computing a maximal independent set in a hypergraph (see \cite{BL} and \cite{KR}). We present an efficient deterministic NC algorithm for finding a maximal independent set in a hypergraph of dimension $3$: the algorithm runs in time $O(\log^4 n)$ time on $n+m$ processors of an EREW PRAM and is optimal up to a polylogarithmic factor. Our algorithm adapts the technique of Goldberg and Spencer (\cite{GS}) for finding a maximal independent set in a graph (or hypergraph of dimension $2$). It is the first efficient NC algorithm for finding a maximal independent set in a hypergraph of dimension greater than 2. 000777 Network Support For Multimedia: A Discussion of the Tenet Approach Domenico Ferrari, Anindo Banerjea, Hui Zhang tr-92-072 1992 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-072.pdf Multimedia communication can be supported in an integrated-services network in the general framework of realtime communication. The Tenet Group has devised an approach that provides some initial solutions to the realtime communication problem. This paper attempts to identify the principles behind these solutions. We also describe a suite of protocols, and their implementations in several environments, that embody these principles, and work in progress that will lead towards more complete solutions. 000778 Optimal Traversal of Directed Hypergraphs Giorgio Ausiello, Giuseppe F. Italiano, Umberto Nanni tr-92-073 1992 09 __ 000006 A ``directed hypergraph'' is defined by a set of nodes and a set of ``hyperarcs'', each of which connects a set of ``source'' nodes to a single ``target'' node. Directed hypergraphs are used in several contexts to model different combinatorial structures, such as functional dependencies [20], Horn clauses in propositional calculus [6], AND-OR graphs [17], Petri nets [18]. A ``hyperpath'', similarly to the analogous notion of path in directed graphs, consists of a connection among nodes using hyperarcs. Unlike paths in graphs, hyperpaths are suitable of different definitions of measure, corresponding to different concepts arising in various applications.
In this paper we consider the problem of finding optimal hyperpaths according to several optimization criteria. We show that some of these problems are NP-hard but, if the measure function on hyperpaths matches certain conditions (namely if it is ``value-based''), the problem turns out to be tractable. We describe efficient algorithms and data structures to find optimal hyperpaths which can be used with any value-based measure function, since it appears in parametric form. The achieved time bound is O(|H| + n log n) for a hypergraph with n nodes and an overall description of size |H|. Dynamic maintenance of optimal hyperpaths is also considered, and the proposed solution supports insertions of hyperarcs. 000779 When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem? Alan Frieze, Richard Karp, Bruce Reed tr-92-074 1992 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-074.pdf We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem ATSP(M) and the value of its assignment relaxation AP(M). We assume here that the costs are given by an n\times n matrix M whose entries are independently and identically distributed. We focus on the relationship between Pr(ATSP(M)=AP(M)) and the probability p_n that any particular entry is zero. If np_n\rightarrow \infty with n then we prove that ATSP(M)=AP(M) with probability 1-o(1). This is shown to be best possible in the sense that if np(n)\rightarrow c, c>0 and constant, then Pr(ATSP(M)=AP(M))<1-\phi(c) for some positive function phi. Finally, if np_n\rightarrow 0 then Pr(ATSP(M)=AP(M))\rightarrow 0. 000780 Genetic and Non Genetic Operators in Alecsys - Revised Version Marco Dorigo tr-92-075 1992 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-075.pdf It is well known that standard learning classifier systems, when applied to many different domains, exhibit a number of problems: payoff oscillation, difficult to regulate interplay between the reward system and the background genetic algorithm (GA), rule chains instability, default hierarchies instability, are only a few. Alecsys is a parallel version of a standard learning classifier system (CS), and as such suffers of these same problems. In this paper we propose some innovative solutions to some of these problems. We introduce the following original features. Mutespec, a new genetic operator used to specialize potentially useful classifiers. Energy, a quantity introduced to measure global convergence in order to apply the genetic algorithm only when the system is close to a steady state. Dynamical adjustment of the classifiers set cardinality, in order to speed up the performance phase of the algorithm. We present simulation results of experiments run in a simulated two-dimensional world in which a simple agent learns to follow a light source.
Keywords: learning classifier systems, genetic algorithms, robotics. 000781 Approximate Evaluation of a Polynomial on a Set of Real Points Victor Pan tr-92-076 1992 11 __ 000006 The previous best algorithm for approximate evaluation of a polynomial on a real set was due to Rokhlin and required the order of mu + (nu superscript 3) infinite precision arithmetic operations to approximate [on a fixed bounded set X(m) of m + 1 real points] a degree n polynomial p(x) = (sum (superscript n) (subscript i=0)) (p subscript i) (x superscript i) within the error bound (2 superscript -u) (sum (superscript n) (subscript i=0)) |p subscript i|. We develop an approximation algorithm, which decreases Rokhlin's record estimate to O(m (log superscript 2) u + n min (u, log n)). For log u = o(log n), this result may also be favorably compared with the record bound O((m+n) (log superscript 2) n) on the complexity of the exact multipoint polynomial evaluation. The new algorithm can be performed in the fields (or rings) generated by the input values, which enables us to decrease the precision of the computations [by using modular (residue) arithmetic] and to simplify our computations further in the case where u = O(log n). Our algorithm allows NC and simultaneously processor efficient parallel implementation. Because of the fundamental nature of the multipoint polynomial evaluation, our results have further applications to numerical and algebraic computational problems. By passing, we also show a substantial improvement in the Chinese remainder algorithm for integers based on incorporating Kaminski's fast residue computation. 000782 Polynomial Uniform Convergence and Polynomial-Sample Learnability Alberto Beroni, Paola Campadelli, Anna Morpurgo, Sandra Panizza tr-92-077 1992 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-077.pdf In the PAC model, polynomial-sample learnability in the distribution dependent framework has been characterized in terms of minimun cardinality of $\epsilon$-covers. In this paper we propose another approach to the problem by investigating the relationship between polynomial-sample learnability and uniform convergence, in analogy to what was done for the distribution free setting. First of all, we introduce the notion of polynomial uniform convergence, giving a characterization for it in terms of an entropic measure, then we study its relationship with polynomial- sample learnability. We show that, contrarily to what happens in the distribution independent setting, polynomial uniform convergence is a sufficient but not necessary condition for polynomial-sample learnability. 000783 On Randomized Versus Deterministic Computation Marek Karpinski, Rutger Verbeek tr-92-078 1992 11 __ 000006 In contrast to deterministic or nondeterministic computation, it is a fundamental open problem in randomized computation how to separate different randomized time classes (at this point we do not even know how to separate linear randomized time from O(n superscript (log n)) randomized time) or how to compare them relative to corresponding deterministic time classes. In another words we are far from understanding the power of ``random coin tosses'' in the computation, and the possible ways of simulating them deterministically.
In this paper we study the relative power of linear and polynomial randomized time compared with exponential deterministic time. Surprisingly, we are able to construct an oracle A such that exponential time (with or without the oracle A) is simulated by linear time Las Vegas algorithms using the oracle A. We are also able to prove, for the first time, that in some situations the randomized reductions are exponentially more powerful than deterministic ones (cf. [Adleman, Manders, 1977]).
Furthermore, a set B is constructed such that Monte Carlo polynomial time (BPP) under the oracle B is exponentially more powerful than deterministic time with nondeterministic oracles. This strengthens considerably a result of Stockmeyer [St85] about the polynomial time hierarchy that for some decidable oracle B, (BPP superscript B) (not subseteq)(Delta subscript 2)(P superscript B). Under our oracle BPP superscript B is exponentially more powerful than (Delta subscript 2)(P superscript B), and B does not add any power to (Delta subscript 2)(EXPTIME). 000784 Computation of the Additive Complexity of Algebraic Circuits with Root Extracting Marek Karpinski, Rutger Verbeek tr-92-079 1992 11 __ 000006 We design an algorithm for computing the generalized (algebraic circuits with root extraction) ``additive complexity'' of any rational function. It is the first computability result of this sort on the additive complexity of algebraic circuits (cf. [SW80]). 000785 Simulating Threshold Circuits by Majority Circuits Mikael Goldmann, Marek Karpinski tr-92-080 1992 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-080.pdf We prove that a single threshold gate can be simulated by an explicit polynomial size depth 2 majority circuit. In general we show that a depth d threshold circuit can be simulated uniformly by a majority circuit of depth d+1. Goldmann, Hastad and Razborov demonstrated that a non-uniform simulation exists. Our construction answers two open questions posed in their work: We give an explicit construction whereas Goldmann, Hastad and Razborov use a randomized existence argument, and we show that such a simulation is possible even if the depth d grows with the number of variables n (the simulation in their work gives polynomial size circuits only when d is constant). 000786 Connectionist Probability Estimation in HMM Speech Recognition Steve Renals, Nelson Morgan tr-92-081 1992 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-081.pdf This report is concerned with integrating connectionist networks into a hidden Markov model (HMM) speech recognition system. This is achieved through a statistical understanding of connectionist networks as probability estimators, first elucidated by Herve- Bourlard. We review the basis of HMM speech recognition, and point out the possible benefits of incorporating connectionist networks. We discuss some issues necessary to the construction of a connectionist HMM recognition system, and describe the performance of such a system, including evaluations on the DARPA database, in collaboration with Mike Cohen and Horacio Franco of SRI International. In conclusion, we show that a connectionist component improves a state of the art HMM system. 000787 Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions Moni Naor, Rafail Ostrovsky tr-92-082 1992 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-082.pdf "Zero-knowledge arguments" is a fundamental cryptographic primitive which allows one polynomial-time player to convince another polynomial-time player of the validity of an NP statement, without revealing any additional information in the information-theoretic sense. Despite their practical and theoretical importance, it was only known how to implement zero-knowledge arguments based on specific algebraic assumptions; basing them on a general complexity assumption was open since their introduction in 1986 [BCC, BC, CH]. In this paper, we finally show a general construction, which can be based on any one-way permutation.
We stress that our scheme is "efficient": both players can execute only polynomial-time programs during the protocol. Moreover, the security achieved is "on-line": in order to cheat and validate a false theorem, the prover must break a cryptographic assumption on-line "during the conversation", while the verifier can not find (ever!) any information unconditionally (in the information theoretic sense). 000788 Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent Shafi Goldwasser, Rafail Ostrovsky tr-92-083 1992 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-083.pdf The standard definition of digital signatures allows a document to have many valid signatures. In this paper, we consider a subclass of digital signatures, called invariant signatures, in which all legal signatures of a document must be identical according to some polynomial-time computable function (of a signature) which is hard to predict given an unsigned document. We formalize this notion and show its equivalence to non-interactive zero-knowledge proofs. 000789 Implicit Parallelism in Genetic Algorithms Alberto Bertoni, Marco Dorigo tr-93-001 1993 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-001.pdf This paper is related to Holland's result on implicit parallelism. Roughly speaking, Holland showed a lower bound of the order of (n^3)/(c1*sqrt(l)) to the number of schemata usefully processed by the genetic algorithm in a population of n=c1*2^l binary strings, with c1 a small integer. We analyze the case of population of n = 2*beta*l binary strings where beta is a positive parameter (Holland's result is related to the case beta=1). In the main result, for all beta>0 we state a lower bound on the expected number of processed schemata; moreover, we prove that this bound is tight up to a constant for all beta>=1 and, in this case, we strengthen in probability the previous result.
Keywords: genetic algorithms, implicit parallelism. 000790 Optimization Problems: Expressibility, Approximation Properties and Expected Asymptotic Growth of Optimal Solutions T. Behrendt, K. Compton, E. Graedel tr-93-002 1993 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-002.pdf We extend the recent approach of Papadimitrou and Yannakakis that relates the approximation properties of optimization problems to their logical representation.
Our work builds on results by Kolaitis and Thakur who sytematically studied the expressibility classes MS_n and MP_n of maximization problems and showed that they form a short hierarchy of four levels. The two lowest levels, MS_0 and MS_1 coincide with the classes Max Snp and Max Np of Papadimitriou and Yannakakis; they contain on ly problems that are approximable in polynomial time up to a constant factor and thus provide a logical criterion for approximability. However, there are computationally very easy maximization problems, such as Maximum Connected Component (MCC) that fail to satisfy this criterion.
We modify these classes by allowing the formulae to contain predicates that are definable in least fixpoint logic. In addition, we maximize not only over relations but also over constants. We call the extended classes MSF_i and MPF_i. The proof of Papadimitriou and Yannakakis can be extended to MSF_1 to show that all problems in this class are approximable. Some problems, such as MCC, descend from the highest level in the original hierarchy to the lowest level MSF_0 in the new hierarchy. Thus our extended class MSF_1 provides a more powerful sufficient criterion for approximability than the original class MS_1.
We separate the extended classes and prove that a number of important problems do not belong to MSF_1. These include Max Clique, Max Independent Set, V-C Dimension and Max Common Induced Subgraph.
To do this we introduce a new method that characterizes rates of growth of aveage optimal solution sizes. For instance, it is known that the expected size of a maximal clique in a random graph grows logarithmically with respect to the cardinality of the graph. We show that no problem in MSF_1 can have this property, thus proving that Max Clique is not in MSF_1. This technique is related to limit laws for various logics and to the probabilistic method from combinatorics. We believe that this method may be of independent interest.
In contrast to the recent results on the non-approximability of many maximization problems, among them Max Clique, our results do not depend on any unproved hypothesis from complexity theory, such as P does not equal NP. 000791 Simple Multivariate Polynomial Multiplication Victor Pan tr-93-003 1993 08 __ 000006 We observe that polynomial evaluation and interpolation can be performed fast over a multidimensional grid (lattice), and we apply this observation in order to obtain the bounds M(c,m) is greater than or equal to (c superscript m)(1 + m + 1.5m + 2 (log subscript 2) c) over the fields of constants supporting FFT on c points, c being a power of 2, and M (c, m) = 0[N log N log log c], over any field, where N = (c superscript m), and M (c, m) denotes the number of arithmetic operations required in order to multiply (over any field F) a pair of m-variate polynomials whose product has degree at most c - 1 in each variable, so that M (c, m) = 0(N log N) if c=0(1), m right arrow infinity (over any field F), versus the known bound of O (N log N log log N). 000792 Mixture Models and the EM Algorithm for Object Recognition within Compositional Hierarchies. Part 1: Recognition Joachim Utans tr-93-004 1993 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-004.pdf We apply the Expectation Maximization (EM) algorithm to an assignment problem where in addition to binary assignment variables analog parameters must be estimated. As an example, we use the problem of part labelling in the context of model based object recognition where models are stored in from of a compositional hierarchy. This problem has been formulated previously as a graph matching problem and stated in terms of minimizing an objective function that a recurrent neural network solves. Mjolsness has introduced a "stochastic visual grammar" as a model for this problem; there the matching problem arises from an index renumbering operation via a permutation matrix. The optimization problem w.r.t the match variables is difficult and Mean Field Annealing techniques are used to solve it. Here we propose to model the part labelling problem in terms of a mixture of distributions, each describing the parameters of a part. Under this model, the match variables correspond to the a posteriori estimates of the mixture coefficients. The parts in the input image are unlabelled, this problem can be stated as missing data problem and the EM algorithm can be used to recover the labels and estimate parameters. The resulting update equations are identical to the Elastic Net equations; however, the update dynamics differ.
Keywords: EM algorithm, object recognition, compositional hierarchy, elastic matching, mean field annealing. 000793 A Dynamic Connection Management Scheme for Guaranteed Performance Services in Packet-Switching Integrated Services Networks Colin Parris tr-93-005 1993 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-005.pdf With the demand for multimedia and computational science applications, guaranteed performance communication services have become a necessary feature of future high-speed networks. These communications services should possess a high level of sophistication so that they can easily adapt the network to the wide variety of applications soon to be seen, thereby allowing the network to increase its availability and flexibility. Availability is the ability of the network to accommodate as many real-time clients as possible without violating any client's performance guarantees, while flexibility is the ability to adapt to changing network state and client demands in order to maintain the performance guarantees and quality of service promised to the client. Flexibility also refers to the ability of the network to easily increase the variety of real-time services that it offers. It is our contention that availability and flexibility can be enhanced in a network by providing the network with the ability to modify the performance parameters and/or the route of any guaranteed performance connection in the network without violating the previously made performance contracts.
In this paper, we present a scheme for dynamically managing guaranteed performance service connections and experimental results to verify the correctness and usefulness of the scheme. The motivation for this scheme, Dynamic Connection Management (DCM), is discussed, and detailed descriptions of the DCM modification contracts and algorithms are provided. A survey of guaranteed performance services protocols, architectures, and routing algorithms are presented together with their relevance to this work. A simulator has been built, and preliminary experiments and analyses were done on the scheme. The paper concludes with a summary and some topics for future work. 000794 A Characterization of Multi-Party Interactive Multimedia Applications Clemens Szyperski, Giorgio Ventre tr-93-006 1993 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-006.pdf This document tries to define and characterize a class of applications called Multi-Party Interactive Multimedia (MIM), for which many examples are given. This class includes applications such as CSCW, teleconferencing, and remote education; its consideration in this report is based on the observation that MIM applications are both important and representative for the area of high-performance real-time communication. Purely functional criteria are used to capture the MIM class, {i.e.} ones that are not related to any particular way of implementation. Thus, future directions are sketched that give some indications on what a network architecture will need to provide, in order to effectively support such applications. 000795 On Removing Randomness from a Parallel Algorithm for Minimum Cuts Michael Luby, Joseph Naor, Moni Naor tr-93-007 1993 02 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-007.pdf The weighted minimum cut problem in a graph is a fundamental problem in combinatorial optimization. Recently, Karger suggested a randomized parallel algorithm for this problem. We show that a similar algorithm can be implemented using only $O(\log^2 n)$ random bits. We also show that our result holds for computing minimum weight k-cuts, where k is fixed. 000796 Galileo: a Tool for Simulation and Analysis of Real-Time Networks Edward W. Knightly, Giorgio Ventre tr-93-008 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-008.pdf Galileo is a flexible tool for simulation of heterogeneous real-time communication networks and for development and verification of network protocols. Galileo provides several unique features that make it particularly suitable for the simulation and analysis of networks that provide quality-of-service guarantees. First, its object-oriented programming environment provides the means for a modular, hierarchical, heterogeneous description of networks. Second, its multimedia device interface provides the tools for a qualitative analysis of network protocols. Finally, Galileo's network interface provides interaction with actual networks to access real data and simulate realistic multimedia scenarios. 000797 On Deterministic Approximation of DNF Michael Luby, Boban Velickovic tr-93-009 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-009.pdf We develop efficient deterministic algorithms for approximating the fraction of truth assignments that satisfy a disjunctive normal form formula. Although the algorithms themselves are deterministic, their analysis is probabilistic and uses the notion of limited independence between random variables. 000798 Optimal Speedup of Las Vegas Algorithms Michael Luby, Alistair Sinclair, David Zuckerman tr-93-010 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-010.pdf Let A be a Las Vegas algorithm, i.e., A is a randomized algorithm that always produces the correct answer when it stops but whose running time is a random variable. We consider the problem of minimizing the expected time required to obtain an answer from~A using strategies which simulate A as follows: run A for a fixed amount of time t_1, then run A independently for a fixed amount of time t_2, etc. The simulation stops if A completes its execution during any of the runs. Let S=(t_1,t_2,...) be a strategy, and let \ell_A=inf_{S}T(A,S), where T(A,S) is the expected value of the running time of the simulation of A under strategy S.
We describe a simple universal strategy Sopt, with the property that, for any algorithm A, T(A,S^univ)=O(\ell_A log(\ell_A)). Furthermore, we show that this is the best performance that can be achieved, up to a constant factor, by any universal strategy. 000799 Graceful Adaptation of Guaranteed Performance Service Connections Colin Parris, Giorgio Ventre, Hui Zhang tr-93-011 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-011.pdf Most of the solutions proposed to support real-time communication services in a packet-switching network adopt a connection-oriented and reservation-oriented approach. In this approach, the resource allocation and route selection decisions are made before the start of the application on the basis of resource availability and real-time network load at that time, and are usually kept for the duration of the application. However, such an approach shows two major limitations: first, the communication service provided is usually fixed, with no or limited capability of adaptation to dynamic changes in the clients' requirements; second, a low utilization of the network may be observed. In this paper, we present a flexible management scheme that allows graceful adaptation of guaranteed performance service connections. Mechanisms have been devised to allow changing of the traffic and performance parameters of a real-time communication during its lifetime. These mechanisms, together with an adaption policy, can make more efficient use of the network resources by performing cooperative, consenting, high-level multiplexing. We distinguish between two types of adaptation: client initiated adaptation and network initiated adaptation. We give examples for both types and we also present results from simulation experiments to verify the correctness our proposal. 000800 Estimation of noise spectrum and its application to SNR-estimation and speech enhancement Hans-Günter Hirsch tr-93-012 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-012.pdf One possible solution to improve recognition of noisy speech is the application of noise reduction techniques. Spectral subtraction is one well known technique to reduce stationary background noise in case of recording with a single microphone. An estimation of the noise spectrum is necessary to apply this method. The determination of segments containing just noise is usually a difficult task. This report describes a method to estimate the noise spectrum without the need of distinguishing between segments of noisy speech and segments of pure noise. The estimation of noise power inside one subband is based on an analysis of the histogram of a certain number of past short-term energy values inside this subband. This technique for estimating the noise spectrum can be used to estimate the actual signal-to-noise ratio (SNR). Another application is the integration inside a spectral subtraction technique for speech enhancement. 000801 Optimal Stochastic Quadrature Formulas For Convex Functions Erich Novak, Knut Petras tr-93-013 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-013.pdf We study optimal stochastic (or Monte Carlo) quadrature formulas for convex functions. While nonadaptive Monte Carlo methods are not better than deterministic methods we prove that adaptive Monte Carlo methods are much better. 000802 Optimal Recovery and n-Widths For Convex Classes of Functions Erich Novak tr-93-014 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-014.pdf We study the problem of optimal recovery in the case of a nonsymmetric convex class of functions. In particular we show that adaptive methods may be much better than nonadaptive methods. We define certain Gelfand-type widths that are useful for nonsymmetric classes and prove relations to optimal error bounds for adaptive and nonadaptive methods, respectively. 000803 Channel Groups: A Unifying Abstraction for Specifying Inter-stream Relationships Amit Gupta, Mark Moran tr-93-015 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-015.pdf A single distributed application typically requires setting up a number of real-time connections, or channels. Current schemes usually assume that different channels are independent, when in reality, important relationships often exist between them. We introduce a new abstraction called channel groups that allows network clients to describe these relationships explicitly to the network service provider. For example, by describing sharing relationships between channels, the network client enables the network to share resource allocations among related channels-lowering the cost and improving the scalability of communication. In addition, specification of other relationships, such as inter-stream synchronization, disjoint-path routing, relative dropping priorities, and simultaneous establishment provide a richer, more efficient service. Channel groups provide a unifying abstraction and an easily-extensible interface for specifying these and other relationships. This report presents a general description of the channel group abstraction and demonstrates its usefulness in describing several types of inter-stream relationships. 000804 Accelerated Solution of the Tridiagonal Symmetric Eigenvalue Problem Victor Pan tr-93-016 1993 03 __ 000006 We present new algorithms that accelerate the bisection method for the symmetric eigenvalue problem. The algorithms rely on some new techniques, which include acceleration of Newton's iteration and can also be further applied to acceleration of some other iterative processes, in particular, of iterative algorithms for approximating polynomial zeros. 000805 Efficient Multicasting for Interactive Multimedia Applications Clemens Szyperski, Giorgio Ventre tr-93-017 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-017.pdf A specific class of multimedia applications is expected to be of importance for future communication networks: Multi-Party Interactive Multimedia (MIM). Based on the isolation and characterization of MIM applications, concrete network support requirements are derived in this paper. The varying degree of connectivity, the vastly different sizes in terms of participants and the reliance on a guaranteed Quality of Service make MIM support a difficult problem. Starting with the definition of multimedia communication abstractions, principles of solutions are sketched. For an important subclass of applications a particularly efficient and practicable alternative implementation based on half-duplex channels is introduced. Finally, interfaces at both the transport and network layers are considered. 000806 Navigation Without Perception of Coordinates and Distances Armin Hemmerling tr-93-018 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-018.pdf We consider the target--reaching problem in plane scenes for a point robot which has a tactile sensor and can locate the target ray. It might have a compass, too, but it is not able to perceive the coordinates of its position nor to measure distances. The complexity of an algorithm is measured by the number of straight moves until reaching the target, as a function of the number of vertices of the (polygonal) scene.
It is shown how the target point can be reached by exhaustive search without using a compass, with the complexity exp(O(n^{2})). Using a compass, there is a target--reaching algorithm, based on rotation counting, with the complexity O(n^{2}).
The decision problem, to recognize if the target cannot be reached because it belongs to an obstacle, cannot be solved by our type of robot. If the behaviour of a robot without compass is periodic in a homogeneous environment, it cannot solve the target--reaching problem.
Keywords: motion planning, on-line algorithms, labyrinth problems, exhaustive search, rotation counting, trap constructions, power of compass. 000807 Matchings in Lattice Graphs (Preliminary Version) Claire Kenyon, Dana Randall, Alistair Sinclair tr-93-019 1993 03 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-019.pdf We study the problem of counting the number of matchings of given cardinality in a d-dimensional rectangular lattice. This problem arises in several models in statistical physics, including monomer-dimer systems and cell-cluster theory. A classical algorithms due to Fisher, Kasteleyn and Temperley counts perfect matchings exactly in two dimensions, but is not applicable in higher dimensions and does not allow one to count matchings of arbitrary cardinality. In this paper, we present the first efficient approximation algorithms for counting matchings of arbitrary cardinality in (i)~d-dimensional ``periodic'' lattices (i.e., with wrap-around edges) in any fixed dimension~d; and (ii)~two-dimensional lattices with ``fixed boundary conditions'' (i.e., no wrap-around edges). Our technique generalizes to approximately counting matchings in any bipartite graph that is the Cayley graph of some finite group. 000808 Design Principles of Parallel Operating Systems: ---A PEACE Case Study--- Wolfgang Schröder-Preikschat tr-93-020 1993 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-020.pdf Forthcoming massively parallel systems are distributed memory architectures. They consist of several hundreds to thousands of autonomous processing nodes interconnected by a high-speed network. A major challenge in operating system design for massively parallel architectures is to design a structure that reduces system bootstrap time, avoids bottlenecks in serving system calls, promotes fault tolerance, is dynamically alterable, and application-oriented. In addition to that, system-wide message passing is demanded to be of very low latency and very high efficiency. State of the art parallel operating systems design must obey the maxim not to punish an application by unneeded system functions. This requires to design a parallel operating system as a family of program modules, with parallel applications being an integral part of that family, and motivates object orientation to achieve an efficient implementation.
Keywords: MIMD systems, parallel operating systems, microkernel family, object orientation 000809 CNS-1 Architecture Specification: A Connectionist Network Supercomputer Krste Asanovic, James Beck, Tim Callahan, Jerry Feldman, Bertrand Irissou, Brian Kingsbury, Phil Kohn, John Lazzaro, Nelson Morgan, David Stoutamire, John Wawrzynek tr-93-021 1993 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-021.pdf A Collaboration of the University of California, Berkeley and the International Computer Science Institute. The Connectionist Network Supercomputer, or CNS-1, is a multi-year effort to incorporate recent advances in VLSI design and application-specific computer architecture for the realization of a massively parallel machine. Application targets for the CNS-1 include connectionist networks in the areas of speech recognition, language modeling, vision, and hardware simulation for VLSI. This technical report presents the background and motivation for high-level design decisions, along with descriptions of several hardware and software elements. The document represents a "snapshot" of the design, which is expected to be operational in 1995.
Keywords: connectionist networks, VLSI, computer architecture, Torrent, Hydrant, application-specific, massively parallel. 000810 A Multivalued Evolutionary Algorithm Hans-Michael Voigt, Joachim Born, Ivan Santibanez-Koref tr-93-022 1993 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-022.pdf With this paper we present a Multivalued Evolutionary Algorithm (MEA) which is inspired by fuzzy set theory. The genetic representation and encoding is done in such a way that no inferences can be drawn from phenotype to genotype. This representation influences the used genetic operators. The basic operators of the algorithm will be explained and comparisons for global optimization problems with recently published results will be presented. 000811 Training Agents to Perform Sequential Behavior Marco Colombetti, Marco Dorigo tr-93-023 1993 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-023.pdf This paper is concerned with training an agent to perform sequential behavior. In previous work we have been applying reinforcement learning techniques to control a reactive robot. Obviously, a pure reactive system is limited in the kind of interactions it can learn. In particular, it can only learn what we call pseudo-sequences, that is sequences of actions in which the transition signal is generated by the appearance of a sensorial stimulus. We discuss the difference between pseudo-sequences and proper sequences, and the implication that these differences have on training procedures. A result of our research is that, in case of proper sequences, for learning to be successful the agent must have some kind of memory; moreover it is often necessary to let the trainer and the learner communicate. We study therefore the influence of communication on the learning process. First we consider trainer-to-learner communication introducing the concept of reinforce ment sensor, which let the learning robot explicitly know whether the last reinforcement was a reward or a punishment; we also show how the use of this sensor induces the creation of a set of error recovery rules. Then we introduce learner-to-trainer communication, which is used to disambiguate indeterminate training situations, that is situations in which observation alone of the learner behavior does not provide the trainer with enough information to decide if the learner is performing a right or a wrong move. All the design choices we make are discussed and compared by means of experiments in a simulated world.
Keywords: machine learning, adaptive systems, genetic algorithms, learning classifier systems, behavior-based robotics, reinforcement learning. 000812 Generalized Vandermonde Determinants over the Chebyshev Basis Thorsten Werther tr-93-024 1993 04 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-024.pdf The recent developments in the area of interpolation and learnability of sparse polynomials over the reals are based on the nonsingularity of the generalized Vandermonde matrix. In this paper we study real polynomials that admit sparse representations in the Chebyshev basis. The main result of the paper states the analogy of Michell's theorem for the Chebyshev case, i.e. the determinant of the generalized Vandermonde matrix build over the Chebyshev basis can be represented in this basis as the product of the standard Vandermonde determinant and a polynomial with nonnegative integer coefficients. An immediate consequence of this result is the nonsingularity of Vandermonde matrices over the Chebyshev basis provided that the indeterminates take distinct values greater 1.
As an application, we investigate the relationship between the number of real roots of a polynomial and its sparsity with respect to the Chebyshev basis. We prove that the number of real zeros of a polynomial, either to the left or to the right of the interval of orthogonality, does not exceed its sparsity with respect to the Chebyshev basis. The bound on the number of real roots is used to prove finiteness of the Vapnik- Chervonenkis dimension (and thereby uniform learnability) of the class of polynomials of bounded sparsity over the Chebyshev basis. 000813 Kohonen Feature Maps and Growing Cell Structures --a Performance Comparison Bernd Fritzke tr-93-025 1993 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-025.pdf A performance comparison of two self-organizing networks, the Kohonen Feature Map and the recently proposed Growing Cell Struc- tures is made. For this purpose several performance criteria for self-organizing networks are proposed and motivated. The models are tested with three example problems of increasing difficulty. The Kohonen Feature Map demonstrates slightly superior results only for the simplest problem. For the other more difficult and also more realistic problems the Growing Cell Structures exhibit significantly better performance by every criterion. Additional advantages of the new model are that all parameters are constant over time and that size as well as structure of the network are determined automatically.
Keywords: feature map, incremental learning, Kohonen
* Presented at NIPS 5 in Denver 000814 Growing Cell Structures - a self-organizing network for unsupervised and supervised learning Bernd Fritzke tr-93-026 1993 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-026.pdf We present a new self-organizing neural network model having two variants. The first variant performs unsupervised learning and can be used for data visualization, clustering, and vector quantization. The main advantage over existing ap- proaches, e.g., the Kohonen feature map, is the ability of the model to automatically find a suitable network structure and size. This is achieved through a controlled growth process which also includes occasional removal of units. The second variant of the model is a supervised learning method which results from the combination of the abovementioned self-organizing network with the radial basis function (RBF) approach. In this model it is possible - in con- trast to earlier approaches - to perform the positioning of the RBF units and the supervised training of the weights in parallel. Therefore, the current classification error can be used to determine where to insert new RBF units. This leads to small networks which generalize very well. Results on the two- spirals benchmark and a vowel classification problem are present- ed which are better than any results previously published.
Keywords: Self-organization, incremental learning, radial basis function, clustering, data visualization, pattern classification, two spiral problem, feature map 000815 A Stochastic Model of Actions and Plans for Anytime Planning under Uncertainty Sylvie Thiebaux, Joachim Hertzberg, William Shoaff, Moti Schneider tr-93-027 1993 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-027.pdf Building planning systems that operate in real domains requires coping with both uncertainty and time pressure. This paper describes a model of reaction plans, which are generated using a formalization of actions and of state descriptions in probabilistic logic, as a basis for anytime planning under uncertainty.
The model has the following main features. At the action level, we handle incomplete and ambiguous domain information, and reason about alternative action effects whose probabilities are given. On this basis, we generate reaction plans that specify different courses of action, reflecting the domain uncertainty and alternative action effects; if generation time was insufficient, these plans may be left unfinished, but they can be reused, incrementally improved, and finished later. At the planning level, we develop a framework for measuring the quality of plans that takes domain uncertainty and probabilistic information into account using Markov chain theory; based on this framework, one can design anytime algorithms focusing on those parts of an unfinished plan first, whose completion promises the most ``gain''. Finally, the plan quality can be updated during execution, according to additional information acquired, and can therefore be used for on-line planning. 000816 pSather: Layered Extensions to an Object-Oriented Language for Efficient Parallel Computation Stephan Murer, Jerome A. Feldman, Chu-Cheow Lim, Martina-Maria Seidel tr-93-028 1993 06 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-028.pdf pSather is a parallel extension of the existing object-oriented language Sather. It offers a shared-memory programming model which integrates both control- and data-parallel extensions. This integration increases the flexibility of the language to express different algorithms and data structures, especially on distributed-memory machines (e.g.\ CM-5). This report describes our design objectives and the programming language pSather in detail. 000817 Labeling RAAM Alessandro Sperduti tr-93-029 1993 05 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-029.pdf In this report we propose an extension of the Recursive Auto-Associative Memory (RAAM) by Pollack. This extension, the Labeling RAAM (LRAAM), is able to encode labeled graphs with cycles by representing pointers explicitly. A theoretical analysis of the constraints imposed on the weights by the learning task under the hypothesis of perfect learning and linear output units is presented. Cycles and confluent pointers result to be particularly effective in imposing constraints on the weights. Some technical problems encountered in the RAAM, such as the termination problem in the learning and decoding processes, are solved more naturally in the LRAAM framework. The representations developed for the pointers seem to be robust to recurrent decoding along a cycle. Data encoded in a LRAAM can be accessed by pointer as well as by content. The direct access by content can be achieved by transforming the encoder network of the LRAAM in a Bidirectional Associative Memory (BAM). Different access procedures can be defined according to the access key. The access procedures are not wholly reliable, however they seem to have a high likelihood of success. A geometric interpretation of the decoding process is given and the representations developed in the pointer space of a two hidden units LRAAM are presented and discussed. In particular, the pointer space results to be partitioned in a fractal-like fashion. Some effects on the representations induced by the Hopfield-like dynamics of the pointer decoding process are discussed and an encoding scheme able to retain the richness of representation devised by the decoding function is outlined. The application of the LRAAM model to the control of the dynamics of recurrent high-order networks is briefly sketched as well. 000818 Sensitivity of Boolean Functions, Harmonic Analysis, and Circuit Complexity Anna Bernasconi, Bruno Codenotti tr-93-030 1993 06 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-030.pdf We exploit the notion of sensitivity of Boolean functions to find complexity results. We first analyze the distribution of the average sensitivity over the set of all the Boolean functions, and show some applications of this analysis. We then use harmonic analysis on the cube to study how the average sensitivity of a Boolean function propagates if the function corresponds, e.g., to an oracle available to compute another function. We use this relation to prove that symmetric functions in $AC^0$ have exponentially decreasing average sensitivity. 000819 On Some Stability Properties of the LRAAM Model Alessandro Sperduti tr-93-031 1993 06 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-031.pdf In this report we discuss some mathematical properties of the LRAAM model. The LRAAM model is an extension of the RAAM model by Pollack. It allows one to obtain distributed reduced representations of labeled graphs. In particular, we give sufficient conditions on the asymptotical stability of the decoding process along a cycle of the encoded structure. Data encoded in an LRAAM can also be accessed by content by transforming the LRAAM in an analog Hopfield network with hidden units and asymmetric connection matrix (CA network.) Different access procedures can be defined according to the access key. Each access procedure corresponds to a particular constrained version of the CA network. We give sufficient conditions under which the property of asymptotical stability of a fixed point in one particular constrained version of the CA network can be extended to related fixed points of different constrained versions of the CA network. An example of encoding of a labeled graph on which the theoretical results are applied is given as well. 000820 Repetitive Hidden-Surface-Removal for Polyhedra Marco Pellegrini tr-93-032 1993 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-032.pdf The repetitive hidden-surface-removal problem can be rephrased as the problem of finding the most compact representation of all views of a polyhedral scene that allows efficient on-line retrieval of a single view. In this paper we present a novel approach to this problem. We assume that a polyhedral scene in 3-space is given in advance and is preprocessed off-line into a data structure. Afterwards, the data structure is accessed repeatedly with view-points given on-line and the portions of the polyhedra visible from each view-point are produced on-line. This mode of operation is close to that of real interactive display systems. The main difficulty is to preprocess the scene without knowing the query view-points.
Let $n$ be the number total of edges, vertices and faces of the polyhedral objects and let $k$ be the number of vertices and edges of the image. The main result of this paper is that, using an off-line data structure of size $m$ with $n^{1+\epsilon} \leq m \leq n^{2+\epsilon}$, it is possible to answer on-line hidden-surface-removal queries in time $O(k\log n + \min\{n\log n, kn^{1+\epsilon}/m^{1/2}\})$, when the scene is composed of $c$-oriented polyhedra. This data structure accommodates dynamic insertion and deletion of polyhedral objects. The polyhedra may intersect and may have cycles in the dominance relation. We also improve worst-case time/storage bounds for the repetitive hidden surface removal problem when the polyhedral scene is composed of unrestricted polyhedra.
Preliminary version of this work is in the Proceedings of the 1993 Workshop on Algorithms and Data Structures. 000821 Turning an Action Formalism Into a Planner---A Case Study Joachim Hertzberg, Sylvie Thiebaux tr-93-033 1993 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-033.pdf The paper describes a case study that explores the idea of building a planner with a neat semantics of the plans it produces, by choosing some action formalism that is ``ideal'' for the planning application and building the planner accordingly. In general---and particularly so for the action formalism used in this study, which is quite expressive---this strategy is unlikely to yield fast and efficient planners if the formalism is used naively. Therefore, we adopt the idea that the planner approximates the theoretically ideal plans, where the approximation gets closer, the more run time the planner is allowed. As the particular formalism underlying our study allows a significant degree of uncertainty to be modeled and copes with the ramification problem, we end up in a planner that is functionally comparable to modern anytime uncertainty planners, yet is based on a neat formal semantics. 000822 On Lines Missing Polyhedral Sets in 3-Space Marco Pellegrini tr-93-034 1993 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-034.pdf We show some combinatorial and algorithmic results concerning sets of lines and polyhedral objects in 3-space. Our main results include:
(1) An $O(n^32^{c\sqrt{\log n}})$ upper bound on the worst case complexity of the set of lines missing a star-shaped compact polyhedron with $n$ edges, where $c$ is a suitable constant.
(2) An $O(n^3 2^{c\sqrt{\log n}})$ upper bound on the worst case complexity of the set of lines that can be moved to infinity without intersecting a set of $n$ given lines, where $c$ is a suitable constant. This bound is almost tight.
(3) An $O(n^{1.5+\eps})$ randomized expected time algorithm that tests whether a direction $v$ exists along which a set of $n$ red lines can be translated away from a set of $n$ blue lines without collisions.
(4) Computing the intersection of two polyhedral terrains in 3-space with $n$ total edges in time $O(n^{4/3+\eps} + k^{1/3}n^{1+\eps} + k\log^2 n)$, where $k$ is the size of the output, and $\epsilon >0$ an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelle at al.
The tools used to obtain these results include Plucker coordinates of lines, random sampling and polarity transformations in 3-space.
A preliminary version of this work appeared in the Proceedings of the 9th ACM Symposium on Computational Geometry. 000823 Perturbation: An Efficient Technique for the Solution of Very Large Instances of the Euclidean TSP B. Codenotti, G. Manzini, L. Margara, G. Resta tr-93-035 1993 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-035.pdf In this paper we introduce a technique for building efficient iterated local search procedures. This technique, that we call perturbation, uses global information on TSP instances to speed-up and improve the quality of the tours found by heuristic methods. The experimental results done on up to 100,000 cities, show that our techniques outperform the known methods for iterating local search for very large instances.
Keywords: TSP, sensitivity, perturbation, heuristics, experimental evaluation. 000824 Sparse Interpolation from Multiple Derivatives Thorsten Werther tr-93-036 1993 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-036.pdf In this note, we consider the problem of interpolating a sparse function from the values of its multiple derivatives at some given point. We give efficient algorithms for reconstructing sparse Fourier series and sparse polynomials over Sturm-Liouville bases. In both cases, the number of evaluations is linear in the sparsity. 000825 An Algorithm to Learn Read-Once Threshold Formulas, and some generic Transformations between Learning Models (Revised Version) Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski tr-93-037 1993 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-037.pdf We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. We also present a catalogue of generic transformations that can be used to convert an algorithm in one learning model into an algorithm in a different model. 000826 Exploitation of Structured Gating Connections for the Normalization of a Visual Pattern Alessandro Sperduti tr-93-038 1993 07 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-038.pdf Structured gating connections can be useful to reduce the complexity of networks with a high number of inputs. An example of their application to the normalization of a visual pattern with respect to scale and position is presented. The use of gating connections allows us to have a linear number of connections in the number of pixels. The connections are also very localized. 000827 Building convex space partitions induced by pairwise interior-disjoint simplices Marco Pellegrini tr-93-039 1993 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-039.pdf Given a set $S$ of $n$ pairwise interior-disjoint $(d-1)$-simplices in $d$-space, for $d \geq 3$, a Convex Space Partition induced by $S$ (denoted $CSP(S)$) is a partition of $d$-space into convex cells such that the interior of each cell does not intersect the interior of any simplex in $S$. In this paper it is shown that a $CSP(S)$ of size $O(n^{d-1})$ can be computed deterministically in time $O(n^{d-1})$. These bounds are worst case optimal for $d=3$. The results are proved using a variation of the efficient hierarchical cuttings of Chazelle. 000828 Efficient PRAM Simulation on a Distributed Memory Machine R. Karp, M. Luby, F. Meyer auf der Heide tr-93-040 1993 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-040.pdf We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the same cell, whereas the memory of a DMM is divided into modules, one for each processor, and concurrent accesses to the same module create a conflict. The delay of a simulation is the time needed to simulate a parallel memory access of the PRAM. Any general simulation of an m processor PRAM on a n processor DMM will necessarily have delay at least m/n. A randomized simulation is called time-processor optimal if the delay is O(m/n) with high probability. Using a novel simulation scheme based on hashing we obtain a time-processor optimal simulation with delay O(\loglog(n)\logstn). The best previous simulations use a simpler scheme based on hashing and have much larger delay. 000829 Optimal Parallelization of Las Vegas Algorithms Michael Luby, Wolfgang Ertel tr-93-041 1993 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-041.pdf Let $A$ be a Las Vegas algorithm, i.e., $A$ is a randomized algorithm that always produces the correct answer when it stops but whose running time is a random variable. In\lit{LSZ93} a method was developed for minimizing the expected time required to obtain an answer from~$A$ using sequential strategies which simulate $A$ as follows: run $A$ for a fixed amount of time $t_1$, then run $A$ independently for a fixed amount of time $t_2$, etc. The simulation stops if $A$ completes its execution during any of the runs.
In this paper, we consider parallel simulation strategies for this same problem, i.e., strategies where many sequential strategies are executed independently in parallel using a large number of processors. We present a close to optimal parallel strategy for the case when the distribution of $A$ is known. If the number of processors is below a certain threshold, we show that this parallel strategy achieves almost linear speedup over the optimal sequential strategy. For the more realistic case where the distribution of $A$ is not known, we describe a universal parallel strategy whose expected running time is only a logarithmic factor worse than that of an optimal parallel strategy. Finally, the application of the described parallel strategies to a randomized automated theorem prover confirms the theoretical results and shows that in most cases good speedup can be achieved up to hundreds of processors, even on networks of workstations. 000830 Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Decision Trees Dima Grigoriev, Marek Karpinski tr-93-042 1993 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-042.pdf We describe a new method for proving lower bounds for algebraic decision trees. We prove, for the first time, that the minimum depth for arbitrary decision trees for the problem of testing the membership to a polygon with N nodes is Omega(log N). Moreover, we prove that the corresponding lower bound for the randomized decision trees matches the above bound. Finally, we prove that for the algebraic exp-log decision trees (cf. [GSY 93]), the minimum depth is Omega(sqrt(log N)). We generalize the last result to the multidimensional case, showing that if an exp-log decision tree tests a membership to a semialgebraic set with a sum of Betti numbers M, then the depth of a tree is at least Omega(sqrt(log M)). 000831 Finite Branching Processes and AND/OR Tree Evaluation Richard Karp tr-93-043 1993 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-043.pdf This paper studies tail bounds on supercritical branching processes with finite distributions of offspring. Given a finite supercritical branching process Z_n\_0^{infinity}, we derive upper bounds, decaying exponentially fast as c increases, on the right-tail probability \Pr[Z_n > c E(Z_n)]. We obtain a similar upper bound on the left-tail probability \Pr[Z_n < \frac{E(Z_n)}c] under the assumption that each individual generates at least two offspring. As an application, we observe that the evaluation of an AND/OR tree by a canonical algorithm in certain probabilistic models can be viewed as a two-type supercritical finite branching process, and show that the execution time of this algorithm is likely to concentrate around its expectation. 000832 An application of a neural net for fuzzy abductive reasoning Matthias Kaiser tr-93-044 1993 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-044.pdf This is a description of a simple system that is able of performing abductive reasoning over fuzzy data using a back-propagation neural net for the hypothesis generation process.
I will first outline and exemplify the notion of abduction as a process of building hypotheses on the basis of a given set of data, evaluating them to find the best hypothesis and give explanation for the made selection. I extend this notion to account for abductive reasoning over fuzzy data. As an example I describe the classification of objects according to fuzzy sensory features into previously learned categories that were represented by a set of objects described by feature-value-pairs from which prototypes are detected which form the center of a category.
In the following a brief description of the back-propagation algorithm and a design of a demonstration system that is capable of carrying out abductive reasoning in a small example domain is given. The system is able to learn to classify kinds of fruit given certain feature-value-pairs and to detect the most prototypical feature-value-pair-clusters within a category. The trained neural net is used for the hypothesis generation process. It also provides very critical information for the evaluation and explanation of hypotheses. I then discuss the implementation of an evaluation and explanation component using the specific capabilities of the neural net. 000833 Sather Iters: Object-Oriented Iteration Abstraction Stephan Murer, Steve Omohundro, Clemens Szyperski tr-93-045 1993 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-045.pdf Sather iters are a powerful new way to encapsulate iteration. We argue that such iteration abstractions belong in a class' interface on an equal footing with its routines. Sather iters were derived from CLU iterators but are much more flexible and better suited for object-oriented programming. We motivate and describe the construct along with several simple examples. We compare it with iteration based on CLU iterators, cursors, riders, streams, series, generators, coroutines, blocks, closures, and lambda expressions. Finally, we describe how to implement them in terms of coroutines and then show how to transform this implementation into efficient code. 000834 A Performance Analysis of the CNS-1 on Large, Dense Backpropagation Networks Silvia M. Müller tr-93-046 1993 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-046.pdf We determine in this study the sustained performance of the CNS-1 during training and evaluation of large multilayered feedforward neural networks. Using a sophisticated coding, the 128-node machine would achieve up to 111 GCPS and 22 GCUPS. During recall the machine would archieve 87% of the peak multiply-accumulate performance. The training of large nets is less efficient than the recall but only by a factor of 1.5 to 2.
The benchmark is parallelized and the machine code is optimized before analyzing the performance. Starting from an optimal parallel algorithm, CNS specific optimizations still reduce the run time by a factor of 4 for recall and by a factor of 3 for training. Our analysis also yields some strategies for code optimization.
The CNS-1 is still in design, and therefore we have to model the run time behavior of the memory system and the interconnection network. This gives us the option of changing some parameters of the CNS-1 system in order to analyze their performance impact.
Keywords: CNS, performance analysis, run time model, backpropagation, parallelization. 000835 Source-to-Source Code Generation Based on Pattern Matching and Dynamic Programming Weimin Chen, Volker Turau tr-93-047 1993 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-047.pdf This paper introduces a new technique for source-to-source code generation based on pattern matching and dynamic programming. This technique can be applied to all source and target-languages which satisfy some requirements. The main differences to conventional approaches are the complexity of the target language, the handling of side effects caused by function calls and the introduction of temporaries. Code optimization is achieved by introducing a new cost- model. The technique allows an incremental development based on improvements of the target library. These require only a modification of the rewriting rules since those are separated from the pattern matching algorithm. Experience of an successful application of our technique is given. 000836 The Sublogarithmic Space World Maciej Liskiewicz, Ruediger Reischuk tr-93-048 1993 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-048.pdf (Pages: 42) This paper tries to fully characterize the properties and relationships of space classes defined by Turing machines that use less than logarithmic space -- may they be deterministic, nondeterministic or alternating (DTM, NTM or ATM). We provide several examples of specific languages and show that such machines are unable to accept these languages. The basic proof method is a nontrivial extension of the (1 superscript n) right arrow (1 superscript (n+n!)) technique to alternating TMs 000837 Precise Average Case Complexity Measures Ruediger Reischuk tr-93-049 1993 08 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-049.pdf (Pages: 36) A new definition is given for the average growth of a function f : (Sigma superscript *) right arrow (IN) with respect to a probability measure mu on (Sigma superscript *). This allows us to define meaningful average case distributional complexity classes for arbitrary time bounds (previously, one could not guarantee arbitrary good precision). It is shown that basically only the ranking of the inputs by decreasing probabilities are of importance.
To compare the average and worst case complexity of problems we study average case complexity classes defined by a time bound and a bound on the complexity of possible distributions. Here, the complexity is measured by the time to compute the rank functions of the distributions. We obtain tight and optimal separation results between these average case classes. Also the worst case classes can be embedded into this hierarchy. They are shown to be identical to average case classes with respect to distributions of exponential complexity. 000838 Interior point methods in semidefinite progrmming with applications to combinatorial optimization Farid Alizadeh tr-93-050 1993 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-050.pdf We study the semidefinite programming problem (SDP), i.e the optimization problem of a linear function of a symmetric matrix subject to linear equality constraints and the additional condition that the matrix be positive semidefinite. First we review the classical cone duality as specialized to SDP. Next we present aninterior point algorithm which converges to the optimal solution in polynomial time. The approach is a direct extension of Ye's projective method for linear programming. We also argue that most known interior point methods for linear programs can be transformed in a mechanical way to algorithms for SDP with proofs of convergence and polynomial time complexity also carrying over in a similar fashion. Finally we study the significance of these results in a variety of combinatorial optimization problems including the general 0-1 integer programs, the maximum clique and maximum stable set problems in perfect graphs, the maximum $k$-partite subgraph problem in graphs, and various graph partitioning and cut problems. As a result, we present barrier oracles for certain combinatorial optimization problems (in particular, clique and stable set problem for perfect graphs) whose linear programming formulation requires exponentially many inequalities. Existence of such barrier oracles refutes the commonly believed notion that in order to solve a combinatorial optimization problem with interior point methods, one needs its linear programming formulation explicitly. 000839 Dynamic maintenance of approximate solutions of Min-Weighted Node Cover and Min-Weighted Set Cover problems Giorgio Gambosi, Marco Protasi, Maurizio Talamo tr-93-051 1993 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-051.pdf In this paper, we introduce new algorithms for the dynamic maintenance of approximated solutions of Min-Weighted Node Cover and Min-Weighted Set Cover. For what concerns Min-Weighted Node Cover, for any sequence of edge insertions and deletions, the algorithms maintain a solution whose approximation ratio (that is, the ratio between the approximate and the optimum value) is equal to the best asymptotic one for the static case. The algorithms require O(1) time for edge insertion, while an O(1) amortized time is required for edge deletion.
For what regards Min-Weighted Set Cover, we present dynamic algorithms whose approximation ratio matches one of the two different and incomparable best approx- imate bounds for the static case. The time complexity for element insertion and its amortized complexity for element deletion are proportional to the maximum redundancy of an element in the approximate solution. 000840 On a Criterion for Minimum Uncertainty Sensing Vincenzo Caglioti tr-93-052 1993 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-052.pdf This is an invited article for the Structural Complexity Column, edited by Juris Hartmanis, which will appear in the Bulletin EATCS in October 1993. The scope of the article is indicated in the following list of Sections: 1. Overview of Information-Based Complexity 2. Breaking Intractability 3. Verification 4. Combinatorial Complexity 5. Similarities and Differences with Discrete Complexity 6. Brief History 7. Appendix 8. References 000841 On a Criterion for Minimum Uncertainty Sensing Vincenzo Caglioti tr-93-053 1993 09 __ 000006 A criterion is presented for the automatic selection of a sensor detection aimed at observing the state of a system, which is described both by discrete variable and by continuous ones. The criterion is based on the expected value of the entropy variation relative to the transition associated to the sensor observation. This criterion is then applied to object recognition and localization tasks, in which the observed system is described by object class (i.e., a discrete variable) and by the object position (i.e. a vector of continuous parameters). The proposed criterion allows to account for the information obtained in the case the observed object is missed by the measurement. Finally, a simple example is discussed concerning an observed system constituted by an object. The state of the observed system is described in terms of the object identity and the object position and orientation parameters. The sensors used to observe the system are an orientable range finder and a mobile camera. 000842 An Investigation into Fault Recovery in Guaranteed Performance Service Connections Colin J. Parris, Anindo Banerjea tr-93-054 1993 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-054.pdf As high speed networks are starting to provide guaranteed performance services, it is imperative that fault recovery techniques be revised to support this new service. In this paper we investigate one aspect of fault recovery in this context, the rerouting of guaranteed performance connections affected by link faults in the network. Recovery is achieved by rerouting the affected connection so as to avoid the failed link while ensuring that the traffic and performance guarantees made along the previous route are satisfied along the new route. The goal of the rerouting schemes is to reroute as much of the affected traffic as quickly and efficiently as possible. We investigate rerouting along the lines of two orthogonal components: the locus of reroute, which determines the node that does route selection and the new route selected; and the timing component, which determines when the individual reroute attempts are initiated. Within each of these two components we examine approaches that span the spectrum of that component. We compare all possible combinations of these approaches under a cross-section of network workloads, using in our comparisons a novel metric, the Queuing Delay Load Index, that captures both the bandwidth and delay resources required by a connection. Extensive simulation experiments were conducted on the various combinations and their results and analysis are presented in the paper. 000843 Testable Algorithms for Self-Avoiding Walks Dana Randall, Alistair Sinclair tr-93-055 1993 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-055.pdf We present a polynomial time Monte Carlo algorithm for almost uniformly generating and approximately counting self-avoiding walks in rectangular lattices. These are classical problems that arise, for example, in the study of long polymer chains. While there are a number of Monte Carlo algorithms used to solve these problems in practice, these are heuristic and their correctness relies on unproven conjectures. In contrast, our algorithm relies on a single, widely-believed conjecture that is simpler than preceding assumptions, and, more importantly, is one which the algorithm itself can test. Thus our algorithm is reliable, in the sense that it either outputs answers that are guaranteed, with high probability, to be correct, or finds a counterexample to the conjecture. 000844 Dynamic Join and Leave for Real-Time Multicast Wolfgang Effelsberg, Eberhard Müller-Menrad tr-93-056 1993 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-056.pdf Many new applications in networks require support for multicast communication. In addition, continuous data streams such as audio and video require real-time performance guarantees as a quality of service. We introduce a model for real-time mulitcast channels and present a set of scalable algorithms for the dynamic joining and leaving of destination nodes in this environment. In particular we present an algorithm for finding a good attachment point to the multicast tree. We also describe detailed admission tests that preserve the guarantees given to existing channels. Our algorithm for a leaving node specifies in particular the resources to be released in the network. We also discuss tree reorganization issues.
Keywords: multicast, dynamic, membership, multicast tree
000845 Second Order Backpropagation - Efficient Computation of the Hessian Matrix for Neural Networks Raul Rojas tr-93-057 1993 09 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-057.pdf Traditional learning methods for neural networks use some kind of gradient descent in order to determine the network's weights for a given task. Some second order learning algorithms deal with a quadratic approximation of the error function determined from the calculation of the Hessian matrix, and achieve improved convergence rates in many cases. We introduce in this paper second order backpropagation, a method to calculate efficiently the Hessian of a linear network of one-dimensional functions. This technique can be used to get explicit symbolic expressions or numerical approximations of the Hessian and could be used in parallel computers to improve second order learning algorithms for neural networks. It can be of interest also for computer algebra systems.
[A newer version of this method is found in the book: Raul Rojas, Neural Networks, 1996, Springer-Verlag, available in English and German.]
000846 Towards a cognitively based approach of a a description of spatial deixis Matthias Kaiser tr-93-058 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-058.pdf In this presentation an approach towards a description of spatial deixis based on the perceptual and cognitive abilities of humans is outlined. After a basic introduction into space perception and representation the findings of this part are taken to form the basis for a characterization of the phenomenon of deixis as well as the conceptual components of deictic expressions in a natural language. For the analysis of deictic expressions a cross-linguistic view is applied to find on the one hand universal components of those expressions but also a number of potentially influencing factors. The goal is to find features that may be components of deictic expressions and thus must be considered in a general model of spatial deixis which can serve to classify and describe the meaning of spatial deictic expressions in any natural language.
000847 Constructive Deterministic PRAM Simulation on a Mesh-Connected Computer Andrea Pietracaprina, Geppino Pucci, Jop F. Sibeyn tr-93-059 1993 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-059.pdf The PRAM model of computation consists of a collection of sequential RAM machines accessing a shared memory in lock-step fashion. The PRAM is a very high-level abstraction of a parallel computer, and its direct realization in hardware is beyond reach of the current (or even foreseeable) technology. In this paper we present a deterministic simulation scheme to emulate PRAM computation on a mesh-connected computer, a feasible machine where each processor has its own memory module and is connected to at most four other processors via point-to-point links. In order to achieve a good worst-case performance, any deterministic simulation scheme has to replicate each variable in a number of copies. Such copies are stored in the local memory modules according to a Memory Organization Scheme (MOS), which is known to all the processors. A variable is then accessed by routing packets to its copies. All deterministic schemes in the literature make use of a MOS whose existence is proved via the probabilistic method, but that cannot be efficiently constructed. We introduce a new constructive MOS, and show how to employ it to simulate an $n$-processor PRAM on an $n$-node mesh-connected computer. Our simulation achieves almost optimal slowdown for small memories. This is the first constructive deterministic PRAM simulation on a bounded-degree network
000848 Improved Band Matrix Computations Victor Pan tr-93-060 1993 09 __ 000006 We solve a band linear system of equations and compute the determinant of a band matrix in NC over the complex field and its subfields and in RNC over any field. Our algorithms support the optimum bound on the potential work (the product of time and processor bounds); moreover, the algorithms are in NC superscript 1 or RNC superscript 1 if the bandwidth is a constant. These results substantially improve the previous records of [E].
000849 Optimum Parallel Computations with Band Matrices Victor Pan tr-93-061 1993 09 __ 000006 We devise optimum parallel algorithms for solving a band linear system of equations and for computing the determinant of a band matrix, substantially improving the previous record computational complexity estimates of [E]. All our algorithms are in NC or RNC and processor efficient; almost all of them reach the optimum bound on the potential work (the product of time and processor bounds). Moreover, these algorithms are in NC superscript 1 or RNC superscript 1 if the bandwidth is a constant.
000850 A Formalization of Viewpoints Giuseppe Attardi, Maria Simi tr-93-062 1993 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-062.pdf We present a formalisation for the notion of "viewpoint", a construct meant for expressing several varieties of relativised truth. The formalisation consists in a logic which extends first order predicate calculus through an axiomatization of provability and with the addition of proper reflection rules. The extension is not conservative, but consistency is granted. Viewpoints are defined as set of reified meta-level sentences. A proof theory for viewponts is developed which enables to carry out proofs of sentences involving several viewpoints. A semantic account of viewpoints is provided, dealing with issues of self referential theories and paradoxes, and exploiting the notion of "contextual entailment". Notions such as beliefs, knowledge, truth and situations can be uniformly modeled as provability in specialised viewpoints, obtained by imposing suitable constraints on viewpoints.
Keywords: meta-level, logics for truth, belief and knowledge, situations, contexts. 000851 A Parallel Object-Oriented System for Realizing Reusable and Efficient Data Abstractions Chu-Cheow Lim tr-93-063 1993 10 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-063.pdf (319 pages) We examine the use of an object-oriented language to make programming multiprocessors easier for the general programmer. We choose an object-oriented paradigm because we believe that its support for encapsulation and software reuse allows users who are writing general application programs to reuse class libraries designed by expert library writers.
We describe the design, implementation and use of a parallel object-oriented language: parallel Sather (pSather). PSather has a shared address space independent of the underlying multiprocessor architecture, because we believe that the cooperative nature of parallel programs is most easily captured by a shared-memory-like model. To account for distributed-memory machines, pSather uses an abstract model in which processors are grouped in clusters. Associated with a cluster is a part of the address space with fast access; access to other parts of the address space is $\leq 2$ orders of magnitude slower. PSather integrates both control and data-parallel constructs to support a variety of algorithmic styles. We have an implementation of pSather on the CM-5. The prototype shows that even on distributed-memory machines without hardware/operating system support for a shared address space, it is still practical and reasonably efficient for the shared address abstraction to be implemented in the compiler/runtime. The experience also helps us understand the features of low-level libraries that are necessary for an efficient realization of a high-level language. For example, even though low message latency is crucial, the message-passing paradigm (active vs. passive, polling vs. interrupt-driven) is also important in deciding how easy and efficient the language implementation will be. We also study certain straight-forward compiler optimizations. Several abstractions and applications have been written for the CM-5 using the shared-address cluster model, and we have achieved reasonable speedups. In some cases, we can further demonstrate good absolute performance for pSather programs (by getting their speedups relative to a 1-processor C program). Some of the abstractions are reused in several applications, to show how the object-oriented constructs facilitate code reuse. The work described here supports our optimism that pSather is a practical and efficient parallel object-oriented language. There are, however, still many issues that need to be explored in order to provide parallel programming environments as powerful as the ones we are accustomed to on sequential environments. In the conclusion, we summarize some of the possible future research directions. 000852 Engineering a Programming Language: The Type and Class System of Sather Clemens Szypersky, Stephen Omohundro, Stephan Murer tr-93-064 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-064.pdf Sather 1.0 is a programming language whose design has resulted from the interplay of many criteria. It attempts to support a powerful object-oriented paradigm without sacrificing either the computational performance of traditional procedural languages or support for safety and correctness checking. Much of the engineering effort went into the design of the class and type system. This paper describes some of these design decisions and relates them to approaches taken in other languages. We particularly focus on issues surrounding inheritance and subtyping and the decision to explicitly separate them in Sather. 000853 An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities Andreas Stolcke tr-93-065 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-065.pdf We describe an extension of Earley's parser for stochastic context-free grammars that computes the following quantities given a stochastic context-free grammar and an input string: a) probabilities of successive prefixes being generated by the grammar; b) probabilities of substrings being generated by the nonterminals, including the entire string being generated by the grammar; c) most likely (Viterbi) parse of the string; d) posterior expected number of applications of each grammar production, as required for reestimating rule probabilities. (a) and (b) are computed incrementally in a single left-to-right pass over the input. Our algorithm compares favorably to standard bottom-up parsing methods for SCFGs in that it works efficiently on sparse grammars by making use of Earley's top-down control structure. It can process any context-free rule format without conversion to some normal form, and combines computations for (a) through (d) in a single algorithm. Finally, the algorithm has simple extensions for processing partially bracketed inputs, and for finding partial parses and their likelihoods on ungrammatical inputs. 000854 Recovering Guaranteed Performance Service Connections from Single and Multiple Faults Anindo Banerjea, Colin Parris, Domenico Ferrari tr-93-066 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-066.pdf Fault recovery techniques must be reexamined in the light of the new guaranteed performance services that networks will support. We investigate the rerouting of guaranteed performance service connections on the occurrence of link faults, focussing on the aspects of route selection and establishment in the network. In a previous investigation, we explored some components of rerouting in the presence of single link faults in the network. In this paper we study the behavior of our techniques in the presence of multiple link faults in the network, and also examine the technique of retries to improve the success of rerouting. Our schemes are simulated on a cross-section of network workloads, and compared using the criteria of the fraction of the affected traffic that could be rerouted, the time to reroute and the amount of resources consumed in the network. A novel metric, the Queueing Delay Load Index, which captures both the bandwidth and delay demands made on the network by a connection, is used to present and analyze the results. 000855 A Software Reuse System for C Codes Le Van Huu tr-93-067 1993 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-067.pdf This paper presents PRASSY, a hypertext system for the storage and retrieval of procedure source codes, on the basis of the semantics of their comments. The objective of the system is to provide the program developer with the possibility of retrieving and reusing the source code of C subroutines that have been previously built by his colleagues or that are already present in the system. The approach adopted by PRASSY is the analysis of the source code comments and of the specification documents written in natural language, in order to extract indexing information. Such information is organized in a hypertext structure and the browsing mechanism is used by the user to select reusable software components. The system provides a way for measuring the semantic similarity between the user requirements and the candidate node to be selected. The paper describes the system's architecture and functionalities. Some examples of the user interface and the browsing mechanisms are reported. Finally, it describes the algorithm proposed by Aragon-Ramirez and Paice and adopted by PRASSY for defining the semantic similarity among phrases expressed in natural language.
Keywords: hypertext, software reuse, semantic phrases similarity 000856 Lexical Modeling in a Speaker Independent Speech Understanding System Charles Clayton Wooters tr-93-068 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-068.pdf This thesis presents an algorithm for the construction of models that attempt to capture the variation that occurs in the pronunciations of words in spontaneous (i.e., non-read) speech. A technique for developing alternate pronunciations of words and then estimating the probabilities of the alternate pronunciations is presented. Additionally, we describe the development and implementation of a spoken-language understanding system called the Berkeley Restaurant Project (BeRP). Multiple pronunciation word models constructed using the algorithm proposed in this thesis are evaluated within the context of the BeRP system. The results of this evaluation show that the explicit modeling of variation in the pronunciation of words improves the performance of both the speech recognition and the speech understanding components of the BeRP system. 000857 On the Definition of Speedup Wolfgang Ertel tr-93-069 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-069.pdf We propose an alternative definition for the speedup of parallel algorithms. Let A be a sequential algorithm and B a parallel algorithm for solving the same problem. If A and/or B are randomized or if we are interested in their performance on a probability distribution of problem instances, the running times are described by random variables T_A and T_B. The speedup is usually defined as E[T_A]/E[T_B] where E is the arithmetic mean. This notion of speedup delivers just a number, i.e. much information about the distribution is lost. For example, there is no variance of the speedup. To define a measure for possible fluctuations of the speedup, a new notion of speedup is required. The basic idea is to define speedup as M(T_A/ T_B) where the functional form of M has to be determined. Also, we argue that in many cases M(T_A/T_B) is more informative than E[T_A]/E[T_B] for a typical user of A and B. We present a set of intuitive axioms that any speedup function M(T_A/T_B) must fulfill and prove that the geometric mean is the only solution. As a result, we now have a uniquely defined speedup function that will allow the user of an improved system to talk about the average performance improvement as well as about its possible variations. 000858 An Alphabet-Independent Optimal Parallel Search for Three Dimensional Patterns Marek Karpinski, Wojciech Rytter tr-93-070 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-070.pdf We give an alphabet-independent optimal parallel algorithm for the searching phase of three dimensional pattern- matching. All occurrences of a three dimensional pattern P of shape m x m x m in a text T of shape n x n x n are to be found. Our algorithm works in log m time with O(N log m) processors of a CREW PRAM, where N = n^3. The searching phase in three dimensions explores classification of two- dimensional periodicities of the cubic pattern. Some new projection techniques are developed to deal with three dimensions. The periodicities of the pattern with respect to its faces are investigated. The nonperiodicities imply some sparseness properties, while periodicities imply other special useful properties (i.e. monotonicity) of the set of occurrences. Both types of properties are useful in deriving an efficient algorithm.
The search phase is preceeded by the preprocessing phase (computation of the witness table). Our main results concern the searching phase, however we present shortly a new approach to the second phase also. Usefullness of the dictionaries of basic factors (DBF's), see [CR 91], in the computation of the three dimensional witness table is presented. The DBF approach gains simplicity at the expense of a small increase in time. It gives a (nonoptimal) O(log m) time algorithm using m processors of a CRCW PRAM. The alphabet-independent optimal preprocessing is very complex even in the case of two dimensions, see [GP 92]. For large alphabets the DBF's give assymptotically the same complexity as the (alphabet-dependent) suffix trees approach (but avoids suffix trees and is simpler).
However, the basic advantage of the DBF approach is its simplicity of dealing with three (or more) dimensions.
The algorithm can be easily adjusted to the case of unequally sided patterns. 000859 Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov tr-93-071 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-071.pdf We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound Omega(log N) for testing membership to a convex polyhedron having N facets of all dimensions. This bound apparently does not follow from the methods developed by M. Ben-Or, A. Bjoerner, L. Lovasz, A. Yao ([B 83], [BLY 92]) because the topological invariants used in these methods become trivial for the convex polyhedra. 000860 Software Protection and Simulation on Oblivious RAMs Oded Goldreich, Rafail Ostrovsky tr-93-072 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-072.pdf Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the theoretical treatment it deserves. In this paper we provide theoretical treatment of software protection. We reduce the problem of software protection to the problem of efficient simulation on {\em oblivious\/} RAM.
A machine is {\em oblivious\/} if the sequence in which it accesses memory locations is equivalent for any two inputs with the same running time. For example, an oblivious Turing Machine is one for which the movement of the heads on the tapes is identical for each computation. (Thus, it is independent of the actual input.) {\em What is the slowdown in the running time of any machine, if it is required to be oblivious?\/} In 1979 Pippenger and Fischer showed how a two-tape {\em oblivious\/} Turing Machine can simulate, on-line, a one-tape Turing Machine, with a logarithmic slowdown in the running time. We show an analogue result for the random-access machine (RAM) model of computation. In particular, we show how to do an on-line simulation of an arbitrary RAM input by a probabilistic {\em oblivious\/} RAM with a poly-logarithmic slowdown in the running time. On the other hand, we show that a logarithmic slowdown is a lower bound. 000861 One-Way Functions are Essential for Non-Trivial Zero-Knowledge Rafail Ostrovsky, Avi Wigderson tr-93-073 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-073.pdf It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in $\PSPACE$. We prove that unless very {\em weak} one-way functions exist, Zero-Knowledge proofs can be given only for languages in $\BPP$. For average-case definitions of $\BPP$ we prove an analogous result under the assumption that {\em uniform} one-way functions do not exist.
Thus, very loosely speaking, zero--knowledge is either {\em useless} (exists only for ``easy'' languages), or {\em universal} (exists for every provable language). 000862 How and When to Be Unique Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir tr-93-074 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-074.pdf One of the fundamental problems in distributed computing is how identical processors with identical local memory can choose unique IDs provided they can flip a coin. The variant considered in this paper is the asynchronous shared memory model (atomic registers), and the basic correctness requirement is that upon termination the processes must always have unique IDs.
We study this problem from several viewpoints. On the positive side, we present the first protocol that solves the problem and terminates with probability 1. The protocol terminates in (optimal) $O(\log n)$ expected time, using $O(n)$ shared memory space, where $n$ is the number of participating processes. On the negative side, we show that no protocol can terminate with probability 1 if $n$ is unknown, and that no finite-state protocol can terminate with probability 1 if the schedule is non-oblivious (i.e., may depend on the history of the shared variable).
We also discuss the dynamic setting (where processes may join and leave the system dynamically), and give a deterministic protocol for the read-modify-write model that needs only 3 shared bits. 000863 Matching nuts and bolts Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky tr-93-075 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-075.pdf We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of bolts and nuts and wants to find the corresponding pairs of bolts and nuts. The procedure uses our (and the carpenter's) ability to construct efficiently highly expanding graphs. The problem considered is given a collection of $n$ bolts of distinct widths and $n$ nuts such that there is a 1-1 correspondence between the nuts and bolts. The goal is to find for each bolt its corresponding nut by comparing nuts to bolts but not nuts to nuts or bolts to bolts. Our objective is to minimize the number of operations of this kind (as well as the total running time). The problem has a randomized algorithm similar to Quicksort. Our main result is an $n (\log n)^{O(1)}$-time {\em deterministic} algorithm, based on expander graphs, for matching the bolts and the nuts. 000864 Any Non-Private Boolean Function Is Complete For Private Multi-Party Computations Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky tr-93-076 1993 11 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-076.pdf Let $g$ be an $n$-argument boolean function. Suppose we are given a {\em black-box\/} for $g$, to which $n$ honest-but-curious players can secretly give inputs and it broadcasts the result of operating $g$ on these inputs to all the players. We say that $g$ is {\em complete \/} (for multi-party private computations) if for {\em every\/} function $f$, the $n$ players can compute the function $f$ $n$-privately, given the black-box for $g$. In this paper, we characterize the boolean functions which are complete: we show that a boolean function $g$ is complete if and only if $g$ itself cannot be computed $n$-privately (when there is no black-box available). Namely, for boolean functions, the notions of {\bf completeness\/} and {\bf $n$-privacy} are {\em complementary\/}. On the other hand, for non-boolean functions, we show that this two notions are {\em not\/} complementary. Our result can be viewed as a generalization (for multi-party protocols and for $(n\geq 2)$-argument functions) of the two-party case, where it was known that two-argument functions which contain ``embedded-OR'' are complete. 000865 A Cognitive Model of Sentence Interpretation: the Construction Grammar approach Daniel Jurafsky tr-93-077 1993 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-077.pdf This paper describes a new, psychologically-plausible model of human sentence interpretation, based on a new model of linguistic structure, Construction Grammar. This on-line, parallel, probabilistic interpreter accounts for a wide variety of psycholinguistic results on lexical access, idiom processing, parsing preferences, and studies of gap-filling and other valence ambiguities, including various frequency effects. We show that many of these results derive from the fundamental assumptions of Construction Grammar that lexical idioms, idioms, and syntactic structures are uniformly represented as grammatical constructions, and argue for the use of probabilistically-enriched grammars and interpreters as models of human knowledge of and processing of language. 000866 An Evaluation of Burst-level Bandwidth Reservation Methods in WAN Environments Makiko Yoshida, Chinatsu Ikeda, Hiroshi Suzuki tr-93-078 1994 02 __ 000006 This paper shows the evaluation results of fast bandwidth reservation (FRP) methods applied to bursty traffics, e.g. a large file transfer, in ATM networks with long propagation delay. These traffics require a large bandwidth for a short time, i.e., bursty characteristics and a strict cell loss quality. For these traffics, an FRP instead of a call level bandwidth resservation is effective to utilize network resources under guaranteed QoS. Comparison among FRP methods with peak rate controls in terms of a transmission completion time is carried out under a short and long propagation delay. We compare two types of FRP and FRPs with three adaptive peak rate controls.
Evaluation results show that confirmed type FRP is preferable to uncomfirmed type FRP. In addition, we see from the results that FRP is preferable to unconfirmed type FRP. In addition, we see from the results that FRP with peak rate control using network availability information provids the shortest transmission completion time under light load conditions. However, the results also show that FRP with simple peak rate control using ACK/NACK provides fair transmission completion time under heavy load and long propagation delay conditions. 000867 On a Sublinear Time Parallel Construction of Optimal Binary Search Trees Marek Karpinski, Wojciech Rytter tr-93-079 1993 12 __ 000006 We design an efficient sublinear time parallel construction of optimal binary search trees. The efficiency of the parallel algorithm corresponds to its total work (the product time X processors). Our algorithm works in O(n_1-e) log(n)) time with the total work O(n_2+2e), for an aritrarily small constant 0< e less than or equal to one half. This is optimal within factor n_2e with respect to the best known sequential algorithm given by Knuth, which needs only O(n_2) time due to a monotonicity property of optimal binary search trees, see {6}). It is unknown how to explore this property in an efficient NC construction of binary search trees. Here we show that it can be effectively used in sublinear time parallel computation. Our improvement also relies on the use (in independently processed small subcomputations) of the parallelism present in the Knuth's algorithm. The best known sublinear time algorithms for the construction of binary search trees (as an instance of a more general problem) have O(n_3) work for time larger than n_3/4, see {3} and {7}. For time square root of (n) these algorithms need n_4 work, while our algorithm needs for this time only n_3 work, thus improving the known algorithms by a linear factor. Also if time is O(n_1-e) and e is very small our improvement is close to O(n). Such improvement is similar to the one implied by the monotonicity property in sequential computations (from n_3 sequential time for a more general dynamic programming problem to n_2 time for the special case of optimal binary search trees). 000868 Dynamic Programming in a Generalized Decision Model Ulrich Huckenbeck tr-93-080 1993 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-080.pdf (Pages: 40) We present two dynamic programming strategies for a general class of decision processes. Each of these algorithms includes among others the following graph theoretic optimization algorithms as special cases:
In our general decision model, we define several structural properties of cost measures in order to formulate sufficient conditions for the correctness of our algorithms.
Our first algorithm works as fast as the original Ford-Bellman Strategy and the Greedy Method, respectively. Our second algorithm solves a larger class of optimization problems than our first search strategy. 000869 On Valve Adjustments that Interrupt all s-t-Paths in a Digraph Ulrich Huckenbeck tr-93-081 1993 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-081.pdf (Pages: 15) When searching a path in a digraph, usually the following situation is given: Every node v may be entered by an arbitrary incoming arc (u,v), and v may be left by an arbitrary outgoing arc (v,w).
In this paper, however, we consider graphs with valve nodes, which cannot arbitrarily be entered and left. More precisely, a movable valve is installed in each valve node v. entering v via (u,v) and leaving it via (v,w) is only possible if the current position of the valve generates a connection between these two arcs; if, however, the current valve adjustment interrupts this connection then every path using the arcs (u,v) and (v,w) is interrupted, too.
We investigate the complexity of the following problem:
Given a digraph with valve nodes. Let s and t be two nodes of this graph.
Does there exist a valve adjustment that interrupts all paths from s to t?
We show that this problem can be solved in deterministic polynomial time if all valve nodes belong to a particular class of valves; otherwise the problem is NP-complete. 000870 All-to-all Broadcast on the CNS-1 Silvia M. Müller tr-93-082 1993 12 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-082.pdf This study deals with the all-to-all broadcast on the CNS-1. We determine a lower bound for the run time and present an algorithm meeting this bound. Since this study points out a bottleneck in the network interface, we also analyze the performance of alternative interface designs. Our analyses are based on a run time model of the network.
Keywords: CNS, all-to-all broadcast, transfer, performance analysis, parallelization. 000871 Surface Learning with Applications to Lip-Reading Christoph Bregler, Stephen Omohundro tr-94-001 1994 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-001.pdf Most connectionist research has focused on learning mappings from one space to another (eg. classification and regression). This paper introduces the more general task of learning constraint surfaces. It describes a simple but powerful architecture for learning and manipulating nonlinear surfaces from data. We demonstrate the technique on low dimensional synthetic surfaces and compare it to nearest neighbor approaches. We then show its utility in learning the space of lip images in a system for improving speech recognition by lip reading. This learned surface is used to improve the visual tracking performance during recognition. 000872 "Eigenlips" for Robust Speech Recognition Christoph Bregler, Yochai Konig tr-94-002 1994 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-002.pdf In this study we improve the performance of a hybrid connectionist speech recognition system by incorporating visual information about the corresponding lip movements. Specifically, we investigate the benefits of adding visual features in the presence of additive noise and crosstalk (cocktail party effect). Our study extends previous experiments by using a new visual front end, and an alternative architecture for combining the visual and acoustic information. Furthermore, we have extended our recognizer to a multi-speaker, connected letters recognizer. Our results show a significant improvement for the combined architecture (acoustic and visual information) over just the acoustic system in the presence of additive noise and crosstalk. 000873 Best-first Model Merging for Hidden Markov Model Induction Andreas Stolcke, Stephen M. Omohundro tr-94-003 1994 01 __ 000006 ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-003.pdf This report describes a new technique for inducing the structure of Hidden Markov Models from data which is based on the general `model merging' strategy (Omohundro 1992). The process begins with a maximum likelihood HMM that directly encodes the training data. Successively more general models are produced by merging HMM states. A Bayesian posterior probability criterion is used to determine which states to merge and when to stop generalizing. The procedure may be considered a heuristic search for the HMM structure with the highest posterior probability.
We discuss a variety of possible priors for HMMs, as well as a number of approximations which improve the computational efficiency of the algorithm. We studied three applications to evaluate the procedure. The first compares the merging algorithm with the standard Baum-Welch ap