A study of the time complexity of an Elitist Genetic Algorithm used for associating optical observations of MEO and GEO Space Debris

Currently several thousands of objects are being tracked in the MEO and GEO regions through optical means. The problem faced in this framework is that of Multiple Target Tracking (MTT). In this context both the correct associations among the observations, and the orbits of the objects have to be determined. The complexity of the MTT problem is defined by its dimension S. Where S stands for the number of ’fences’ used in the problem, each fence consists of a set of observations that all originate from dierent targets. For a dimension of S ˃ the MTT problem becomes NP-hard. As of now no algorithm exists that can solve an NP-hard problem in an optimal manner within a reasonable (polynomial) computation time. However, there are algorithms that can approximate the solution with a realistic computational e ort. To this end an Elitist Genetic Algorithm is implemented to approximately solve the S ˃ MTT problem in an e cient manner. Its complexity is studied and it is found that an approximate solution can be obtained in a polynomial time. With the advent of improved sensors and a heightened interest in the problem of space debris, it is expected that the number of tracked objects will grow by an order of magnitude in the near future. This research aims to provide a method that can treat the correlation and orbit determination problems simultaneously, and is able to e ciently process large data sets with minimal manual intervention.

Single-dose piracetam effects on global complexity measures of human spontaneous multichannel EEG

Global complexity of 47-channel resting electroencephalogram (EEG) of healthy young volunteers was studied after intake of a single dose of a nootropic drug (piracetam, Nootropil® UCB Pharma) in 12 healthy volunteers. Four treatment levels were used: 2.4, 4.8, 9.6 g piracetam and placebo. Brain electric activity was assessed through Global Dimensional Complexity and Global Omega-Complexity as quantitative measures of the complexity of the trajectory of multichannel EEG in state space. After oral ingestion (1–1.5 h), both measures showed significant decreases from placebo to 2.4 g piracetam. In addition, Global Dimensional Complexity showed a significant return to placebo values at 9.6 g piracetam. The results indicate that a single dose of piracetam dose-dependently affects the spontaneous EEG in normal volunteers, showing effects at the lowest treatment level. The decreased EEG complexity is interpreted as increased cooperativity of brain functional processes.

Brain electric correlates of strong belief in paranormal phenomena: intracerebral EEG source and regional Omega complexity analyses

The neurocognitive processes underlying the formation and maintenance of paranormal beliefs are important for understanding schizotypal ideation. Behavioral studies indicated that both schizotypal and paranormal ideation are based on an overreliance on the right hemisphere, whose coarse rather than focussed semantic processing may favor the emergence of 'loose' and 'uncommon' associations. To elucidate the electrophysiological basis of these behavioral observations, 35-channel resting EEG was recorded in pre-screened female strong believers and disbelievers during resting baseline. EEG data were subjected to FFT-Dipole-Approximation analysis, a reference-free frequency-domain dipole source modeling, and Regional (hemispheric) Omega Complexity analysis, a linear approach estimating the complexity of the trajectories of momentary EEG map series in state space. Compared to disbelievers, believers showed: more right-located sources of the beta2 band (18.5-21 Hz, excitatory activity); reduced interhemispheric differences in Omega complexity values; higher scores on the Magical Ideation scale; more general negative affect; and more hypnagogic-like reveries after a 4-min eyes-closed resting period. Thus, subjects differing in their declared paranormal belief displayed different active, cerebral neural populations during resting, task-free conditions. As hypothesized, believers showed relatively higher right hemispheric activation and reduced hemispheric asymmetry of functional complexity. These markers may constitute the neurophysiological basis for paranormal and schizotypal ideation.

Chewing-gum flavor affects measures of global complexity of multichannel EEG

Global complexity of spontaneous brain electric activity was studied before and after chewing gum without flavor and with 2 different flavors. One-minute, 19-channel, eyes-closed electroencephalograms (EEG) were recorded from 20 healthy males before and after using 3 types of chewing gum: regular gum containing sugar and aromatic additives, gum containing 200 mg theanine (a constituent of Japanese green tea), and gum base (no sugar, no aromatic additives); each was chewed for 5 min in randomized sequence. Brain electric activity was assessed through Global Omega (Ω)-Complexity and Global Dimensional Complexity (GDC), quantitative measures of complexity of the trajectory of EEG map series in state space; their differences from pre-chewing data were compared across gum-chewing conditions. Friedman Anova (p < 0.043) showed that effects on Ω-Complexity differed significantly between conditions and differences were maximal between gum base and theanine gum. No differences were found using GDC. Global Omega-Complexity appears to be a sensitive measure for subtle, central effects of chewing gum with and without flavor.

