Physics-inspired methods for networking and communications

Advances in statistical physics relating to our understanding of large-scale complex systems have recently been successfully applied in the context of communication networks. Statistical mechanics methods can be used to decompose global system behavior into simple local interactions. Thus, large-scale problems can be solved or approximated in a distributed manner with iterative lightweight local messaging. This survey discusses how statistical physics methodology can provide efficient solutions to hard network problems that are intractable by classical methods. We highlight three typical examples in the realm of networking and communications. In each case we show how a fundamental idea of statistical physics helps solve the problem in an efficient manner. In particular, we discuss how to perform multicast scheduling with message passing methods, how to improve coding using the crystallization process, and how to compute optimal routing by representing routes as interacting polymers.

On the Vertex Separation of Maximal Outerplanar Graphs

We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.

Storage capacity of ultrametric committee machines

The problem of computing the storage capacity of a feed-forward network, with L hidden layers, N inputs, and K units in the first hidden layer, is analyzed using techniques from statistical mechanics. We found that the storage capacity strongly depends on the network architecture αc ∼ (log K)1-1/2L and that the number of units K limits the number of possible hidden layers L through the relationship 2L - 1 < 2log K. © 2014 IOP Publishing Ltd.

A Survey of Counterexamples to Hilbert's Fourteenth Problem

We survey counterexamples to Hilbert’s Fourteenth Problem, beginning with those of Nagata in the late 1950s, and including recent counterexamples in low dimension constructed with locally nilpotent derivations. Historical framework and pertinent references are provided. We also include 8 important open questions.

Special Functions and Pathways for Problems in Astrophysics: An Essay in Honor of A.M. Mathai

The paper provides a review of A.M. Mathai's applications of the theory of special functions, particularly generalized hypergeometric functions, to problems in stellar physics and formation of structure in the Universe and to questions related to reaction, diffusion, and reaction-diffusion models. The essay also highlights Mathai's recent work on entropic, distributional, and differential pathways to basic concepts in statistical mechanics, making use of his earlier research results in information and statistical distribution theory. The results presented in the essay cover a period of time in Mathai's research from 1982 to 2008 and are all related to the thematic area of the gravitationally stabilized solar fusion reactor and fractional reaction-diffusion, taking into account concepts of non-extensive statistical mechanics. The time period referred to above coincides also with Mathai's exceptional contributions to the establishment and operation of the Centre for Mathematical Sciences, India, as well as the holding of the United Nations (UN)/European Space Agency (ESA)/National Aeronautics and Space Administration (NASA) of the United States/ Japanese Aerospace Exploration Agency (JAXA) Workshops on basic space science and the International Heliophysical Year 2007, around the world. Professor Mathai's contributions to the latter, since 1991, are a testimony for his social con-science applied to international scientific activity.

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

ACM Computing Classification System (1998): G.2.2.

A Fast Algorithm for Weber Problem on a Grid

AMS subject classification: 90B80.

Source localization methods

One of the most pressing demands on electrophysiology applied to the diagnosis of epilepsy is the non-invasive localization of the neuronal generators responsible for brain electrical and magnetic fields (the so-called inverse problem). These neuronal generators produce primary currents in the brain, which together with passive currents give rise to the EEG signal. Unfortunately, the signal we measure on the scalp surface doesn't directly indicate the location of the active neuronal assemblies. This is the expression of the ambiguity of the underlying static electromagnetic inverse problem, partly due to the relatively limited number of independent measures available. A given electric potential distribution recorded at the scalp can be explained by the activity of infinite different configurations of intracranial sources. In contrast, the forward problem, which consists of computing the potential field at the scalp from known source locations and strengths with known geometry and conductivity properties of the brain and its layers (CSF/meninges, skin and skull), i.e. the head model, has a unique solution. The head models vary from the computationally simpler spherical models (three or four concentric spheres) to the realistic models based on the segmentation of anatomical images obtained using magnetic resonance imaging (MRI). Realistic models – computationally intensive and difficult to implement – can separate different tissues of the head and account for the convoluted geometry of the brain and the significant inter-individual variability. In real-life applications, if the assumptions of the statistical, anatomical or functional properties of the signal and the volume in which it is generated are meaningful, a true three-dimensional tomographic representation of sources of brain electrical activity is possible in spite of the ‘ill-posed’ nature of the inverse problem (Michel et al., 2004). The techniques used to achieve this are now referred to as electrical source imaging (ESI) or magnetic source imaging (MSI). The first issue to influence reconstruction accuracy is spatial sampling, i.e. the number of EEG electrodes. It has been shown that this relationship is not linear, reaching a plateau at about 128 electrodes, provided spatial distribution is uniform. The second factor is related to the different properties of the source localization strategies used with respect to the hypothesized source configuration.

