Search results for " complexity."
showing 10 items of 603 documents
Some Afterthoughts on Hopfield Networks
1999
In the present paper we investigate four relatively independent issues, which complete our knowledge regarding the computational aspects of popular Hopfield nets. In Section 2 of the paper, the computational equivalence of convergent asymmetric and Hopfield nets is shown with respect to network size. In Section 3, the convergence time of Hopfield nets is analyzed in terms of bit representations. In Section 4, a polynomial time approximate algorithm for the minimum energy problem is shown. In Section 5, the Turing universality of analog Hopfield nets is studied. peerReviewed
Transition Function Complexity of Finite Automata
2019
State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata -- BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity.
Upper bounds on multiparty communication complexity of shifts
1996
We consider some communication complexity problems which arise when proving lower bounds on the complexity of Boolean functions. In particular, we prove an \(O(\frac{n}{{2\sqrt {\log n} }}\log ^{1/4} n)\)upper bound on 3-party communication complexity of shifts, an O(n e ) upper bound on the multiparty communication complexity of shifts for a polylogarithmic number of parties. These bounds are all significant improvements over ones recently considered “unexpected” by Pudlak [5].
Bounded Computational Capacity Equilibrium
2010
We study repeated games played by players with bounded computational power, where, in contrast to Abreu and Rubisntein (1988), the memory is costly. We prove a folk theorem: the limit set of equilibrium payoffs in mixed strategies, as the cost of memory goes to 0, includes the set of feasible and individually rational payoffs. This result stands in sharp contrast to Abreu and Rubisntein (1988), who proved that when memory is free, the set of equilibrium payoffs in repeated games played by players with bounded computational power is a strict subset of the set of feasible and individually rational payoffs. Our result emphasizes the role of memory cost and of mixing when players have bounded c…
Thermalization and condensation in an incoherently pumped passive optical cavity
2011
International audience; We study theoretically and numerically the condensation and the thermalization of classical optical waves in an incoherently pumped passive Kerr cavity. We show that the dynamics of the cavity exhibits a turbulent behavior that can be described by the wave turbulence theory. A mean-field kinetic equation is derived, which reveals that, in its high finesse regime, the cavity behaves essentially as a conservative Hamiltonian system. In particular, the intracavity turbulent field is shown to relax adiabatically toward a thermodynamic equilibrium state of energy equipartition. As a consequence of this effect of wave thermalization, the incoherent optical field undergoes …
Neural Network Based Finite-Time Stabilization for Discrete-Time Markov Jump Nonlinear Systems with Time Delays
2013
Published version of an article in the journal: Abstract and Applied Analysis. Also available from the publisher at: http://dx.doi.org/10.1155/2013/359265 Open Access This paper deals with the finite-time stabilization problem for discrete-time Markov jump nonlinear systems with time delays and norm-bounded exogenous disturbance. The nonlinearities in different jump modes are parameterized by neural networks. Subsequently, a linear difference inclusion state space representation for a class of neural networks is established. Based on this, sufficient conditions are derived in terms of linear matrix inequalities to guarantee stochastic finite-time boundedness and stochastic finite-time stabi…
Performance comparison of residual related algorithms for ToA positioning in wireless terrestrial and sensor networks
2009
©2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE." Article also available from publisher: http://dx.doi.org/10.1109/WIRELESSVITAE.2009.5172462 Time of Arrival (ToA) is a popular technique for terrestrial positioning. This paper presents a comparison of ToA based residual related positioning algorithms in wireless terrestrial and sensor networks in both long range outdoor and short range indoor environments. Us…
Hamiltonian structural analysis of curved beams with or without generalized two-parameter foundation
2013
The solution of curved Timoshenko beams with or without generalized two-parameter elastic foundation is presented. Beam can be subjected to any kind of loads and imposed external actions, distributed or concentrated along the beam. It can have external and internal restraints and any kind of internal kinematical or mechanical discontinuity. Moreover, the beam may have any spatial curved geometry, by dividing the entire structure into segments of constant curvature and constant elastic properties, each segment resting or not on elastic foundation. The foundation has six parameters like a generalized Winkler soil with the addition of other two parameters involving the link between settlements…
Multi-label Classification Using Stacked Hierarchical Dirichlet Processes with Reduced Sampling Complexity
2018
Nonparametric topic models based on hierarchical Dirichlet processes (HDPs) allow for the number of topics to be automatically discovered from the data. The computational complexity of standard Gibbs sampling techniques for model training is linear in the number of topics. Recently, it was reduced to be linear in the number of topics per word using a technique called alias sampling combined with Metropolis Hastings (MH) sampling. We propose a different proposal distribution for the MH step based on the observation that distributions on the upper hierarchy level change slower than the document-specific distributions at the lower level. This reduces the sampling complexity, making it linear i…
Lévy flights in confining potentials.
2009
We analyze confining mechanisms for L\'{e}vy flights. When they evolve in suitable external potentials their variance may exist and show signatures of a superdiffusive transport. Two classes of stochastic jump - type processes are considered: those driven by Langevin equation with L\'{e}vy noise and those, named by us topological L\'{e}vy processes (occurring in systems with topological complexity like folded polymers or complex networks and generically in inhomogeneous media), whose Langevin representation is unknown and possibly nonexistent. Our major finding is that both above classes of processes stay in affinity and may share common stationary (eventually asymptotic) probability densit…