Estimating Parameters Associated with Monotone Properties

Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann and Henrique Stagni

There has been substantial interest in estimating the value of a graph parameter, i.e., of a real function defined on the set of finite graphs, by sampling a randomly chosen substructure whose size is independent of the size of the input. Graph parameters that may be successfully estimated in this way are said to be testable or estimable, and the sample complexity qz = qz(ε) of an estimable parameter z is the size of the random sample required to ensure that the value of z(G) may be estimated within error ε with probability at least 2/3. In this paper, we study the sample complexity of estimating two graph parameters associated with a monotone graph property, improving previously known results. To obtain our results, we prove that the vertex set of any graph that satisfies a monotone property P may be partitioned equitably into a constant number of classes in such a way that the cluster graph induced by the partition is not far from satisfying a natural weighted graph generalization of P. Properties for which this holds are said to be recoverable, and the study of recoverable properties may be of independent interest

On the Number of Bh-Sets

Domingos Dellamonica, Yoshiharu Kohayakawa, Sang June Lee, Vojtěch Rödl and Wojciech Samotij

A set A of positive integers is a Bh-set if all sums of the form a1 + ··· + ah, with a1,...,ah ∈ A and a1 ··· ah, are distinct. We provide asymptotic bounds for the number of Bh-sets of a given cardinality contained in the interval [n] = {1,...,n}. As a consequence of our results, we address a problem of Cameron and Erd˝os (1990) in the context of Bh-sets.
We also use these results to estimate the maximum size of a Bh-set contained in a typical (random) subset of [n] with a given cardinality.

Diversity improves performance in excitable networks

Leonardo L. Gollo​, Mauro Copelli and James A. Roberts

As few real systems comprise indistinguishable units, diversity is a hallmark of nature. Diversity among interacting units shapes properties of collective behavior such as synchronization and information transmission. However, the benefits of diversity on information processing at the edge of a phase transition, ordinarily assumed to emerge from identical elements, remain largely unexplored. Analyzing a general model of excitable systems with heterogeneous excitability, we find that diversity can greatly enhance optimal performance (by two orders of magnitude) when distinguishing incoming inputs. Heterogeneous systems possess a subset of specialized elements whose capability greatly exceeds that of the nonspecialized elements. We also find that diversity can yield multiple percolation, with performance optimized at tricriticality. Our results are robust in specific and more realistic neuronal systems comprising a combination of excitatory and inhibitory units, and indicate that diversity-induced amplification can be harnessed by neuronal systems for evaluating stimulus intensities.

Nonparametric statistical inference for the context tree of a stationary ergodic process

Sandro Gallo and Florencia Leonardi

We consider the problem of estimating the context tree of a stationary ergodic process with finite alphabet without imposing additional conditions on the process. As a starting point we introduce a Hamming metric in the space of irreducible context trees and we use the properties of the weak topology in the space of ergodic stationary processes to prove that if the Hamming metric is unbounded, there exist no consistent estimators for the context tree. Even in the bounded case we show that there exist no two-sided confidence bounds. However we prove that one-sided inference is possible in this general setting and we construct a consistent estimator that is a lower bound for the context tree of the process with an explicit formula for the coverage probability. We develop an efficient algorithm to compute the lower bound and we apply the method to test a linguistic hypothesis about the context tree of codified written texts in European Portuguese.

Investigation of rat exploratory behavior via evolving artificial neural networks

Ariadne de Andrade Costa and Renato Tinós

Background: Neuroevolution comprises the use of evolutionary computation to define the architecture and/or to train artificial neural networks (ANNs). This strategy has been employed to investigate the behavior of rats in the elevated plus-maze, which is a widely used tool for studying anxiety in mice and rats. New method: Here we propose a neuroevolutionary model, in which both the weights and the architecture of artificial neural networks (our virtual rats) are evolved by a genetic algorithm. Comparison with Existing Methods: This model is an improvement of a previous model that involves the evolution of just the weights of the ANN by the genetic algorithm. In order to compare both models, we analyzed traditional measures of anxiety behavior, like the time spent and the number of entries in both open and closed arms of the maze. Results: When compared to real rat data, our findings suggest that the results from the model introduced here are statistically better than those from other models in the literature. Conclusions: In this way, the neuroevolution of architecture is clearly important for the development of the virtual rats. Moreover, this technique allowed the comprehension of the importance of different sensory units and different number of hidden neurons (performing as memory) in the ANNs (virtual rats).

Contrast response functions in the visual wulst of the alert burrowing owl: a single-unit study

Vieira P.G., de Sousa J.P. and Baron J.

