On simulating the quantum and classical branching programs

The complexity classes defined on the basis of branching programs are considered. Some basic relations are established between the complexity classes defined by the probabilistic and quantum branching programs (measure-once, as well as measure-many), computing with bounded or unbounded error. To prove these relations, we developed a method of “linear simulation” of a quantum branching program and a method of “quantum simulation” of a probabilistic branching program.     

The Emergence of Social Order by Processes of Typifying: A Computational Model

The article argues that Rational Choice approaches are not sufficient to explain the “how” of the emergence of social order. Therefore, the concept of “typifying” according to the theory of Berger and Luckmann is understood as the most important form of establishing social orders between different social actors. A computational model is described that captures the basic features of the typifying process. Each artifical actor consists of two different neural nets, an “action net” and a “perception net”. These nets allow an actor to establish social rules of interaction with other actors, to remember the other actors after a time and to typify new actors as persons that belong to the same type as actors the first actor is already “acquainted” with. Experimental results and theoretical consequences are also given.     

Correspondence and canonical analysis of relational data

Correspondence analysis, a data analytic technique used to study two‐way cross‐classifications, is applied to social relational data. Such data are frequently termed “sociometric” or “network” data. The method allows one to model forms of relational data and types of empirical relationships not easily analyzed using either standard social network methods or common scaling or clustering techniques. In particular, correspondence analysis allows one to model:

—two‐mode networks (rows and columns of a sociomatrix refer to different objects)

—valued relations (e.g. counts, ratings, or frequencies).

In general, the technique provides scale values for row and column units, visual presentation of relationships among rows and columns, and criteria for assessing “dimensionality” or graphical complexity of the data and goodness‐of‐fit to particular models. Correspondence analysis has recently been the subject of research by Goodman, Haberman, and Gilula, who have termed their approach to the problem “canonical analysis” to reflect its similarity to canonical correlation analysis of continuous multivariate data. This generalization links the technique to more standard categorical data analysis models, and provides a much‐needed statistical justificatioa

We review both correspondence and canonical analysis, and present these ideas by analyzing relational data on the 1980 monetary donations from corporations to nonprofit organizations in the Minneapolis St. Paul metropolitan area. We also show how these techniques are related to dyadic independence models, first introduced by Holland, Leinhardt, Fienberg, and Wasserman in the early 1980's. The highlight of this paper is the relationship between correspondence and canonical analysis, and these dyadic independence models, which are designed specifically for relational data. The paper concludes with a discussion of this relationship, and some data analyses that illustrate the fart that correspondence analysis models can be used as approximate dyadic independence models.     

Approximation to measurable functions and its relation to probabilistic computation

A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship between these two complexity measures is further studied and compared with the notion of the distribution-free probabilistic computation. The computational complexity of the Lebesgue integral of polynomial-time approximable functions is studied and related to the question “FP = ♯P?”.     

A Note on a Traffic Counting Distribution

In this paper the author formulates and derives a discrete traffic counting distribution and a passing rule which lead to bunches of zero or one “fast” vehicle behind a “slow” vehicle. “Slow” vehicles are distributed in a Poisson fashion and, except for those instants at which passing occurs, the constrained or “fast” vehicles follow immediately behind a “slow” one. The counting distribution is a simple example of one in which successive inter-vehicle spacings have the Markov property.     

The emergence of dynamical complexity: An exploration using elementary cellular automata

This work concerns the interaction between two classical problems: the forecasting of the dynamical behaviors of elementary cellular automata (ECA) from its intrinsic mathematical laws and the conditions that determine the emergence of complex dynamics. To approach these problems, and inspired by the theory of reversible logical gates, we decompose the ECA laws in a “spectrum” of dyadic Boolean gates. Emergent properties due to interactions are captured generating another spectrum of logical gates. The combined analysis of both spectra shows the existence of characteristic bias in the distribution of Boolean gates for ECA belonging to different dynamical classes. These results suggest the existence of signatures capable to indicate the propensity to develop complex dynamics. Logical gates “exclusive‐or” and “equivalence” are among these signatures of complexity. An important conclusion is that within ECA space, interactions are not capable to generate signatures of complexity in the case these signatures are absent in the intrinsic law of the automaton. © 2004 Wiley Periodicals, Inc. Complexity 9: 33–42, 2004     

Canonizing structural Ramsey theorems