Anisotropic opinion dynamics

We consider the process of opinion formation in a society of interacting agents, where there is a set B of socially accepted rules. In this scenario, we observed that agents, represented by simple feed-forward, adaptive neural networks, may have a conservative attitude (mostly in agreement with B) or liberal attitude (mostly in agreement with neighboring agents) depending on how much their opinions are influenced by their peers. The topology of the network representing the interaction of the society's members is determined by a graph, where the agents' properties are defined over the vertexes and the interagent interactions are defined over the bonds. The adaptability of the agents allows us to model the formation of opinions as an online learning process, where agents learn continuously as new information becomes available to the whole society (online learning). Through the application of statistical mechanics techniques we deduced a set of differential equations describing the dynamics of the system. We observed that by slowly varying the average peer influence in such a way that the agents attitude changes from conservative to liberal and back, the average social opinion develops a hysteresis cycle. Such hysteretic behavior disappears when the variance of the social influence distribution is large enough. In all the cases studied, the change from conservative to liberal behavior is characterized by the emergence of conservative clusters, i.e., a closed knitted set of society members that follow a leader who agrees with the social status quo when the rule B is challenged.

Efeitos do freio magnético sobre a distribuição da rotação estelar

The pioneering work proposed by Skumanich (1972) has shown that the projected mean rotational velocity < v sini > for solar type stars follows a rotation law decreases with the time given by t −1/2 , where t is the stellar age. This relationship is consistent with the theories of the angular momentum loss through the ionized stellar wind, which in turn is coupled to the star through its magnetic field. Several authors (e.g.: Silva et al. 2013 and de Freitas et al. 2014) have analyzed the possible matches between the rotational decay and the profile of the velocity distribution. These authors came to a simple heuristic relationship, but did not build a direct path between the exponent of the rotational decay (j) and the exponent of the distribution of the rotational velocity (q). The whole theoretical scenario has been proposed using an efficient and strong statistical mechanics well known as non-extensive statistical mechanics. The present dissertation proposes effectively to close this issue by elaborating a theoretical way to modify the q-Maxwellians’ distributions into q-Maxwellians with physics links extracted from the theory of magnetic braking. In order to test our distributions we have used the GenevaCapenhagen Survey data with approximately 6000 F and G field stars limited by age. As a result, we obtained that the exponents of the decay law and distribution follow a similar relationship to that proposed by Silva et al. (2013).

Coding Strategies and Implementations of Compressive Sensing

This dissertation studies the coding strategies of computational imaging to overcome the limitation of conventional sensing techniques. The information capacity of conventional sensing is limited by the physical properties of optics, such as aperture size, detector pixels, quantum efficiency, and sampling rate. These parameters determine the spatial, depth, spectral, temporal, and polarization sensitivity of each imager. To increase sensitivity in any dimension can significantly compromise the others.

This research implements various coding strategies subject to optical multidimensional imaging and acoustic sensing in order to extend their sensing abilities. The proposed coding strategies combine hardware modification and signal processing to exploiting bandwidth and sensitivity from conventional sensors. We discuss the hardware architecture, compression strategies, sensing process modeling, and reconstruction algorithm of each sensing system.

Optical multidimensional imaging measures three or more dimensional information of the optical signal. Traditional multidimensional imagers acquire extra dimensional information at the cost of degrading temporal or spatial resolution. Compressive multidimensional imaging multiplexes the transverse spatial, spectral, temporal, and polarization information on a two-dimensional (2D) detector. The corresponding spectral, temporal and polarization coding strategies adapt optics, electronic devices, and designed modulation techniques for multiplex measurement. This computational imaging technique provides multispectral, temporal super-resolution, and polarization imaging abilities with minimal loss in spatial resolution and noise level while maintaining or gaining higher temporal resolution. The experimental results prove that the appropriate coding strategies may improve hundreds times more sensing capacity.