The neuronal representation of luminance contrast has not been thoroughly studied in birds. Here we present a detailed quantitative analysis of the contrast response of 120 individual neurons recorded from the visual wulst of awake burrowing owls (Athene cunicularia). Stimuli were sine-wave gratings presented within the cell classical receptive field and optimized in terms of eye preference, direction of drift, and spatiotemporal frequency. As contrast intensity was increased from zero to near 100%, most cells exhibited a monotonic response profile with a compressive, at times saturating, nonlinearity at higher contrasts. However, contrast response functions were found to have a highly variable shape across cells. With the view to capture a systematic trend in the data, we assessed the performance of four plausible models (linear, power, logarithmic, and hyperbolic ratio) using classical goodness-of-fit measures and more rigorous statistical tools for multimodel inferences based on the Akaike information criterion. From this analysis, we conclude that a high degree of model uncertainty is present in our data, meaning that no single descriptor is able on its own to capture the heterogeneous nature of single-unit contrast responses in the wulst. We further show that the generalizability of the hyperbolic ratio model established, for example, in the primary visual cortex of cats and monkeys is not tenable in the owl wulst mainly because most neurons in this area have a much wider dynamic range that starts at low contrast. The challenge for future research will be to understand the functional implications of these findings.

Continuity properties of a factor of Markov chains

Walter A. F. de Carvalho, Sandro Gallo and Nancy L. Garcia

Starting from a Markov chain with a finite or a countable infinite alphabet, we consider the chain obtained when all but one symbol are indistinguishable for the practitioner. We study conditions on the transition matrix of the Markov chain ensuring that the image chain has continuous or discontinuous transition probabilities with respect to the past.

Stochastic Ising model with plastic interactions

Eugene Pechersky, Guillem Via and Anatoly Yambartsev

We propose a new model based on the Ising model with the aim to study synaptic plasticity phenomena in neural networks. It is today well established in biology that the synapses or connections between certain types of neurons are strengthened when the neurons are co-active, a form of the so called synaptic plasticity. Such mechanism is believed to mediate the formation and maintenance of memories. The proposed model describes some features from that phenomenon. Together with the spin-flip dynamics, in our model the coupling constants are also subject to stochastic dynamics, so that they interact with each other. The evolution of the system is described by a continuous-time Markov jump process.

Phase transitions and self-organized criticality in networks of stochastic spiking neurons

Ludmila Brochini, Ariadne de Andrade Costa, Miguel Abadi, Antônio C. Roque, Jorge Stolfi and Osame Kinouchi

Phase transitions and critical behavior are crucial issues both in theoretical and experimental neuroscience. We report analytic and computational results about phase transitions and self-organized criticality (SOC) in networks with general stochastic neurons. The stochastic neuron has a firing probability given by a smooth monotonic function Φ(V) of the membrane potential V, rather than a sharp firing threshold. We find that such networks can operate in several dynamic regimes (phases) depending on the average synaptic weight and the shape of the firing function Φ. In particular, we encounter both continuous and discontinuous phase transitions to absorbing states. At the continuous transition critical boundary, neuronal avalanches occur whose distributions of size and duration are given by power laws, as observed in biological neural networks. We also propose and test a new mechanism to produce SOC: the use of dynamic neuronal gains – a form of short-term plasticity probably located at the axon initial segment (AIS) – instead of depressing synapses at the dendrites (as previously studied in the literature). The new self-organization mechanism produces a slightly supercritical state, that we called SOSC, in accord to some intuitions of Alan Turing.

Motor Coordination Correlates with Academic Achievement and Cognitive Function in Children

Valter R. Fernandes, Michelle L. Scipião Ribeiro, Thais Melo, Paulo de Tarso Maciel-Pinheiro, Thiago T. Guimarães, Narahyana B. Araújo, Sidarta Ribeiro and Andréa C. Deslandes

The relationship between exercise and cognition is an important topic of research that only recently began to unravel. Here, we set out to investigate the relation between motor skills, cognitive function, and school performance in 45 students from 8 to 14 years of age. We used a cross-sectional design to evaluate motor coordination (Touch Test Disc), agility (Shuttle Run Speed—running back and forth), school performance (Academic Achievement Test), the Stroop test, and six sub-tests of the Wechsler Intelligence Scale for Children-IV (WISC-IV). We found, that the Touch Test Disc was the best predictor of school performance (R2 = 0.20). Significant correlations were also observed between motor coordination and several indices of cognitive function, such as the total score of the Academic Achievement Test (AAT; Spearman's rho = 0.536; p ≤ 0.001), as well as two WISC-IV sub-tests: block design (R = −0.438; p = 0.003) and cancelation (rho = −0.471; p = 0.001). All the other cognitive variables pointed in the same direction, and even correlated with agility, but did not reach statistical significance. Altogether, the data indicate that visual motor coordination and visual selective attention, but not agility, may influence academic achievement and cognitive function. The results highlight the importance of investigating the correlation between physical skills and different aspects of cognition.




The Research, Innovation and Dissemination Center for Neuromathematics is hosted by the University of São Paulo and funded by FAPESP (São Paulo Research Foundation).


User login



1010 Matão Street - Cidade Universitária - São Paulo - SP - Brasil. 05508-090. See map.

55 11 3091-1717

General contact email:

Media inquiries email: