Malign Distributions for Average Case Circuit Complexity

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of alln-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at leastn−log n−log log nexpected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depthd, i.e. of worst-case complexityd, the expected time complexity will be at leastd−log n−log dwith respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained.     

On the Sample Complexity of Weak Learning

In this paper, we study the sample complexity of weak learning. That is, we ask how many data must be collected from an unknown distribution in order to extract a small but significant advantage in prediction. We show that it is important to distinguish between those learning algorithms that output deterministic hypotheses and those that output randomized hypotheses. We prove that in the weak learning model, any algorithm using deterministic hypotheses to weakly learn a class of Vapnik-Chervonenkis dimension d(n) requires Ω ([formula]) examples. In contrast, when randomized hypotheses are allowed, we show that Θ (1) examples suffice in some cases. We then show that there exists an efficient algorithm using deterministic hypotheses that weakly learns against any distribution on a set of size d(n) with only O(d(n)^2/3) examples. Thus for the class of symmetric Boolean functions over n variables, where the strong learning sample complexity is Θ (n), the sample complexity for weak learning using deterministic hypotheses is Ω ([formula]) and O(n^2/3), and the sample complexity for weak learning using randomized hypotheses is Θ (1). Next we prove the existence of classes for which the distribution-free sample size required to obtain a slight advantage in prediction over random guessing is essentially equal to that required to obtain arbitrary accuracy. Finally, for a class of small circuits, namely all parity functions of subsets of n Boolean variables, we prove a weak learning sample complexity of Θ(n). This bound holds even if the weak learning algorithm is allowed to replace random sampling with membership queries, and the target distribution is uniform on {0, 1}ⁿ.     

Asymptotic speed-ups in constructive solid geometry

We convert constructive solid geometry input to explicit representations of polygons, polyhedra, or more generallyd-dimensional polyhedra, in time and space 0(n^d), improving a previous0(n^d logn) time bound. We then show that any Boolean formula can be preprocessed in time0(n log n/log logn) and linear space so that the value of the formula can be maintained, as variables are changed one by one, in time O(log n/log logn) per change; this speeds up certain output-sensitive algorithms for constructive solid geometry.     

On the Complexity of Learning from Drifting Distributions

We consider two models of on-line learning of binary-valued functions from drifting distributions due to Bartlett. We show that if each example is drawn from a joint distribution which changes in total variation distance by at mostO(ε³/(d log(1/ε))) between trials, then an algorithm can achieve a probability of a mistake at mostεworse than the best function in a class of VC-dimensiond. We prove a corresponding necessary condition ofO(ε³/d). Finally, in the case that a fixed function is to be learned from noise-free examples, we show that if the distributions on the domain generating the examples change by at mostO(ε²/(d log(1/ε))), then any consistent algorithm learns to within accuracyε.     

Learning Boxes in High Dimension

We present exact learning algorithms that learn several classes of (discrete) boxes in {0,...,l-1} ⁿ . In particular we learn: (1) The class of unions of O(log n) boxes in time poly(n,log l) (solving an open problem of [16] and [12]; in [3] this class is shown to be learnable in time poly(n,l) ). (2) The class of unions of disjoint boxes in time poly(n,t,log l) , where t is the number of boxes. (Previously this was known only in the case where all boxes are disjoint in one of the dimensions; in [3] this class is shown to be learnable in time poly(n,t,l) .) In particular our algorithm learns the class of decision trees over n variables, that take values in {0,...,l-1} , with comparison nodes in time poly(n,t,log l) , where t is the number of leaves (this was an open problem in [9] which was shown in [4] to be learnable in time poly(n,t,l) ). (3) The class of unions of O(1) -degenerate boxes (that is, boxes that depend only on O(1) variables) in time poly(n,t, log l) (generalizing the learnability of O(1) -DNF and of boxes in O(1) dimensions). The algorithm for this class uses only equivalence queries and it can also be used to learn the class of unions of O(1) boxes (from equivalence queries only). Received January 19, 1997; revised June 4, 1997.     

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

We consider broadcasting in random d-regular graphs by using a simple modification of the random phone call model introduced by Karp et al. (Proceedings of the FOCS ’00, 2000). In the phone call model, in every time step, each node calls a randomly chosen neighbour to establish a communication channel to this node. The communication channels can then be used bi-directionally to transmit messages. We show that, if we allow every node to choose four distinct neighbours instead of one, then the average number of message transmissions per node required to broadcast a message efficiently decreases exponentially. Formally, we present an algorithm that has time complexity \(O(\log n)\) and uses \(O(n\log \log n)\) transmissions per message. In contrast, we show for the standard model that every distributed algorithm in a restricted address-oblivious model that broadcasts a message in time \(O(\log n)\) requires \(\Omega (n \log n{/} \log d)\) message transmissions. Our algorithm efficiently handles limited communication failures, only requires rough estimates of the number of nodes, and is robust against limited changes in the size of the network. Our results have applications in peer-to-peer networks and replicated databases.     

Simple Algorithms for the On-Line Multidimensional Dictionary and Related Problems

The on-line multidimensional dictionary problem consists of executing on-line any sequence of the following operations: INSERT(p) , DELETE(p) , and MEM-BER-SHIP(p) , where p is any (ordered) d -tuple (or string with d elements, or points in d -space where the dimensions have been ordered). We introduce a clean structure based on balanced binary search trees, which we call multidimensional balanced binary search trees, to represent the set of d -tuples. We present algorithms for each of the above operations that take O(d + log n) time, where n is the current number of d -tuples in the set, and each INSERT and DELETE operation requires no more than a constant number of rotations. Our structure requires dn words to represent the input, plus O(n) pointers and data indicating the first component where pairs of d -tuples differ. This information, which can be easily updated, enables us to test for MEMBERSHIP efficiently. Other operations that can be performed efficiently in our multidimensional balanced binary search trees are: print in lexicographic order (O(dn) time), find the (lexicographically) smallest or largest d -tuple (O( log n) time), and concatenation (O(d + log n) time). Finding the (lexicographically) k th smallest or largest d -tuple can also be implemented efficiently (O( log n) time), at the expense of adding an integer value at each node. Received June 13, 1997; revised September 3, 1998.     

An efficient top-down search algorithm for learning Boolean networks of gene expression

Boolean networks provide a simple and intuitive model for gene regulatory networks, but a critical defect is the time required to learn the networks. In recent years, efficient network search algorithms have been developed for a noise-free case and for a limited function class. In general, the conventional algorithm has the high time complexity of O(2^{2k mn k+1}) where m is the number of measurements, n is the number of nodes (genes), and k is the number of input parents. Here, we suggest a simple and new approach to Boolean networks, and provide a randomized network search algorithm with average time complexity O ^{(mn k+1}/ (log m)^(k−1)). We show the efficiency of our algorithm via computational experiments, and present optimal parameters. Additionally, we provide tests for yeast expression data. Editor: David Page     

Efficient Randomized Algorithms for the Repeated Median Line Estimator

The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Recently there has been a great deal of interest is robust estimators, because of their lack of sensitivity to outlying data points. The basic measure of the robustness of an estimator is its breakdown point, that is, the fraction (up to 50%) of outlying data points that can corrupt the estimator. One problem with robust estimators is that achieving high breakdown points (near 50%) has proved to be computationally demanding. In this paper we present the best known theoretical algorithm and a practical subquadratic algorithm for computing a 50% breakdown point line estimator, the Siegel or repeated median line estimator. We first present an O(n\log n) randomized expected-time algorithm, where n is the number of given points. This algorithm relies, however, on sophisticated data structures. We also present a very simple O(n log ² n) randomized algorithm for this problem, which uses no complex data structures. We provide empirical evidence that, for many realistic input distributions, the running time of this second algorithm is actually O(n log n) expected time. Received January 25, 1995; revised May 17, 1996. Communciated by L. J. Guibas.     

Bounded-Diameter Minimum-Cost Graph Problems

We present approximation algorithms for two closely related bicriteria problems. Given a graph with two weight functions on the edges, length and cost, we consider the Bounded-Diameter Minimum-Cost Steiner Tree (BDMST) problem and the Bounded-Diameter Minimum-Cardinality Edge Addition (BDMC) problem. We present a parameterized approximation algorithm for the BDMST problem with a bicriteria approximation ratio of (O(p log s/log p),O(log s/log p)) where the first factor gives the relaxation on the diameter bound, the second factor is the cost-approximation factor, s is the number of required nodes and p, 1 ≤ p < s, is an input parameter. The parameter p allows a trade-off between the two approximation factors. This is the first improvement of the cost-approximation factor since the scheme proposed by Marathe et al. [9]. For example, p can be set to s^α to obtain an (O(s^α),O(1)) approximation for a constant α. The algorithm is very simple and is suitable for distributed implementations. We also present the first algorithm for Bounded-Hops Minimum-Cost Steiner Tree for complete graphs with triangle inequality. This model includes graphs defined by points in a Euclidean space of any dimension. The algorithm guarantees an approximation ratio of (O(log_ds),O(log_ds)) where d is the bound on the diameter. This is an improvement over the general-case approximation when d is comparable with s. For example, the ratio is (O(1),O(1)) for any d = s^α where α is a constant between 0 and 1. For the case where the number of terminals is a constant and all edge lengths are unit, we have a polynomial-time algorithm. This can be extended to any length function providing a (1 + ε) in the approximation with ε showing up in the time complexity of the algorithm. For another special case, where the cost of any edge is either 1 or 0 and the length of each edge is positive, an algorithm with approximation ratio of (O(log(c log s)), O(log(c log s))) is presented, where c is the cost of the optimal solution. This approximation is a significant improvement over (O(log s),O(log s)) when the cost of the solution c is much smaller than the number of terminals s. This is useful when an existing multicast network is to be modified to accommodate new terminals with the addition of as few new edges as possible. We also propose an approximation algorithm for the Bounded-Diameter Minimum-Cardinality Edge Addition problem, which achieves an O(log n) approximation while relaxing the diameter bound by 2. While this ratio is the same as the one claimed in [3], this algorithm is simple and combinatorial rather than based on the Linear Program solution and can be readily modified for a distributed implementation.     

PAC Learning Intersections of Halfspaces with Membership Queries

A randomized learning algorithm {POLLY} is presented that efficiently learns intersections of s halfspaces in n dimensions, in time polynomial in both s and n . The learning protocol is the PAC (probably approximately correct) model of Valiant, augmented with membership queries. In particular, {POLLY} receives a set S of m = poly(n,s,1/ε,1/δ) randomly generated points from an arbitrary distribution over the unit hypercube, and is told exactly which points are contained in, and which points are not contained in, the convex polyhedron P defined by the halfspaces. {POLLY} may also obtain the same information about points of its own choosing. It is shown that after poly(n , s , 1/ε , 1/δ , log(1/d) ) time, the probability that {POLLY} fails to output a collection of s halfspaces with classification error at most ε , is at most δ . Here, d is the minimum distance between the boundary of the target and those examples in S that are not lying on the boundary. The parameter log(1/d) can be bounded by the number of bits needed to encode the coefficients of the bounding hyperplanes and the coordinates of the sampled examples S . Moreover, {POLLY} can be extended to learn unions of k disjoint polyhedra with each polyhedron having at most s facets, in time poly(n , k , s , 1/ε , 1/δ , log(1/d) , 1/γ ) where γ is the minimum distance between any two distinct polyhedra. Received February 5, 1997; revised July 1, 1997.     

On a Nearest-Neighbor Problem Under Minkowski and Power Metrics for Large Data Sets

The paper presents the sequential and the parallel algorithm for solving the nearest-neighbor problem in the plane, based on the generalized Voronoi diagram construction. The applications of the problem are found in the areas of networking, communications, distributed systems, computer modeling and information retrieval. The input for the problem is the set of circular sites S with varying radii, the query point p and the metric (Minkowski or power) according to which the site, neighboring the query point, is to be reported. The sequential algorithm takes O(n) time to build the data structure and O(log n) time for each query. The parallel algorithm requires O(log n log) preprocessing time and O(log) query time on EREW PRAM architecture with n/log n processors. The IDG/NNM software was developed for an experimental study of the problem. The experimental results demonstrate that the Voronoi diagram method outperforms the k – d tree method for all tested input configurations. The tests were conducted on large data sets, comprising thousands of generators.     

