We investigate the complexity of depth-3 threshold circuits with majority gates at the output, possibly negated AND gates at level two, and MODm gates at level one. We show that the fan-in of the AND gates can be redu...
详细信息
We investigate the complexity of depth-3 threshold circuits with majority gates at the output, possibly negated AND gates at level two, and MODm gates at level one. We show that the fan-in of the AND gates can be reduced to O(log n) in the case where m is unbounded, and to a constant in the case where m is constant. We then use these upper bounds to derive exponential lower bounds for this class of circuits. In the unbounded m case, this yields a new proof of a lower bound of Grolmusz;in the constant m case, our result sharpens his lower bound. In addition, we prove an exponential lower bound if OR gates are also permitted on level two and m is a constant prime power.
Spectral partitioning methods use the Fiedler vector-the eigenvector of the second-smallest eigenvalue of the Laplacian matrix-to find a small separator of a graph. These methods are important components of many scien...
详细信息
Spectral partitioning methods use the Fiedler vector-the eigenvector of the second-smallest eigenvalue of the Laplacian matrix-to find a small separator of a graph. These methods are important components of many scientific numerical algorithms and have been demonstrated by experiment to work extremely well. In this paper, we show that spectral partitioning methods work well on bounded-degree planar graphs and finite element meshes-the classes of graphs to which they are usually applied. While active spectral bisection does not necessarily work, we prove that spectral partitioning techniques can be used to produce separators whose ratio of vertices removed to edges cut is O(/spl radic/n) for bounded-degree planar graphs and two-dimensional meshes and O(n/sup 1/d/) for well-shaped d-dimensional meshes. The heart of our analysis is an upper bound on the second-smallest eigenvalues of the Laplacian matrices of these graphs: we prove a bound of O(1/n) for bounded-degree planar graphs and O(1/n/sup 2/d/) for well-shaped d-dimensional meshes.
The authors study the question of determining whether an unknown function has a particular property or is /spl epsiv/-far from any function with that property. A property testing algorithm is given a sample of the val...
详细信息
The authors study the question of determining whether an unknown function has a particular property or is /spl epsiv/-far from any function with that property. A property testing algorithm is given a sample of the value of the function on instances drawn according to some distribution, and possibly may query the function on instances of its choice. First, they establish some connections between property testing and problems in learning theory. Next, they focus on testing graph properties, and devise algorithms to test whether a graph has properties such as being k-colorable or having a /spl rho/-clique (clique of density /spl rho/ w.r.t. the vertex set). The graph property testing algorithms are probabilistic and make assertions which are correct with high probability utilizing only poly(1//spl epsiv/) edge-queries into the graph, where /spl epsiv/ is the distance parameter. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph which correspond to the property being tested, if it holds for the input graph.
In a fair multicast video distribution scheme each receiver should receive a video stream with a quality that is commensurate with its capabilities or the capabilities of the path leading to it, regardless of other re...
详细信息
In a fair multicast video distribution scheme each receiver should receive a video stream with a quality that is commensurate with its capabilities or the capabilities of the path leading to it, regardless of other receivers or network paths. This fairness problem results from the fact that multicast communication trades economy of bandwidth with granularity of control. Distributing video using individual feedback-controlled point-to-point streams results in high bandwidth utilization but the granularity of control is high as communication parameters can be negotiated individually with each receiver. In contrast, using a single multicast stream has good bandwidth economy, but very low granularity of control. In this paper we propose, implement and experiment with a system that spans the spectrum represented by the two extremes above. In the scheme, called destination set grouping (DSG), a source maintains a small number of video streams, carrying the same video but each targeted at receivers with different capabilities. Each stream is feedback-controlled within prescribed limits by its group of receivers. Receivers may move among streams as their capabilities or the capabilities of the network paths leading to them change. The scheme is shown to improve fairness significantly at a small bandwidth cost.
We present an analysis of the effects of face distinctiveness on the performance of a computational model of recognition over viewpoint change. In the first stage of the model, the face stimulus is normalized by being...
详细信息
We present an analysis of the effects of face distinctiveness on the performance of a computational model of recognition over viewpoint change. In the first stage of the model, the face stimulus is normalized by being mapped to an arbitrary standard view. In the second stage, the normalized stimulus is mapped into a "face space" spanned by a number of reference faces, and is classified as familiar or unfamiliar We carried out experiments employing a parametrically generated family of face stimuli that vary in distinctiveness. The experiments show that while the "view-mapping" process operates more accurately for typical versus distinctive faces, the base level distinctiveness of the faces is preserved in the face space coding. These data provide insight into how the psychophysically well-established inverse relationship between the typically and recognizability of faces might operate for recognition across changes in viewpoint.
An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of a given (undirected or directed) graph G=(V,E). There are four versions of the problem, depending on wheth...
详细信息
An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of a given (undirected or directed) graph G=(V,E). There are four versions of the problem, depending on whether G is undirected or directed, and whether the spanning subgraph is required to be k-node connected (k-NCSS) or k-edge connected (k-ECSS). The approximation guarantees are as follows: min-size k-NCSS of an undirected graph 1+[1/k], min-size k-NCSS of a directed graph 1+[1/k], min-size k-ECSS of an undirected graph 1+[7/k], & min-size k-ECSS of a directed graph 1+[4//spl radic/k]. The heuristic is based on a subroutine for the degree-constrained subgraph (b-matching) problem. It is simple, deterministic, and runs in time O(k|E|/sup 2/). For undirected graphs and k=2, a (deterministic) parallel NC version of the heuristic finds a 2-node connected (or a-edge connected) spanning subgraph whose size is within a factor of (1.5+/spl epsiv/) of minimum, where /spl epsiv/>0 is a constant.
We show that no fixed number of parallel repetitions suffices in order to reduce the error in two-prover one-round proof systems from one constant to another. Our results imply that the recent bounds proven by Ran Raz...
详细信息
We show that no fixed number of parallel repetitions suffices in order to reduce the error in two-prover one-round proof systems from one constant to another. Our results imply that the recent bounds proven by Ran Raz (1995), showing that the number of rounds that suffice is inversely proportional to the answer length, are nearly best possible.
In this paper we apply the method of complexity regularization to derive estimation bounds for nonlinear function estimation using a single hidden layer radial basis function network. Our approach differs from the pre...
In this paper we apply the method of complexity regularization to derive estimation bounds for nonlinear function estimation using a single hidden layer radial basis function network. Our approach differs from the previous complexity regularization neural network function learning schemes in that we operate with random covering numbers and l1 metric entropy, making it possible to consider much broader families of activation functions, namely functions of bounded variation. Some constraints previously imposed on the network parameters are also eliminated this way. The network is trained by means of complexity regularization involving empirical risk minimization. Bounds on the expected risk in terms of the sample size are obtained for a large class of loss functions. Rates of convergence to the optimal loss are also derived.
The goal of many image processing tasks is to recognise objects, to match scenes and to classify images. The shape, gray or colour features of objects are mainly used to describe objects. The most efficient method use...
详细信息
The goal of many image processing tasks is to recognise objects, to match scenes and to classify images. The shape, gray or colour features of objects are mainly used to describe objects. The most efficient method used to describe such features of an object is to use various transformed moments. We express the moments as a linear combination of higher order prefix sums, obtained by iterating the prefix sum computation on previous prefix sums, starting with the original function values. Thus the p'th moment m/sub p/=/spl Sigma//sub x=1//sup N/ x/sup p/f(x) can be computed by O(N/spl middot/p) additions followed by p multiply-adds. The prefix summations can be realized in time O(N) using p+1 simple adders, and in time O(p/spl middot/log N) using parallel prefix computation and O(N) adders. In 1986 Hatamian published a computationally equivalent algorithm, based on a cascade of filters performing the summations. Our recursive derivation allows for explicit expressions and recursive equations for the coefficients used in the final moment calculation. Thus a number of alternative forms for the moment computation can be derived, based on different sets of prefix sums, allowing some simplifications in the implementations.
暂无评论