Human auditory system has the astonishing ability in localizing, tracking, and filtering the selected sound sources or information from a noisy environment. Using engineering efforts to accomplish the same task usually requires multiple detectors, advanced computational algorithms, or artificial intelligence systems. Compressive acoustic sensing incorporates acoustic metamaterials in compressive sensing theory to emulate the abilities of sound localization and selective attention. This research investigates and optimizes the sensing capacity and the spatial sensitivity of the acoustic sensor. The well-modeled acoustic sensor allows localizing multiple speakers in both stationary and dynamic auditory scene; and distinguishing mixed conversations from independent sources with high audio recognition rate.

Petri Net Siphon Analysis and Network Centrality Measures for Identifying Combination Therapies in Signaling Pathways

Aberrant behavior of biological signaling pathways has been implicated in diseases such as cancers. Therapies have been developed to target proteins in these networks in the hope of curing the illness or bringing about remission. However, identifying targets for drug inhibition that exhibit good therapeutic index has proven to be challenging since signaling pathways have a large number of components and many interconnections such as feedback, crosstalk, and divergence. Unfortunately, some characteristics of these pathways such as redundancy, feedback, and drug resistance reduce the efficacy of single drug target therapy and necessitate the employment of more than one drug to target multiple nodes in the system. However, choosing multiple targets with high therapeutic index poses more challenges since the combinatorial search space could be huge. To cope with the complexity of these systems, computational tools such as ordinary differential equations have been used to successfully model some of these pathways. Regrettably, for building these models, experimentally-measured initial concentrations of the components and rates of reactions are needed which are difficult to obtain, and in very large networks, they may not be available at the moment. Fortunately, there exist other modeling tools, though not as powerful as ordinary differential equations, which do not need the rates and initial conditions to model signaling pathways. Petri net and graph theory are among these tools. In this thesis, we introduce a methodology based on Petri net siphon analysis and graph network centrality measures for identifying prospective targets for single and multiple drug therapies. In this methodology, first, potential targets are identified in the Petri net model of a signaling pathway using siphon analysis. Then, the graph-theoretic centrality measures are employed to prioritize the candidate targets. Also, an algorithm is developed to check whether the candidate targets are able to disable the intended outputs in the graph model of the system or not. We implement structural and dynamical models of ErbB1-Ras-MAPK pathways and use them to assess and evaluate this methodology. The identified drug-targets, single and multiple, correspond to clinically relevant drugs. Overall, the results suggest that this methodology, using siphons and centrality measures, shows promise in identifying and ranking drugs. Since this methodology only uses the structural information of the signaling pathways and does not need initial conditions and dynamical rates, it can be utilized in larger networks.

Competition for Cooperation: variability, benefits and heritability of relational wealth in hunter-gatherers

Many defining human characteristics including theory of mind, culture and language relate to our sociality, and facilitate the formation and maintenance of cooperative relationships. Therefore, deciphering the context in which our sociality evolved is invaluable in understanding what makes us unique as a species. Much work has emphasised group-level competition, such as warfare, in moulding human cooperation and sociality. However, competition and cooperation also occur within groups; and inter-individual differences in sociality have reported fitness implications in numerous non-human taxa. Here we investigate whether differential access to cooperation (relational wealth) is likely to lead to variation in fitness at the individual level among BaYaka hunter-gatherers. Using economic gift games we find that relational wealth: a) displays individual-level variation; b) provides advantages in buffering food risk, and is positively associated with body mass index (BMI) and female fertility; c) is partially heritable. These results highlight that individual-level processes may have been fundamental in the extension of human cooperation beyond small units of related individuals, and in shaping our sociality. Additionally, the findings offer insight in to trends related to human sociality found from research in other fields such as psychology and epidemiology.

Nonequilibrium critical scaling from quantum thermodynamics

The emerging field of quantum thermodynamics is contributing important results and insights into archetypal many-body problems, including quantum phase transitions. Still, the question whether out-of-equilibrium quantities, such as fluctuations of work, exhibit critical scaling after a sudden quench in a closed system has remained elusive. Here, we take a novel approach to the problem by studying a quench across an impurity quantum critical point. By performing density matrix renormalization group computations on the two-impurity Kondo model, we are able to establish that the irreversible work produced in a quench exhibits finite-size scaling at quantum criticality. This scaling faithfully predicts the equilibrium critical exponents for the crossover length and the order parameter of the model, and, moreover, implies a new exponent for the rescaled irreversible work. By connecting the irreversible work to the two-impurity spin correlation function, our findings can be tested experimentally.