We consider the problem of learning uncertainty regions for parameter estimation problems. The regions are ellipsoids that minimize the average volumes subject to a prescribed coverage probability. As expected, under the assumption of jointly Gaussian data, we prove that the optimal ellipsoid is centered around the conditional mean and shaped as the conditional covariance matrix. In more practical cases, we propose a differentiable optimization approach for approximately computing the optimal ellipsoids using a neural network with proper calibration. Compared to existing methods, our network requires less storage and less computations in inference time, leading to accurate yet smaller ellipsoids. We demonstrate these advantages on four real-world localization datasets.

Let A and B be two sets of n objects in R d , and let M be a (one-to-one) matching between A and B. Let min(M ), max(M ), and \\Sigma(M ) denote the length of the shortest edge, the length of the longest edge, and the sum of the lengths of the edges of M respectively. Bottleneck matching---a matching that minimizes max(M )---is suggested as a convenient way for measuring the resemblance between A and B. Several algorithms for computing, as well as approximating, this resemblance are proposed. The running time of all the algorithms involving planar objects is close to O(n 1:5 ). For instance, if the objects are points in the plane, the running time of the exact algorithm is O(n 1:5 log n). A semi-dynamic data-structure for answering containment problems for a set of congruent disks in the plane is developed. This data structure may be of independent interest. Next, the problem of finding a translation of B that maximizes the resemblance to A under the bottleneck matching criterion...

Yao proved that in the decision-tree model, the average complexity of the best deterministic algorithm is a lower bound on the complexity of randomized algorithms that solve the same problem. Here it is shown that a similar result does not always hold in the common model of distributed computation, the model in which all the processors run the same program (which may depend on the processors’ input). We therefore construct a new technique that together with Yao’s method enables us to show that in many cases, a similar relationship does hold in the distributed model. This relationship enables us to carry over known lower bounds on the complexity of deterministic computations to the realm of randomized computations, thus obtaining new results. The new technique can also be used for obtaining results concerning algorithms with bounded error.

Two tasks of communication in a multihop synchronous radio network are considered: Point-to-point communication and broadcast (sending a message to all nodes of a network). Efficient protocols for both problems are presented. Even though the protocols are probabilistic, it is shown how to acknowledge messages deterministically. Let n, D, and $\Delta $ be the number of nodes, the diameter and the maximum degree of our network, respectively. Both protocols require a setup phase in which a BFS tree is constructed. This phase takes $O((n + D\log n)\log \Delta )$ time. After the setup, k point-to-point transmissions require $O((k + D)\log \Delta )$ time on the average. Therefore the network allows a new transmission every $O(\log \Delta )$ time slots. Also, k broadcasts require an average of $O((k + D)\log \Delta \log n)$ time. Hence the average throughput of the network is a broadcast every $O(\log \Delta \log n)$ time slots. Both protocols pipeline the messages along the BFS tree. They are always successful on the graph spanned by the BFS tree. Their probabilistic behavior refers only to the running time. Using the above protocols the ranking problem is solved in $O(n\log n\log \Delta )$ time. The performance analysis of both protocols constitutes a new application of queueing theory.

We consider PAC-learning where the distribution is known to the student. The problem addressed here is characterizing when learnability with respect to distribution D1 implies learnability with respect to distribution D2.

This paper presents a new approach for resolving lexical ambiguities in one language using statistical data on lexical relations in another language. This approach exploits the differences between mappings of words to senses in different languages. We concentrate on the problem of target word selection in machine translation, for which the approach is directly applicable, and employ a statistical model for the selection mechanism. The model was evaluated using two sets of Hebrew and German examples and was found to be very useful for disambiguation.

The problem of distributed leader election in an asynchronous complete network, in the presence of faults that occurred prior to the execution of the election algorithm, is discussed. Failures of this type are encountered, for example, during a recovery from a crash in the network. For a network with n processors, k of which start the algorithm that uses at most O(n log k+n+kt) messages is presented and shown to be optimal. An optimal algorithm for the case where the identities of the neighbors are known is also presented. It is noted that the order of the message complexity of a t-resilient algorithm is not always higher than that of a nonresilient one. The t-resilient algorithm is a systematic modification of an existing algorithm for a fault-free network.>

The time-complexity of deterministic and randomized protocols for achieving broadcast (distributing a message from a source to all other nodes) in arbitrary multi-hop radio networks is investigated. In many such networks, communication takes place in synchronous time-slots. A processor receives a message at a certain time-slot if exactly one of its neighbors transmits at that time-slot. We assume no collision-detection mechanism; i.e., it is not always possible to distinguish the case where no neighbor transmits from the case where several neighbors transmit simultaneously. We present a randomized protocol that achieves broadcast in time which is optimal up to a logarithmic factor. In particular, with probability 1 --E, the protocol achieves broadcast within O((D + log n/s) ‘log n) time-slots, where n is the number of processors in the network and D its diameter. On the other hand, we prove a linear lower bound on the deterministic time-complexity of broadcast in this model. Namely, we show that any deterministic broadcast protocol requires 8(n) time-slots, even if the network has diameter 3, and n is known to all processors. These two results demonstrate an exponential gap in complexity between randomization and determinism. l i ‘ 1992 Academic press, IX

