作者：
Williams, R. RyanMIT
Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA
We present a randomized method for computing the min-plus product (a.k.a. tropical product) of two n x n matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense n-node dir...
详细信息
We present a randomized method for computing the min-plus product (a.k.a. tropical product) of two n x n matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense n-node directed graphs with arbitrary edge weights. In the real random-access machine model, where additions and comparisons of reals are unit cost (but all other operations have logarithmic cost), the algorithm runs in time n(3)/2(Omega)(log n)(1/2) and is correct with high probability. On the word random-access machine which permits constant-time operations on log(n)-bit words, the algorithm runs in n(3)/2(Omega)(log n)(1/2) + n(2+o(1)) log(nM) time on graphs with edge weights in ([0, M] boolean AND Z) boolean OR {infinity}. Prior algorithms needed either Theta (n(3)/log(c) n) time for various c <= 2, or Theta (M(alpha)n(beta)) time for various alpha > 0 and beta > 2. Our algorithm applies a tool from circuit complexity, namely, the Razborov-Smolensky polynomials for approximately representing AC(0)[p] circuits, to efficiently reduce a matrix product over the min-plus algebra to a relatively small number of rectangular matrix products over F-2. Each rectangular matrix product can be computed using a particularly efficient method due to Coppersmith. We also give a deterministic version of the algorithm running in n(3)/2(log delta) n time for some delta > 0, which utilizes the Yao-Beigel-Tarui translation of AC(0)[m] circuits into "nice" depth-two circuits
We introduce wire length as a salient complexity measure for analyzing the circuit complexity of sensory processing in biological neural systems. This new complexity measure is applied in this paper to two basic compu...
详细信息
We introduce wire length as a salient complexity measure for analyzing the circuit complexity of sensory processing in biological neural systems. This new complexity measure is applied in this paper to two basic computational problems that arise in translation- and scale-invariant pattern recognition, and hence appear to be useful as benchmark problems for sensory processing. We present new circuit design strategies for these benchmark problems that can be implemented within realistic complexity bounds, in particular with linear or almost linear wire length. Finally, we derive some general bounds which provide information about the relationship between new complexity measure wire length and traditional circuit complexity measures. (C) 2004 Elsevier Inc. All rights reserved.
This paper aims to place neural networks in the context of boolean circuit complexity. We define appropriate classes of feedforward neural networks with specified fan-in, accuracy of computation and depth and using te...
详细信息
This paper aims to place neural networks in the context of boolean circuit complexity. We define appropriate classes of feedforward neural networks with specified fan-in, accuracy of computation and depth and using techniques of communication complexity proceed to show that the classes fit into a well-studied hierarchy of boolean circuits. Results cover both classes of sigmoid activation function networks and linear threshold networks. This provides a much needed theoretical basis for the study of the computational power of feedforward neural networks.
Toffoli gates are natural elements for the circuit model based quantum computation. We investigate general resource requirements for arbitrary n-qubit Toffoli gate. These resources consist of the nontrivial Clifford g...
详细信息
Toffoli gates are natural elements for the circuit model based quantum computation. We investigate general resource requirements for arbitrary n-qubit Toffoli gate. These resources consist of the nontrivial Clifford gate (CNOT), non-Clifford gate (T gate), ancillary qubits, and circuit depth. To implement n-qubit Toffoli gates, we consider two cases: only one auxiliary qubit and unlimited auxiliary qubits. The key of the first case is to decompose an n-qubit Toffoli gate into the reduced Toffoli gate modulo phase shift using the Clifford gates and one ancillary qubit. With this construction, it only requires O(n) number of general resources for an n-qubit Toffoli gate. For the second case, an approximate Toffoli gate is constructed to obtain efficient decomposition of a Toffoli gate. The new decomposition can further reduce general resources except auxiliary qubits.
A Boolean function on n variables is k-mixed if any two distinct restrictions fixing the same set of k variables induce distinct functions on the remaining n - k variables. We give an explicit construction of an (n - ...
详细信息
A Boolean function on n variables is k-mixed if any two distinct restrictions fixing the same set of k variables induce distinct functions on the remaining n - k variables. We give an explicit construction of an (n - o(n))-mixed Boolean function whose circuit complexity over the basis U-2 is 5n + o(n). This shows that a lower bound method for the size of a U2 circuit that applies to arbitrary well-mixed functions, which yields the largest known lower bound of 5n - o(n) for the U-2-circuit size (Mama, Lachish, Morizumi and Raz [STOC01, MFCS02]), has reached the limit. (C) 2010 Elsevier B.V. All rights reserved.
作者：
Williams, R. RyanMIT
Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA Stanford Univ
Stanford CA 94305 USA
We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two n x n matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense n-nod...
详细信息
We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two n x n matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense n-node directed graphs with arbitrary edge weights. On the real RAM, where additions and comparisons of reals are unit cost (but all other operations have typical logarithmic cost), the algorithm runs in time n(3)/2(Omega(log n)1/2) and is correct with high probability. On the word RAM with wordsize log(n), the algorithm runs in n(3)/2(Omega(log n)1/2) + n(2+o(1)) log(nM) time for edge weights in ([0, M] boolean AND Z) boolean OR {infinity}. Prior algorithms took either O(n(3)/log(c)n) time for various c <= 2, or O(M(alpha)n(beta)) time for various alpha > 0 and beta > 2. The new algorithm applies a tool from circuit complexity, namely the Razborov-Smolensky polynomials for approximately representing AC(0)[p] circuits, to efficiently reduce a matrix product over the (min, +) algebra to a relatively small number of rectangular matrix products over F-2, each of which is computable using a particularly efficient method due to Coppersmith. We also give a deterministic version of the algorithm running in n(3)/2log(delta)n time for some delta > 0, which utilizes the Yao-Beigel-Taru translation of AC(0)[m] circuits into "nice" depth-two circuits.
We consider hypotheses about nondeterministic computation that have been studied in different contexts and shown to have interesting consequences: The measure hypothesis: NP does not have p-measure 0. The pseudo-NP hy...
详细信息
We consider hypotheses about nondeterministic computation that have been studied in different contexts and shown to have interesting consequences: The measure hypothesis: NP does not have p-measure 0. The pseudo-NP hypothesis: there is an NP language that can be distinguished from any DTIME(2(n epsilon)) language by an NP refuter. The NP-machine hypothesis: there is an NP machine accepting 0* for which no 2(n epsilon)-time machine can find infinitely many accepting computations. We show that the NP-machine hypothesis is implied by each of the first two. Previously, no relationships were known among these three hypotheses. Moreover, we unify previous work by showing that several derandomizations and circuit-size lower bounds that are known to follow from the first two hypotheses also follow from the NP-machine hypothesis. In particular, the NP-machine hypothesis becomes the weakest known uniform hardness hypothesis that derandomizes AM. We also consider UP versions of the above hypotheses as well as related immunity and scaled dimension hypotheses.
This note consists of two independent parts. In the first part the concept of an (m,c)-system for a set of linear forms is introduced, and a lower bound is obtained for the algebraic complexity of the computation of (...
详细信息
A Boolean function on n variables is k-mixed if any two distinct restrictions fixing the same set of k variables induce distinct functions on the remaining n - k variables. We give an explicit construction of an (n - ...
详细信息
A Boolean function on n variables is k-mixed if any two distinct restrictions fixing the same set of k variables induce distinct functions on the remaining n - k variables. We give an explicit construction of an (n - o(n))-mixed Boolean function whose circuit complexity over the basis U-2 is 5n + o(n). This shows that a lower bound method for the size of a U2 circuit that applies to arbitrary well-mixed functions, which yields the largest known lower bound of 5n - o(n) for the U-2-circuit size (Mama, Lachish, Morizumi and Raz [STOC01, MFCS02]), has reached the limit. (C) 2010 Elsevier B.V. All rights reserved.
The paper is focused on the implementation of parity functions by circuits in the basis U-infinity. This basis consists of all gates that implement functions of the form x(1)(sigma 1) & ... & x(k)(sigma k). It...
详细信息
The paper is focused on the implementation of parity functions by circuits in the basis U-infinity. This basis consists of all gates that implement functions of the form x(1)(sigma 1) & ... & x(k)(sigma k). It is proved that every circuit in U-infinity implementing a parity function of n variables contains at least 2 1/9 n + Theta(1) gates.
暂无评论