Parallel Algorithms for Maximum Matching in Complements of Interval Graphs and Related Problems

Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log ³ n) time using O(n/ log ² n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs. Received November 20, 1995; revised September 3, 1998.     

New fast parallel algorithm for the connected component problem and its VLSI implementation

We present an O(log n) compare-exchange time parallel algorithm to compute the connected components of a given graph. We also introduce a simple regular VLSI architecture on which the proposed algorithm can readily be implemented requiring n³ identical processing elements and O(n) communication time, where n is the number of vertices in the graph.     

On-Line and Off-Line Approximation Algorithms for Vector Covering Problems

This paper deals with vector covering problems in d -dimensional space. The input to a vector covering problem consists of a set X of d -dimensional vectors in [0,1] ^d . The goal is to partition X into a maximum number of parts, subject to the constraint that in every part the sum of all vectors is at least one in every coordinate. This problem is known to be NP-complete, and we are mainly interested in its on-line and off-line approximability. For the on-line version, we construct approximation algorithms with worst case guarantee arbitrarily close to 1/(2d) in d≥ 2 dimensions. This result contradicts a statement of Csirik and Frenk in [5] where it is claimed that, for d≥ 2 , no on-line algorithm can have a worst case ratio better than zero. Moreover, we prove that, for d≥ 2 , no on-line algorithm can have a worst case ratio better than 2/(2d+1) . For the off-line version, we derive polynomial time approximation algorithms with worst case guarantee Θ(1/ log d) . For d=2 , we present a very fast and very simple off-line approximation algorithm that has worst case ratio 1/2 . Moreover, we show that a method from the area of compact vector summation can be used to construct off-line approximation algorithms with worst case ratio 1/d for every d≥ 2 . Received November 1996; revised March 1997.     

Neural network controller with flexible structure based on feedback-error-learning approach

In practice, the back-propagation algorithm often runs very slowly, and the question naturally arises as to whether there are necessarily intrinsic computation and difficulties with training neural networks, or better training algorithms might exist. Two important issues will be investigated in this framework. One establishes a flexible structure, to construct very simple neural network for multi-input/output systems. The other issue is how to obtain the learning algorthm to achieve good performance in the training phase. In this paper, the feedforward neural network with flexible bipolar sigmoid functions (FBSFs) are investigated to learn the inverse model of the system. The FBSF has changeable shape by changing the values of its parameter according to the desired trajectory or the teaching signal. The proposed neural network is trained to learn the inverse dynamic model by using back-propagation learning algorithms. In these learning algorithms, not only the connection weights but also the sigmoid function parameters (SFPs) are adjustable. The feedback-error-learning is used as a learning method for the feedforward controller. In this case, the output of a feedback controller is fed to the neural network model. The suggested method is applied to a two-link robotic manipulator control system which is configured as a direct controller for the system to demonstrate the capability of our scheme. Also, the advantages of the proposed structure over other traditional neural network structures are discussed.     

Evaluation of the Simplex method for training simple multilayer neural networks

A learning algorithm based on the modified Simplex method is proposed for training multilayer neural networks. This algorithm is tested for neural modelling of experimental results obtained during cross-flow filtration tests. The Simplex method is compared to standard back-propagation. Simpler to implement, Simplex has allowed us to achieve better results over four different databases with lower calculation times. The Simplex algorithm is therefore of interest compared to the classical learning techniques for simple neural structures.     

Improved Bounds on Quantum Learning Algorithms

In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples.

An algorithm for merging meaps

Summary We present an algorithm to merge priority queues organized as heaps. The worst case number of comparisons required to merge two heaps of sizes k and n is O(log(n)*log(k)). The algorithm requires O(k) +log(n)*log (k)) data movements if heaps are implemented using arrays and O(log(n)*log(k)) for a pointer-based implementation. Previous algorithms require either O(n+k) data movements and comparisons, or O(k*log(log(n+k))) comparisons and O(k*log(n+k)) data movements. The algorithm presented in this paper improves on the previous algorithms for the case when k>log(n).This work was done while the authors were at McGill University, Montréal, Canada     

Simple learning algorithms using divide and conquer

This paper investigates what happens when a learning algorithm for a classC attempts to learn target formulas from a different class. In many cases, the learning algorithm will find a bad attribute or a property of the target formula which precludes its membership in the classC. To continue the learning process, we proceed by building a decision tree according to the possible values of this attribute (divide) and recursively run the learning algorithm for each value (conquer). This paper shows how to recursively run the learning algorithm for each value using the oracles of the target.We demonstrate that the application of this idea on some known learning algorithms can both simplify the algorithm and provide additional power to learn more classes. In particular, we give a simple exact learning algorithm, using membership and equivalence queries, for the class of DNF that is almost unate, that is, unate with the addition ofO (logn) nonunate variables and a constant number of terms. We also find algorithms in different models for boolean functions that depend onk terms.