In relational databases a view definition is a query against the database, and a view materialization is the result of applying the view definition to the current database. A view materialization over a database may change as relations in the database undergo modifications. Several problems concerning views are considered, many of which are shown to be hard (NP-complete or even $\Sigma _2^p $-complete). Each problem was treated for general databases and for the much simpler tree databases (also called acyclic databases). View related problems over fixed schemas, in which only the data is allowed to vary, were examined. Methods to handle this case were presented; their complexity is polynomial: for tree schemas the degree of the polynomial is independent of the schema structure while for cyclic schemas the degree depends on the schema structure. These methods may present a practical possibility for dynamic view maintenance.

A WRAM is a parallel computer with shared memory into which many processors may write concurrently.To study the bit-complexity of arithmetic operations the computing ability of each of the processors is restricted to bit operations and execution-time address calculation are prohibited.The model differs from unbounded fan-in boolean circuits since computing the cumulative-and, in constant time is shown to require super-linear number of processors in this model, but only 2u gates of an unbounded fan-in boolean circuit.This lower bound implies that adding two n-bit integers in constant time also requires a super-linear number of processors.However, two such integers may be compared in constant time with a linear number of processors.Thus implying the equivalence of two models of resolving write conflicts: that in which concurrent write occurs only when the same number is being written and that in which the processor with the highest index succeeds writing.Finally, several algorithms for arithmetic operations are investigated with the aim of decreasing the number of processors.

Consider a network of asynchronous processors communicating by sending messages over unreliable lines. There are many advantages to restrict all communications to a spanning tree. To overcome the possible failure of k

In relational databases a view definition is a query against the database, and a view materialization is the result of applying the view definition to the current database A view materialization over a database may change as relations in the database undergo modificationsIn this paper a mechanism is proposed in which the view is materialized at all times The problem which this mechanism addresses is how to quickly update the view in response to database changes A structure is maintained which provides information useful in minimizing the amount of work caused by updatesMethods are presented for handling both general databases and the much simpler tree databases (also called acyclic database) In both cases adding or deleting a tuple can be performed in polynomial time For tree databases the degree of the polynomial is independent of the schema structure while for cyclic databases the degree depends on the schema structure The cost of a sequence of tuple additions (deletions) is also analyzed

Abstract The following problem is considered: Given an integer K, a graph G with two distinct vertices s and t, find the maximum number of disjoint paths of length K from s to t. The problem has several variants: the paths may be vertex‐disjoint or edge‐disjoint, the lengths of the paths may be equal to K or bounded by K, the graph may be undirected or directed. It is shown that except for small values of K all the problems are NP‐complete. Assuming P ≠ NP, for each problem, the largest value of K for which the problem is not NP‐complete is found. Whenever a polynomial algorithm exists, an efficient algorithm is described.

A grid graph is a node-induced finite subgraph of the infinite grid. It is rectangular if its set of nodes is the product of two intervals. Given a rectangular grid graph and two of its nodes, we give necessary and sufficient conditions for the graph to have a Hamilton path between these two nodes. In contrast, the Hamilton path (and circuit) problem for general grid graphs is shown to be NP-complete. This provides a new, relatively simple, proof of the result that the Euclidean traveling salesman problem is NP-complete.

Given a ring (cycle) of n processes it is required to design the processes so that they will be able to choose a leader (a uniquely designated process) by sending messages along the ring. If the processes are indistiguishable there is no deterministic algorithm, and therefore probabilistic algorithms are proposed. These algorithms need not terminate, but their expected complexity (time or number of bits of communication) is bounded by a function of n. If the processes work asynchronously then on the average O(n log2n) bits are transmitted. In the above cases the size n of the ring was assumed to be known. If n is not known it is suggested first to determine the value of n and then use the above algorithm. However, n may only be determined probabilistically and any algorithm may yield an incorrect value. In addition, it is shown that the size of the ring cannot be calculated by any probabilistic algorithm in which the processes can sense termination.

We show that any biconnected graph with n nodes and m edges can be covered by simple circuits whose total length is at most $\min (3m,m + 6n)$. Our proof suggests an efficient algorithm for finding such a cover.

Efficient algorithms for finding maximum flow in planar networks are presented. These algorithms take advantage of the planarity and are superior to the most efficient algorithms to date. If the source and the terminal are on the same face, an algorithm of Berge is improved and its time complexity is reduced to $O(n\log n)$. In the general case, for a given $D > 0$ a flow of value D is found if one exists; otherwise, it is indicated that no such flow exists. This algorithm requires $O(n^2 \log n)$ time. If the network is undirected a minimum cut may be found in $O(n^2 \log n)$ time. All algorithms require $O(n)$ space.