MQN-Mapplet: Visualization of Chemical Space with Interactive Maps of DrugBank, ChEMBL, PubChem, GDB-11, and GDB-13

The MQN-mapplet is a Java application giving access to the structure of small molecules in large databases via color-coded maps of their chemical space. These maps are projections from a 42-dimensional property space defined by 42 integer value descriptors called molecular quantum numbers (MQN), which count different categories of atoms, bonds, polar groups, and topological features and categorize molecules by size, rigidity, and polarity. Despite its simplicity, MQN-space is relevant to biological activities. The MQN-mapplet allows localization of any molecule on the color-coded images, visualization of the molecules, and identification of analogs as neighbors on the MQN-map or in the original 42-dimensional MQN-space. No query molecule is necessary to start the exploration, which may be particularly attractive for nonchemists. To our knowledge, this type of interactive exploration tool is unprecedented for very large databases such as PubChem and GDB-13 (almost one billion molecules). The application is freely available for download at www.gdb.unibe.ch.

Quantum Simulation of Non-Abelian Lattice Gauge Theories

We use quantum link models to construct a quantum simulator for U(N) and SU(N) lattice gauge theories. These models replace Wilson’s classical link variables by quantum link operators, reducing the link Hilbert space to a finite number of dimensions. We show how to embody these quantum link models with fermionic matter with ultracold alkaline-earth atoms using optical lattices. Unlike classical simulations, a quantum simulator does not suffer from sign problems and can thus address the corresponding dynamics in real time. Using exact diagonalization results we show that these systems share qualitative features with QCD, including chiral symmetry breaking and we study the expansion of a chirally restored region in space in real time.

The Chemical Space of Flavours

The flavour of foods is determined by the interaction of taste molecules with receptors in the mouth, and fragrances or aroma with receptors in the upper part of the nose. Here, we discuss the properties of taste and fragrance molecules, from the public databases Superscent, Flavornet, SuperSweet and BitterDB, taken collectively as flavours, in the perspective of the chemical space. We survey simple descriptor profiles in comparison with the public collections ChEMBL (bioactive small molecules), ZINC (commercial drug-like molecules) and GDB-13 (all possible organic molecules up to 13 atoms of C, N, O, S, Cl). A global analysis of the chemical space of flavours is also presented based on molecular quantum numbers (MQN) and SMILES fingerprints (SMIfp). While taste molecules span a very broad property range, fragrances occupy a narrow area of the chemical space consisting of generally very small and relatively nonpolar molecules distinct of standard drug molecules. Proximity searching in the chemical space is exemplified as a simple method to facilitate the search for new fragrances.

Applicative theories for logarithmic complexity classes

We present applicative theories of words corresponding to weak, and especially logarithmic, complexity classes. The theories for the logarithmic hierarchy and alternating logarithmic time formalise function algebras with concatenation recursion as main principle. We present two theories for logarithmic space where the first formalises a new two-sorted algebra which is very similar to Cook and Bellantoni's famous two-sorted algebra B for polynomial time [4]. The second theory describes logarithmic space by formalising concatenation- and sharply bounded recursion. All theories contain the predicates WW representing words, and VV representing temporary inaccessible words. They are inspired by Cantini's theories [6] formalising B.

Bufferless Compression of Asynchronously Sampled ECG Signals in Cubic Hermitian Vector Space.

Asynchronous level crossing sampling analog-to-digital converters (ADCs) are known to be more energy efficient and produce fewer samples than their equidistantly sampling counterparts. However, as the required threshold voltage is lowered, the number of samples and, in turn, the data rate and the energy consumed by the overall system increases. In this paper, we present a cubic Hermitian vector-based technique for online compression of asynchronously sampled electrocardiogram signals. The proposed method is computationally efficient data compression. The algorithm has complexity O(n), thus well suited for asynchronous ADCs. Our algorithm requires no data buffering, maintaining the energy advantage of asynchronous ADCs. The proposed method of compression has a compression ratio of up to 90% with achievable percentage root-mean-square difference ratios as a low as 0.97. The algorithm preserves the superior feature-to-feature timing accuracy of asynchronously sampled signals. These advantages are achieved in a computationally efficient manner since algorithm boundary parameters for the signals are extracted a priori.