At the beginning of 1950s Erd?s and Rado suggested the investigation of the Ramsey-type results where the number of colors is not finite. This marked the birth of the so-called canonizing Ramsey theory. In 1985 Prömel and Voigt made the first step towards the structural canonizing Ramsey theory when they proved the canonical Ramsey property for the class of finite linearly ordered hypergraphs, and the subclasses thereof defined by forbidden substructures. Building on their results in this paper we provide several new structural canonical Ramsey results. We prove the canonical Ramsey theorem for the class of all finite linearly ordered tournaments, the class of all finite posets with linear extensions and the class of all finite linearly ordered metric spaces. We conclude the paper with the canonical version of the celebrated Ne?et?il–Rödl Theorem. In contrast to the “classical” Ramsey-theoretic approach, in this paper we advocate the use of category theory to manage the complexity of otherwise technically overwhelming proofs typical in canonical Ramsey theory.     

An infinitary probability logic for type spaces

Type spaces in the sense of Harsanyi (1967/68) play an important role in the theory of games of incomplete information. They can be considered as the probabilistic analog of Kripke structures. By an infinitary propositional language with additional operators “individual i assigns probability at least α to” and infinitary inference rules, we axiomatize the class of (Harsanyi) type spaces. We prove that our axiom system is strongly sound and strongly complete. To the best of our knowledge, this is the very first strong completeness theorem for a probability logic with σ-additive probabilities. We show this by constructing a canonical type space whose states consist of all maximal consistent sets of formulas. Furthermore, we show that this canonical space is universal (i.e., a terminal object in the category of type spaces) and beliefs complete.     

Chaos in M(atrix) theory

We consider the classical and quantum dynamics in M(atrix) theory. Using a simple ansatz we show that a classical trajectory exhibits a chaotic motion. We argue that the holographic feature of M(atrix) theory is related with the repulsive feature of energy eigenvalues in quantum chaotic system. Chaotic dynamics in N = 2 supersymmetric Yang—Mills theory is also discussed. We demonstrate that after the separation of “slow” and “fast” modes there is a singular contribution from the “slow” modes to the Hamiltonian of the “fast” modes.     

Stochastic differential equations

When a system is acted upon by exterior disturbances, its time-development can often be described by a system of ordinary differential equations, provided that the disturbances are smooth functions. But for sound reasons physicists and engineers usually want the theory to apply when the noises belong to a larger class, including for example “white noise.” If the integrals in the system derived for smooth noises are reinterpreted as Itô integrals, the equations make sense; but in nonlinear cases they often fail to describe the time-development of the system. In this paper (extending previous work of the author) a calculus is set up for stochastic systems that extends to a theory of differential equations. When the equations are known that describe the development of the system when noises are smooth, an extension to the larger class of noises is proposed that in many cases gives results consistent with the smooth-noise case and also has “robust” solutions, that change by small amounts when the noises undergo small changes. This is called the “canonical” extension.Nevertheless, there are certain systems in which the canonical equations are inappropriate. A criterion is suggested that may allow us to distinguish when the canonical equations are the right choice and when they are not.     

Generating M-Indeterminate Probability Densities by Way of Quantum Mechanics

Probability densities that are not uniquely determined by their moments are said to be “moment-indeterminate,” or “M-indeterminate.” Determining whether or not a density is M-indeterminate, or how to generate an M-indeterminate density, is a challenging problem with a long history. Quantum mechanics is inherently probabilistic, yet the way in which probability densities are obtained is dramatically different in comparison with standard probability theory, involving complex wave functions and operators, among other aspects. Nevertheless, the end results are standard probabilistic quantities, such as expectation values, moments and probability density functions. We show that the quantum mechanics procedure to obtain densities leads to a simple method to generate an infinite number of M-indeterminate densities. Different self-adjoint operators can lead to new classes of M-indeterminate densities. Depending on the operator, the method can produce densities that are of the Stieltjes class or new formulations that are not of the Stieltjes class. As such, the method complements and extends existing approaches and opens up new avenues for further development. The method applies to continuous and discrete probability densities. A number of examples are given.

     

Zum Begriff der “Argumentation” im Rahmen einer Interaktionstheorie des Lernens und Lehrens von Mathematik

Recent theories of learning emphasize increasingly the social dimension of cognitive development. With regard to this movement, BRUNER (1990), for example, speaks of a “cultural psychology” and MILLER (1986) describes his own approach as the attempt of generating a “sociological theory of learning”. In the following paper the concept of “argumentation” will be applied in order to develop an “interactional theory of, learning and teaching mathematics” and will be based on an extended analysis of interaction of an episode of students’ group work.     

Analysis of non-linear stochastic oscillations by the averaging method

The solution of a quasiconservative non-linear oscillatory system is considered, the right-hand sides of which are proportional to a small parameter. Fundamental relations for solving the problem are obtained by changing to “slow” variables and a combination of the stochastic averaging method and the theory of Markov processes. An efficient numerical algorithm is developed based on the fast Fourier transform that enables the output parameter distribution density and the amplitudes of the oscillations to be obtained. Application of the theory to solve the Duffing–van der Pol equation for an additive and multiplicative stochastic action is considered.     