An algorithm is given to fmd maxtmum two-commodity flow m an undirected graph The algorithm is an improvement on Hu's two-commodity flow algorithm using the methods of Dmlc's single-commodity flow algorithm Karzanov's Improvement of Dmlc's algorithm can be applied to yield an O(I V ] 3) algorithm.It is shown that finding maximum two-commodity flow m a dwected graph is much more dffficuh, in fact it Is as difficult as hnear programming FmaUy, the problem of finding feasible flow m an undirected graph with lower and upper bounds on the edges is shown to be NP-complete even for a single commodity

article Some Matching Problems for Bipartite Graphs Share on Authors: Steven L. Tanimoto Department of Computer Science, University of Washington, Seattle, WA and University of Connecticut, Storrs, Connecticut Department of Computer Science, University of Washington, Seattle, WA and University of Connecticut, Storrs, ConnecticutView Profile , Alon Itai Computer Science Department, Techmon-Israel Institute of Technology, Haifa, Israel Computer Science Department, Techmon-Israel Institute of Technology, Haifa, IsraelView Profile , Michael Rodeh IBM Israel Scientific Center, Haifa, Israel IBM Israel Scientific Center, Haifa, IsraelView Profile Authors Info & Claims Journal of the ACMVolume 25Issue 4Oct. 1978 pp 517–525https://doi.org/10.1145/322092.322093Online:01 October 1978Publication History 51citation1,847DownloadsMetricsTotal Citations51Total Downloads1,847Last 12 Months80Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Finding minimum circuits in graphs and digraphs is discussed. An almost minimum circuit is a circuit which may have only one edge more than the minimum. To find an almost minimum circuit an $O(n^2 )$ algorithm is presented. A direct algorithm for finding a minimum circuit has an $O(ne)$ behavior. It is refined to yield an $O(n^2 )$ average time algorithm. An alternative method is to reduce the problem of finding a minimum circuit to that of finding a triangle in an auxiliary graph. Three methods for finding a triangle in a graph are given. The first has an $O(e^{3/2})$ worst case bound ($O(n)$ for planar graphs); the second takes $O(n^{5/3})$ time on the average; the third has an $O(n^{\log 7} )$ worst case behavior. For digraphs, results of Bloniarz, Fisher and Meyer are used to obtain an algorithm with $O(n^2 \log n)$ average behavior.

Finding minimum circuits in graphs and digraphs is discussed. An almost minimum circuit is a circuit which may have only one edge more than the minimum. An 0(n2) algorithm is presented to find an almost minimum circuit. The straightforward algorithm for finding a minimum circuit has an 0(ne) behavior. It is refined to yield an 0(n2) average time algorithm. An alternative method is to reduce the problem of finding a minimum circuit to that of finding a triangle in an auxiliary graph. Three methods for finding a triangle in a graph are presented. The first has an 0(e3/2) worst case bound ((n) for planar graphs); the second takes 0(n5/3) time on the average; the third has an 0(nlog7) worst case behavior. For digraphs, recent results of Bloniarz, Fisher and Meyer are used to obtain an algorithm with 0(n2logn) average behavior.

A very primitive version of Gotlieb’s timetable problem is shown to be NP-complete, and therefore all the common timetable problems are NP-complete. A polynomial time algorithm, in case all teachers are binary, is shown. The theorem that a meeting function always exists if all teachers and classes have no time constraints is proved. The multicommodity integral flow problem is shown to be NP-complete even if the number of commodities is two. This is true both in the directed and undirected cases.

An algorithm of Knuth for finding an optimal binary tree is extended in several directions to solve related problems. The first case considered is restricting the depth of the tree by some predetermined integer K, and a $Kn^2 $ algorithm is given. Next, for trees of degree $\sigma $, rather than binary trees, $Kn^2 \log \sigma $ and $n^2 \log \sigma $ algorithms are found for the restricted and nonrestricted cases, respectively. For alphabetic trees with letters of unequal cost, $\sigma ^2 n^2 $ algorithm is proposed. We conclude with a comparison of alphabetic and nonalphabetic trees and their respective complexities.

A very primitive version of Gotlieb's timetable problem is shown to be NP-complete, and therefore all the common timetable problems are NP-complete. A polynomial time algorithm, in case all teachers are binary, is shown. The theorem that a meeting function always exists if all teachers and classes have no time constraints is proved. The multi-commodity integral flow problem is shown to be NP-complete even if the number of commodities is two. This is true both in the directed and undirected cases. Finally, the two commodity real flow problem in undirected graphs is shown to be solvable in polynomial time. The time bound is O(|v|2|E|).