Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach

At sufficiently low temperatures, the configurational phase space of a large spin-glass system breaks into many separated domains, each of which is referred to as a macroscopic state. The system is able to visit all spin configurations of the same macroscopic state, while it can not spontaneously jump between two different macroscopic states. Ergodicity of the whole configurational phase space of the system, however, can be recovered if a temperature-annealing process is repeated an infinite number of times. In a heating-annealing cycle, the environmental temperature is first elevated to a high level and then decreased extremely slowly until a final low temperature T is reached. Different macroscopic states may be reached in different rounds of the annealing experiment; while the probability of finding the system in macroscopic state α decreases exponentially with the free energy F _α (T) of this state. For finite-connectivity spin glass systems, we use this free energy Boltzmann distribution to formulate the cavity approach of Mézard and Parisi [Eur. Phys. J. B, 2001, 20: 217] in a slightly different form. For the ±J spin-glass model on a random regular graph of degree K = 6, the predictions of the present work agree with earlier simulational and theoretical results.      

Combination of two basic types of synchronization in a coupled semiconductor laser system

Combination of two basic types of synchronization, anticipatory synchronization and lagged synchronization, is investigated numerically between two coupled semiconductor lasers. It is found that lagged synchronization produced by a backward coupling with a suitable delay can combine with the originally hidden anticipatory synchronization and produce a type of synchronization overcoming the original lagged synchronization produced by a forward coupling. We study the combination synchronization phenomenon when the delay of the backward coupling is different from that of the original anticipatory synchronization. Our results suggest that the synchronization combination phenomenon might allow an interpretation of an experimental observation by Sivaprakasam et al. [Phys. Rev. Lett. 87, 154101 (2001)] that the anticipating time is irrespective of the external-cavity round trip time, which to date remains to be understood.     

A physical organic mechanistic approach to understanding the complex reaction network of hemostasis (blood clotting)

This review focuses on how the mechanistic approach of physical organic chemistry can be used to elucidate the mechanisms behind complex biochemical networks. The dynamics of biochemical reaction networks is difficult to describe by considering their individual reactions, just as the dynamics of organic reactions is difficult to describe by considering individual electrons and atomic nuclei. Physical organic chemists have developed a useful set of tools to predict the outcome of organic reactions by separating the interacting molecules into modules (functional groups), and defining general rules for how these modules interact (mechanisms). This review shows how these tools of physical organic chemistry may be used to describe reaction networks. In addition, it describes the application of these tools to develop a mechanistic understanding of the dynamics of the complex network of hemostasis, which regulates blood clotting. Copyright © 2007 John Wiley & Sons, Ltd.     

Inferring topological features of proteins from amino acid residue networks

Topological properties of native folds are obtained from statistical analysis of 160 low homology proteins covering the four structural classes. This is done analyzing one, two and three-vertex joint distribution of quantities related to the corresponding network of amino acid residues. Emphasis on the amino acid residue hydrophobicity leads to the definition of their center of mass as vertices in this contact network model with interactions represented by edges. The network analysis helps us to interpret experimental results such as hydrophobic scales and fraction of buried accessible surface area in terms of the network connectivity. Moreover, those networks show assortative mixing by degree. To explore the vertex-type dependent correlations, we build a network of hydrophobic and polar vertices. This procedure presents the wiring diagram of the topological structure of globular proteins leading to the following attachment probabilities between hydrophobic–hydrophobic 0.424(5), hydrophobic-polar 0.419(2) and polar–polar 0.157(3) residues.     

Structural complexity of disordered surfaces: Analyzing the porous silicon SFM patterns

This paper introduces a relative structural complexity measure for the characterization of disordered surfaces. Numerical solutions of 2d+1 KPZ equation and scanning force microscopy (SFM) patterns of porous silicon samples are analyzed using this methodology. The results and phenomenological interpretation indicate that the proposed measure is efficient for quantitatively characterize the structural complexity of disordered surfaces (and interfaces) observed and/or simulated in nano, micro and ordinary scales.     

FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension

We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. Moreover, using a weaker notion of approximation, we show the existence of a fully polynomial-time approximation scheme for the problem of maximizing or minimizing an arbitrary polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. A conference version of this article, containing a part of the results presented here, appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006, pp. 743–748. The first author gratefully acknowledges support from NSF grant DMS-0608785, a 2003 UC-Davis Chancellor’s fellow award, the Alexander von Humboldt foundation, and IMO Magdeburg. The remaining authors were supported by the European TMR network ADONET 504438.     

PSPACE complexity of modal logic <Emphasis Type="Italic">K D</Emphasis>45<Subscript>n</Subscript>

We study sequent calculus for multi-modal logic K D45_n and its complexity. We introduce a loop-check free sequent calculus. Loop-check is eliminated by using the marked modal operator □_i^•, which is used as an alternative to sequents with histories ([8], [3], [5]). All inference rules are invertible or semi-invertible. To get this, we use or branches beside common and branches. We prove the equivalence between known sequent calculus and our newly introduced efficient sequent calculus. We concentrate on the complexity analysis of the introduced sequent calculus for multi-modal logic K D45_n. We prove that the space complexity of the given calculus is polynomial (O(l ³)). We show the maximum height of the constructed derivation tree that leads to the reduction of the time and space complexity. We present a decision algorithm for multi-modal logic K D45_n and some nontrivial examples to improve the introduced loop-check free sequent calculus.     

About Segment Complexity of Turing Reductions

We apply complexity concepts to define a new sort of sub-Turing reducibilities ≤ ?? make the degree hierarchy thinner and to obtain some new specifications of the well known jump inversion theorem of Friedberg. We show that this theorem doesn't hold when ≤ T is replaced with ≤ ??, where ?? is any countable subset of the class ?? of all total increasing functions f : ? → ?.     

Two hardness results for core stability in hedonic coalition formation games

We establish NP-completeness of two problems on core stable coalitions in hedonic games. In the first problem every player has only two acceptable coalitions in his preference list, and in the second problem the preference structures arise from the distances in an underlying metric space.