Combining evolutionary game theory and network theory to analyze human cooperation patterns

As natural systems continuously evolve, the human cooperation dilemma represents an increasingly more challenging question. Humans cooperate in natural and social systems, but how it happens and what are the mechanisms which rule the emergence of cooperation, represent an open and fascinating issue. In this work, we investigate the evolution of cooperation through the analysis of the evolutionary dynamics of behaviours within the social network, where nodes can choose to cooperate or defect following the classical social dilemmas represented by Prisoner’s Dilemma and Snowdrift games. To this aim, we introduce a sociological concept and statistical estimator, “Critical Mass”, to detect the minimum initial seed of cooperators able to trigger the diffusion process, and the centrality measure to select within the social network. Selecting different spatial configurations of the Critical Mass nodes, we highlight how the emergence of cooperation can be influenced by this spatial choice of the initial core in the network. Moreover, we target to shed light how the concept of homophily, a social shaping factor for which “birds of a feather flock together”, can affect the evolutionary process. Our findings show that homophily allows speeding up the diffusion process and make quicker the convergence towards human cooperation, while centrality measure and thus the Critical Mass selection, play a key role in the evolution showing how the spatial configurations can create some hidden patterns, partially counterbalancing the impact of homophily.     

Communication structure,trust and the free rider problem

Despite the recent wave of interest in the social and physical sciences regarding “complexity,” relatively title attention has been given to the logical foundation of complexity measurement. With this in mind, a number of fairly simple, “reasonable” axioms for the measurement of network complexity are here presented, and some of the implications of these axioms are considered. It is shown that the only family of graph complexity measures satisfying the “reasonable” axioms is of limited theoretical utility, and hence that those seeking more interesting measures of complexity must be willing to sacrifice at least one intuitively reasonable constraint. Several existing complexity measures are also described, and are differentiated from one another on an axiomatic basis. Finally, some suggestions are offered regarding future efforts at measuring graph complexity.     

Slow convergence of sequences of linear operators II: Arbitrarily slow convergence

We study the rate of convergence of a sequence of linear operators that converges pointwise to a linear operator. Our main interest is in characterizing the slowest type of pointwise convergence possible. This is a continuation of the paper Deutsch and Hundal (2010) [14]. The main result is a “lethargy” theorem (Theorem 3.3) which gives useful conditions that guarantee arbitrarily slow convergence. In the particular case when the sequence of linear operators is generated by the powers of a single linear operator, we obtain a “dichotomy” theorem, which states the surprising result that either there is linear (fast) convergence or arbitrarily slow convergence; no other type of convergence is possible. The dichotomy theorem is applied to generalize and sharpen: (1) the von Neumann–Halperin cyclic projections theorem, (2) the rate of convergence for intermittently (i.e., “almost” randomly) ordered projections, and (3) a theorem of Xu and Zikatanov.     

Homogenization in the problem of long water waves over a bottom site with fast oscillations

The system of equations of gravity surface waves is considered in the case where the basin’s bottom is given by a rapidly oscillating function against a background of slow variations of the bottom. Under the assumption that the lengths of the waves under study are greater than the characteristic length of the basin bottom’s oscillations but can be much less than the characteristic dimensions of the domain where these waves propagate, the adiabatic approximation is used to pass to a reduced homogenized equation of wave equation type or to the linearized Boussinesq equation with dispersion that is “anomalous” in the theory of surface waves (equations of wave equation type with added fourth derivatives). The rapidly varying solutions of the reduced equation can be found (and they were also found in the authors’ works) by asymptotic methods, for example, by the WKB method, and in the case of focal points, by the Maslov canonical operator and its generalizations.     

On Smale's 17th Problem: A Probabilistic Positive Solution

Smale's 17th Problem asks “Can a zero of n complex polynomial equations in n unknowns be found approximately, on the average [for a suitable probability measure on the space of inputs], in polynomial time with a uniform algorithm?” We present a uniform probabilistic algorithm for this problem and prove that its complexity is polynomial. We thus obtain a partial positive solution to Smale's 17th Problem.     

Something out of nothing: a Bayesian learning computational model for the social construction of value

ABSTRACT

This article develops a formalism for the social construction of value. Using a model based on Bayesian agents, it demonstrates how “something” arises out of “nothing” via the emergence of durable value conventions and shows how the developed framework can be used to investigate socially constructed valuations under a variety of circumstances. The resulting analysis clarifies why assumptions that collectives will converge upon the “intrinsic” (i.e., non-socially originating) value of an object (e.g., market efficiency) may not hold for mixed social and non-social valuation regimes, explains the dependency of socially constructed valuations on early accidents, demonstrates the effects of confident actors on constructed values, and identifies the production of time-dependent ratcheting effects from the interaction of bubbles with value conventions.