Article
Refine
Year of publication
Document Type
- Article (393) (remove)
Language
- English (393) (remove)
Has Fulltext
- yes (393)
Is part of the Bibliography
- no (393)
Keywords
- Heavy Ion Experiments (19)
- Hadron-Hadron Scattering (11)
- Hadron-Hadron scattering (experiments) (10)
- LHC (8)
- Heavy-ion collision (7)
- Collective Flow (4)
- Petri net (4)
- Quark-Gluon Plasma (4)
- ALICE (3)
- ALICE experiment (3)
Institute
- Informatik (393) (remove)
The elliptic flow, v2, of muons from heavy-flavour hadron decays at forward rapidity (2.5<y<4) is measured in Pb–Pb collisions at √sNN=2.76 TeV with the ALICE detector at the LHC. The scalar product, two- and four-particle Q cumulants and Lee–Yang zeros methods are used. The dependence of the v2 of muons from heavy-flavour hadron decays on the collision centrality, in the range 0–40%, and on transverse momentum, pT, is studied in the interval 3<pT<10 GeV/c. A positive v2 is observed with the scalar product and two-particle Q cumulants in semi-central collisions (10–20% and 20–40% centrality classes) for the pT interval from 3 to about 5 GeV/c with a significance larger than 3σ, based on the combination of statistical and systematic uncertainties. The v2 magnitude tends to decrease towards more central collisions and with increasing pT. It becomes compatible with zero in the interval 6<pT<10 GeV/c. The results are compared to models describing the interaction of heavy quarks and open heavy-flavour hadrons with the high-density medium formed in high-energy heavy-ion collisions.
The pseudorapidity (η) and transverse-momentum (pT) distributions of charged particles produced in proton–proton collisions are measured at the centre-of-mass energy √s=13 TeV. The pseudorapidity distribution in |η|<1.8 is reported for inelastic events and for events with at least one charged particle in |η|<1. The pseudorapidity density of charged particles produced in the pseudorapidity region |η|<0.5 is 5.31±0.18 and 6.46±0.19 for the two event classes, respectively. The transverse-momentum distribution of charged particles is measured in the range 0.15<pT<20 GeV/c and |η|<0.8 for events with at least one charged particle in |η|<1. The evolution of the transverse momentum spectra of charged particles is also investigated as a function of event multiplicity. The results are compared with calculations from PYTHIA and EPOS Monte Carlo generators.
We present results of a search for two hypothetical strange dibaryon states, i.e. the H-dibaryon and the possible Λn‾ bound state. The search is performed with the ALICE detector in central (0–10%) Pb–Pb collisions at √sNN=2.76 TeV, by invariant mass analysis in the decay modes Λn‾→d‾π+ and H-dibaryon →Λpπ−. No evidence for these bound states is observed. Upper limits are determined at 99% confidence level for a wide range of lifetimes and for the full range of branching ratios. The results are compared to thermal, coalescence and hybrid UrQMD model expectations, which describe correctly the production of other loosely bound states, like the deuteron and the hypertriton.
Two-particle angular correlations between trigger particles in the forward pseudorapidity range (2.5<|η|<4.0) and associated particles in the central range (|η|<1.0) are measured with the ALICE detector in p-Pb collisions at a nucleon-nucleon centre-of-mass energy of 5.02 TeV. The trigger particles are reconstructed using the muon spectrometer, and the associated particles by the central barrel tracking detectors. In high-multiplicity events, the double-ridge structure, previously discovered in two-particle angular correlations at midrapidity, is found to persist to the pseudorapidity ranges studied in this Letter. The second-order Fourier coefficients for muons in high-multiplicity events are extracted after jet-like correlations from low-multiplicity events have been subtracted. The coefficients are found to have a similar transverse momentum (pT) dependence in p-going (p-Pb) and Pb-going (Pb-p) configurations, with the Pb-going coefficients larger by about 16±6%, rather independent of pT within the uncertainties of the measurement. The data are compared with calculations using the AMPT model, which predicts a different pT and η dependence than observed in the data. The results are sensitive to the parent particle v2 and composition of reconstructed muon tracks, where the contribution from heavy flavour decays are expected to dominate at pT>2 GeV/c.
We present a measurement of inclusive J/ψ production in p-Pb collisions at sNN−−−√ = 5.02 TeV as a function of the centrality of the collision, as estimated from the energy deposited in the Zero Degree Calorimeters. The measurement is performed with the ALICE detector down to zero transverse momentum, pT, in the backward (−4.46<ycms<−2.96) and forward (2.03<ycms<3.53) rapidity intervals in the dimuon decay channel and in the mid-rapidity region (−1.37<ycms<0.43) in the dielectron decay channel. The backward and forward rapidity intervals correspond to the Pb-going and p-going direction, respectively. The pT-differential J/ψ production cross section at backward and forward rapidity is measured for several centrality classes, together with the corresponding average pT and p2T values. The nuclear modification factor, QpPb, is presented as a function of centrality for the three rapidity intervals, and, additionally, at backward and forward rapidity, as a function of pT for several centrality classes. At mid- and forward rapidity, the J/ψ yield is suppressed up to 40% compared to that in pp interactions scaled by the number of binary collisions. The degree of suppression increases towards central p-Pb collisions at forward rapidity, and with decreasing pT of the J/ψ. At backward rapidity, the QpPb is compatible with unity within the total uncertainties, with an increasing trend from peripheral to central p-Pb collisions.
Research in the field of Digital Humanities, also known as Humanities Computing, has seen a steady increase over the past years. Situated at the intersection of computing science and the humanities, present efforts focus on making resources such as texts, images, musical pieces and other semiotic artifacts digitally available, searchable and analysable. To this end, computational tools enabling textual search, visual analytics, data mining, statistics and natural language processing are harnessed to support the humanities researcher. The processing of large data sets with appropriate software opens up novel and fruitful approaches to questions in the traditional humanities. This report summarizes the Dagstuhl seminar 14301 on “Computational Humanities - bridging the gap between Computer Science and Digital Humanities”.
1998 ACM Subject Classification I.2.7 Natural Language Processing, J.5 Arts and Humanities
Data structures and advanced models of computation on big data : report from Dagstuhl seminar 14091
(2014)
This report documents the program and the outcomes of Dagstuhl Seminar 14091 "Data Structures and Advanced Models of Computation on Big Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances.
The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures.
The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
1D-3D hybrid modeling : from multi-compartment models to full resolution models in space and time
(2014)
Investigation of cellular and network dynamics in the brain by means of modeling and simulation has evolved into a highly interdisciplinary field, that uses sophisticated modeling and simulation approaches to understand distinct areas of brain function. Depending on the underlying complexity, these models vary in their level of detail, in order to cope with the attached computational cost. Hence for large network simulations, single neurons are typically reduced to time-dependent signal processors, dismissing the spatial aspect of each cell. For single cell or networks with relatively small numbers of neurons, general purpose simulators allow for space and time-dependent simulations of electrical signal processing, based on the cable equation theory. An emerging field in Computational Neuroscience encompasses a new level of detail by incorporating the full three-dimensional morphology of cells and organelles into three-dimensional, space and time-dependent, simulations. While every approach has its advantages and limitations, such as computational cost, integrated and methods-spanning simulation approaches, depending on the network size could establish new ways to investigate the brain. In this paper we present a hybrid simulation approach, that makes use of reduced 1D-models using e.g., the NEURON simulator—which couples to fully resolved models for simulating cellular and sub-cellular dynamics, including the detailed three-dimensional morphology of neurons and organelles. In order to couple 1D- and 3D-simulations, we present a geometry-, membrane potential- and intracellular concentration mapping framework, with which graph- based morphologies, e.g., in the swc- or hoc-format, are mapped to full surface and volume representations of the neuron and computational data from 1D-simulations can be used as boundary conditions for full 3D simulations and vice versa. Thus, established models and data, based on general purpose 1D-simulators, can be directly coupled to the emerging field of fully resolved, highly detailed 3D-modeling approaches. We present the developed general framework for 1D/3D hybrid modeling and apply it to investigate electrically active neurons and their intracellular spatio-temporal calcium dynamics.
The morphology of presynaptic specializations can vary greatly ranging from classical single-release-site boutons in the central nervous system to boutons of various sizes harboring multiple vesicle release sites. Multi-release-site boutons can be found in several neural contexts, for example at the neuromuscular junction (NMJ) of body wall muscles of Drosophila larvae. These NMJs are built by two motor neurons forming two types of glutamatergic multi-release-site boutons with two typical diameters. However, it is unknown why these distinct nerve terminal configurations are used on the same postsynaptic muscle fiber. To systematically dissect the biophysical properties of these boutons we developed a full three-dimensional model of such boutons, their release sites and transmitter-harboring vesicles and analyzed the local vesicle dynamics of various configurations during stimulation. Here we show that the rate of transmission of a bouton is primarily limited by diffusion-based vesicle movements and that the probability of vesicle release and the size of a bouton affect bouton-performance in distinct temporal domains allowing for an optimal transmission of the neural signals at different time scales. A comparison of our in silico simulations with in vivo recordings of the natural motor pattern of both neurons revealed that the bouton properties resemble a well-tuned cooperation of the parameters release probability and bouton size, enabling a reliable transmission of the prevailing firing-pattern at diffusion-limited boutons. Our findings indicate that the prevailing firing-pattern of a neuron may determine the physiological and morphological parameters required for its synaptic terminals.
Alternative polyadenylation (APA) is a widespread mechanism that contributes to the sophisticated dynamics of gene regulation. Approximately 50% of all protein-coding human genes harbor multiple polyadenylation (PA) sites; their selective and combinatorial use gives rise to transcript variants with differing length of their 3' untranslated region (3'UTR). Shortened variants escape UTR-mediated regulation by microRNAs (miRNAs), especially in cancer, where global 3'UTR shortening accelerates disease progression, dedifferentiation and proliferation. Here we present APADB, a database of vertebrate PA sites determined by 3' end sequencing, using massive analysis of complementary DNA ends. APADB provides (A)PA sites for coding and non-coding transcripts of human, mouse and chicken genes. For human and mouse, several tissue types, including different cancer specimens, are available. APADB records the loss of predicted miRNA binding sites and visualizes next-generation sequencing reads that support each PA site in a genome browser. The database tables can either be browsed according to organism and tissue or alternatively searched for a gene of interest. APADB is the largest database of APA in human, chicken and mouse. The stored information provides experimental evidence for thousands of PA sites and APA events. APADB combines 3' end sequencing data with prediction algorithms of miRNA binding sites, allowing to further improve prediction algorithms. Current databases lack correct information about 3'UTR lengths, especially for chicken, and APADB provides necessary information to close this gap. Database URL: http://tools.genxpro.net/apadb/
Event-by-event fluctuations of the mean transverse momentum of charged particles produced in pp collisions at s√ = 0.9, 2.76 and 7 TeV, and Pb-Pb collisions at sNN−−−−√ = 2.76 TeV are studied as a function of the charged-particle multiplicity using the ALICE detector at the LHC. Dynamical fluctuations indicative of correlated particle emission are observed in all systems. The results in pp collisions show little dependence on collision energy. The Monte Carlo event generators PYTHIA and PHOJET are in qualitative agreement with the data. Peripheral Pb-Pb data exhibit a similar multiplicity dependence as that observed in pp. In central Pb-Pb, the results deviate from this trend, featuring a significant reduction of the fluctuation strength. The results in Pb--Pb are in qualitative agreement with previous measurements in Au-Au at lower collision energies and with expectations from models that incorporate collective phenomena.
Aging of biological systems is controlled by various processes which have a potential impact on gene expression. Here we report a genome-wide transcriptome analysis of the fungal aging model Podospora anserina. Total RNA of three individuals of defined age were pooled and analyzed by SuperSAGE (serial analysis of gene expression). A bioinformatics analysis identified different molecular pathways to be affected during aging. While the abundance of transcripts linked to ribosomes and to the proteasome quality control system were found to decrease during aging, those associated with autophagy increase, suggesting that autophagy may act as a compensatory quality control pathway. Transcript profiles associated with the energy metabolism including mitochondrial functions were identified to fluctuate during aging. Comparison of wild-type transcripts, which are continuously down-regulated during aging, with those down-regulated in the long-lived, copper-uptake mutant grisea, validated the relevance of age-related changes in cellular copper metabolism. Overall, we (i) present a unique age-related data set of a longitudinal study of the experimental aging model P. anserina which represents a reference resource for future investigations in a variety of organisms, (ii) suggest autophagy to be a key quality control pathway that becomes active once other pathways fail, and (iii) present testable predictions for subsequent experimental investigations.
To truly appreciate the myriad of events which relate synaptic function and vesicle dynamics, simulations should be done in a spatially realistic environment. This holds true in particular in order to explain as well the rather astonishing motor patterns which we observed within in vivo recordings which underlie peristaltic contractionsas well as the shape of the EPSPs at different forms of long-term stimulation, presented both here, at a well characterized synapse, the neuromuscular junction (NMJ) of the Drosophila larva (c.f. Figure 1). To this end, we have employed a reductionist approach and generated three dimensional models of single presynaptic boutons at the Drosophila larval NMJ. Vesicle dynamics are described by diffusion-like partial differential equations which are solved numerically on unstructured grids using the uG platform. In our model we varied parameters such as bouton-size, vesicle output probability (Po), stimulation frequency and number of synapses, to observe how altering these parameters effected bouton function. Hence we demonstrate that the morphologic and physiologic specialization maybe a convergent evolutionary adaptation to regulate the trade off between sustained, low output, and short term, high output, synaptic signals. There seems to be a biologically meaningful explanation for the co-existence of the two different bouton types as previously observed at the NMJ (characterized especially by the relation between size and Po), the assigning of two different tasks with respect to short- and long-time behaviour could allow for an optimized interplay of different synapse types. We can present astonishing similar results of experimental and simulation data which could be gained in particular without any data fitting, however based only on biophysical values which could be taken from different experimental results. As a side product, we demonstrate how advanced methods from numerical mathematics could help in future to resolve also other difficult experimental neurobiological issues.
Finding motifs in biological, social, technological, and other types of networks has become a widespread method to gain more knowledge about these networks’ structure and function. However, this task is very computationally demanding, because it is highly associated with the graph isomorphism which is an NP problem (not known to belong to P or NP-complete subsets yet). Accordingly, this research is endeavoring to decrease the need to call NAUTY isomorphism detection method, which is the most time-consuming step in many existing algorithms. The work provides an extremely fast motif detection algorithm called QuateXelero, which has a Quaternary Tree data structure in the heart. The proposed algorithm is based on the well-known ESU (FANMOD) motif detection algorithm. The results of experiments on some standard model networks approve the overal superiority of the proposed algorithm, namely QuateXelero, compared with two of the fastest existing algorithms, G-Tries and Kavosh. QuateXelero is especially fastest in constructing the central data structure of the algorithm from scratch based on the input network.
Functional modules of metabolic networks are essential for understanding the metabolism of an organism as a whole. With the vast amount of experimental data and the construction of complex and large-scale, often genome-wide, models, the computer-aided identification of functional modules becomes more and more important. Since steady states play a key role in biology, many methods have been developed in that context, for example, elementary flux modes, extreme pathways, transition invariants and place invariants. Metabolic networks can be studied also from the point of view of graph theory, and algorithms for graph decomposition have been applied for the identification of functional modules. A prominent and currently intensively discussed field of methods in graph theory addresses the Q-modularity. In this paper, we recall known concepts of module detection based on the steady-state assumption, focusing on transition-invariants (elementary modes) and their computation as minimal solutions of systems of Diophantine equations. We present the Fourier-Motzkin algorithm in detail. Afterwards, we introduce the Q-modularity as an example for a useful non-steady-state method and its application to metabolic networks. To illustrate and discuss the concepts of invariants and Q-modularity, we apply a part of the central carbon metabolism in potato tubers (Solanum tuberosum) as running example. The intention of the paper is to give a compact presentation of known steady-state concepts from a graph-theoretical viewpoint in the context of network decomposition and reduction and to introduce the application of Q-modularity to metabolic Petri net models.
Poster presentation: Twenty Second Annual Computational Neuroscience Meeting: CNS*2013. Paris, France. 13-18 July 2013.
The synaptic cleft is an extracellular domain that is capable of relaying a presynaptically received electrical signal by diffusive neurotransmitters to the postsynaptic membrane. The cleft is trans-synaptically bridged by ring-like shaped clusters of pre- and postsynaptically localized calcium-dependent adhesion proteins of the N-Cadherin type and is possibly the smallest intercircuit in nervous systems [1]. The strength of association between the pre- and postsynaptic membranes can account for synaptic plasticity such as long-term potentiation [2]. Through neuronal activity the intra- and extracellular calcium levels are modulated through calcium exchangers embedded in the pre- and postsynaptic membrane. Variations of the concentration of cleft calcium induces changes in the N-Cadherin-zipper, that in synaptic resting states is rigid and tightly connects the pre- and postsynaptic domain. During synaptic activity calcium concentrations are hypothesized to drop below critical thresholds which leads to loosening of the N-Cadherin connections and subsequently "unzips" the Cadherin-mediated connection. These processes may result in changes in synaptic strength [2]. In order to investigate the calcium-mediated N-Cadherin dynamics at the synaptic cleft, we developed a three-dimensional model including the cleft morphology and all prominent calcium exchangers and corresponding density distributions [3-6]. The necessity for a fully three-dimensional model becomes apparent, when investigating the effects of the spatial architecture of the synapse [7], [8]. Our data show, that the localization of calcium channels with respect to the N-Cadherin ring has substantial effects on the time-scales on which the Cadherin-zipper switches between states, ranging from seconds to minutes. This will have significant effects on synaptic signaling. Furthermore we see, that high-frequency action potential firing can only be relayed to the Calcium/N-Cadherin-system at a synapse under precise spatial synaptic reorganization.
Long-range angular correlations on the near and away side in p–Pb collisions at √sNN=5.02 TeV
(2013)
Angular correlations between charged trigger and associated particles are measured by the ALICE detector in p–Pb collisions at a nucleon–nucleon centre-of-mass energy of 5.02 TeV for transverse momentum ranges within 0.5<pT,assoc<pT,trig<4 GeV/c. The correlations are measured over two units of pseudorapidity and full azimuthal angle in different intervals of event multiplicity, and expressed as associated yield per trigger particle. Two long-range ridge-like structures, one on the near side and one on the away side, are observed when the per-trigger yield obtained in low-multiplicity events is subtracted from the one in high-multiplicity events. The excess on the near-side is qualitatively similar to that recently reported by the CMS Collaboration, while the excess on the away-side is reported for the first time. The two-ridge structure projected onto azimuthal angle is quantified with the second and third Fourier coefficients as well as by near-side and away-side yields and widths. The yields on the near side and on the away side are equal within the uncertainties for all studied event multiplicity and pT bins, and the widths show no significant evolution with event multiplicity or pT. These findings suggest that the near-side ridge is accompanied by an essentially identical away-side ridge.
The elliptic, v2, triangular, v3, and quadrangular, v4, azimuthal anisotropic flow coefficients are measured for unidentified charged particles, pions, and (anti-)protons in Pb–Pb collisions at √sNN=2.76 TeV with the ALICE detector at the Large Hadron Collider. Results obtained with the event plane and four-particle cumulant methods are reported for the pseudo-rapidity range |η|<0.8 at different collision centralities and as a function of transverse momentum, pT, out to pT=20 GeV/c. The observed non-zero elliptic and triangular flow depends only weakly on transverse momentum for pT>8 GeV/c. The small pT dependence of the difference between elliptic flow results obtained from the event plane and four-particle cumulant methods suggests a common origin of flow fluctuations up to pT=8 GeV/c. The magnitude of the (anti-)proton elliptic and triangular flow is larger than that of pions out to at least pT=8 GeV/c indicating that the particle type dependence persists out to high pT.
The production cross section of electrons from semileptonic decays of beauty hadrons was measured at mid-rapidity (|y|<0.8) in the transverse momentum range 1<pT<8 GeV/c with the ALICE experiment at the CERN LHC in pp collisions at a center of mass energy √s=7 TeV using an integrated luminosity of 2.2 nb−1. Electrons from beauty hadron decays were selected based on the displacement of the decay vertex from the collision vertex. A perturbative QCD calculation agrees with the measurement within uncertainties. The data were extrapolated to the full phase space to determine the total cross section for the production of beauty quark–antiquark pairs.
The inclusive transverse momentum (pT) distributions of primary charged particles are measured in the pseudo-rapidity range |η|<0.8 as a function of event centrality in Pb–Pb collisions at √sNN=2.76 TeV with ALICE at the LHC. The data are presented in the pT range 0.15<pT<50 GeV/c for nine centrality intervals from 70–80% to 0–5%. The results in Pb–Pb are presented in terms of the nuclear modification factor RAA using a pp reference spectrum measured at the same collision energy. We observe that the suppression of high-pT particles strongly depends on event centrality. The yield is most suppressed in central collisions (0–5%) with RAA≈0.13 at pT=6–7 GeV/c. Above pT=7 GeV/c, there is a significant rise in the nuclear modification factor, which reaches RAA≈0.4 for pT>30 GeV/c. In peripheral collisions (70–80%), only moderate suppression (RAA=0.6–0.7) and a weak pT dependence is observed. The measured nuclear modification factors are compared to other measurements and model calculations.
We introduce tree-width for first order formulae φ, fotw(φ). We show that computing fotw is fixed-parameter tractable with parameter fotw. Moreover, we show that on classes of formulae of bounded fotw, model checking is fixed parameter tractable, with parameter the length of the formula. This is done by translating a formula φ with fotw(φ)<k into a formula of the k-variable fragment Lk of first order logic. For fixed k, the question whether a given first order formula is equivalent to an Lk formula is undecidable. In contrast, the classes of first order formulae with bounded fotw are fragments of first order logic for which the equivalence is decidable. Our notion of tree-width generalises tree-width of conjunctive queries to arbitrary formulae of first order logic by taking into account the quantifier interaction in a formula. Moreover, it is more powerful than the notion of elimination-width of quantified constraint formulae, defined by Chen and Dalmau (CSL 2005): for quantified constraint formulae, both bounded elimination-width and bounded fotw allow for model checking in polynomial time. We prove that fotw of a quantified constraint formula φ is bounded by the elimination-width of φ, and we exhibit a class of quantified constraint formulae with bounded fotw, that has unbounded elimination-width. A similar comparison holds for strict tree-width of non-recursive stratified datalog as defined by Flum, Frick, and Grohe (JACM 49, 2002). Finally, we show that fotw has a characterization in terms of a cops and robbers game without monotonicity cost.
The pT-differential inclusive production cross section of the prompt charm-strange meson Ds+ in the rapidity range |y|<0.5 was measured in proton–proton collisions at s=7 TeV at the LHC using the ALICE detector. The analysis was performed on a data sample of 2.98×108 events collected with a minimum-bias trigger. The corresponding integrated luminosity is Lint=4.8 nb−1. Reconstructing the decay Ds+→ϕπ+, with ϕ→K−K+, and its charge conjugate, about 480 Ds± mesons were counted, after selection cuts, in the transverse momentum range 2<pT<12 GeV/c. The results are compared with predictions from models based on perturbative QCD. The ratios of the cross sections of four D meson species (namely D0, D+, D⁎+ and Ds+) were determined both as a function of pT and integrated over pT after extrapolating to full pT range, together with the strangeness suppression factor in charm fragmentation. The obtained values are found to be compatible within uncertainties with those measured by other experiments in e+e−, ep and pp interactions at various centre-of-mass energies.
he first measurements of the invariant differential cross sections of inclusive π0 and η meson production at mid-rapidity in proton–proton collisions at s=0.9 TeV and s=7 TeV are reported. The π0 measurement covers the ranges 0.4<pT<7 GeV/c and 0.3<pT<25 GeV/c for these two energies, respectively. The production of η mesons was measured at s=√7 TeV in the range 0.4<pT<15 GeV/c. Next-to-Leading Order perturbative QCD calculations, which are consistent with the π0 spectrum at s=0.9 TeV, overestimate those of π0 and η mesons at s=√7 TeV, but agree with the measured η/π0 ratio at s=√7 TeV.
The ALICE Collaboration has measured inclusive J/ψ production in pp collisions at a center-of-mass energy √s=2.76 TeV at the LHC. The results presented in this Letter refer to the rapidity ranges |y|<0.9 and 2.5<y<4 and have been obtained by measuring the electron and muon pair decay channels, respectively. The integrated luminosities for the two channels are Linte=1.1 nb−1 and Lintμ=19.9 nb−1, and the corresponding signal statistics are NJ/ψe+e−=59±14 and NJ/ψμ+μ−=1364±53. We present dσJ/ψ/dy for the two rapidity regions under study and, for the forward-y range, d2σJ/ψ/dydpt in the transverse momentum domain 0<pt<8 GeV/c. The results are compared with previously published results at s=7 TeV and with theoretical calculations.
The ALICE experiment has measured low-mass dimuon production in pp collisions at √s=7 TeV in the dimuon rapidity region 2.5<y<4. The observed dimuon mass spectrum is described as a superposition of resonance decays (η,ρ,ω,η′,ϕ) into muons and semi-leptonic decays of charmed mesons. The measured production cross sections for ω and ϕ are σω(1<pt<5 GeV/c,2.5<y<4)=5.28±0.54(stat)±0.49(syst) mb and σϕ(1<pt<5 GeV/c,2.5<y<4)=0.940±0.084(stat)±0.076(syst) mb. The differential cross sections d2σ/dydpt are extracted as a function of pt for ω and ϕ. The ratio between the ρ and ω cross section is obtained. Results for the ϕ are compared with other measurements at the same energy and with predictions by models.
Identical neutral kaon pair correlations are measured in √s=7 TeV pp collisions in the ALICE experiment. One-dimensional Ks0Ks0 correlation functions in terms of the invariant momentum difference of kaon pairs are formed in two multiplicity and two transverse momentum ranges. The femtoscopic parameters for the radius and correlation strength of the kaon source are extracted. The fit includes quantum statistics and final-state interactions of the a0/f0 resonance. Ks0Ks0 correlations show an increase in radius for increasing multiplicity and a slight decrease in radius for increasing transverse mass, mT, as seen in ππ correlations in pp collisions and in heavy-ion collisions. Transverse mass scaling is observed between the Ks0Ks0 and ππ radii. Also, the first observation is made of the decay of the f2′(1525) meson into the Ks0Ks0 channel in pp collisions.
Heavy flavour decay muon production at forward rapidity in proton–proton collisions at √s=7 TeV
(2012)
The production of muons from heavy flavour decays is measured at forward rapidity in proton–proton collisions at √s=7 TeV collected with the ALICE experiment at the LHC. The analysis is carried out on a data sample corresponding to an integrated luminosity Lint=16.5 nb−1. The transverse momentum and rapidity differential production cross sections of muons from heavy flavour decays are measured in the rapidity range 2.5<y<4, over the transverse momentum range 2<pt<12 GeV/c. The results are compared to predictions based on perturbative QCD calculations.
Harmonic decomposition of two particle angular correlations in Pb–Pb collisions at √sNN=2.76 TeV
(2012)
Angular correlations between unidentified charged trigger (t) and associated (a) particles are measured by the ALICE experiment in Pb–Pb collisions at √sNN=2.76 TeV for transverse momenta 0.25<pTt,a<15 GeV/c, where pTt>pTa. The shapes of the pair correlation distributions are studied in a variety of collision centrality classes between 0 and 50% of the total hadronic cross section for particles in the pseudorapidity interval |η|<1.0. Distributions in relative azimuth Δϕ≡ϕt−ϕa are analyzed for |Δη|≡|ηt−ηa|>0.8, and are referred to as “long-range correlations”. Fourier components VnΔ≡〈cos(nΔϕ)〉 are extracted from the long-range azimuthal correlation functions. If particle pairs are correlated to one another through their individual correlation to a common symmetry plane, then the pair anisotropy VnΔ(pTt,pTa) is fully described in terms of single-particle anisotropies vn(pT) as VnΔ(pTt,pTa)=vn(pTt)vn(pTa). This expectation is tested for 1⩽n⩽5 by applying a global fit of all VnΔ(pTt,pTa) to obtain the best values vn{GF}(pT). It is found that for 2⩽n⩽5, the fit agrees well with data up to pTa∼3–4 GeV/c, with a trend of increasing deviation as pTt and pTa are increased or as collisions become more peripheral. This suggests that no pair correlation harmonic can be described over the full 0.25<pT<15 GeV/c range using a single vn(pT) curve; such a description is however approximately possible for 2⩽n⩽5 when pTa<4 GeV/c. For the n=1 harmonic, however, a single v1(pT) curve is not obtained even within the reduced range pTa<4 GeV/c.
The ALICE Collaboration reports the measurement of the relative J/ψ yield as a function of charged particle pseudorapidity density dNch/dη in pp collisions at √s=7 TeV at the LHC. J/ψ particles are detected for pt>0, in the rapidity interval |y|<0.9 via decay into e+e−, and in the interval 2.5<y<4.0 via decay into μ+μ− pairs. An approximately linear increase of the J/ψ yields normalized to their event average (dNJ/ψ/dy)/〈dNJ/ψ/dy〉 with (dNch/dη)/〈dNch/dη〉 is observed in both rapidity ranges, where dNch/dη is measured within |η|<1 and pt>0. In the highest multiplicity interval with 〈dNch/dη(bin)〉=24.1, corresponding to four times the minimum bias multiplicity density, an enhancement relative to the minimum bias J/ψ yield by a factor of about 5 at 2.5<y<4 (8 at |y|<0.9) is observed.
A measurement of the multi-strange Ξ− and Ω− baryons and their antiparticles by the ALICE experiment at the CERN Large Hadron Collider (LHC) is presented for inelastic proton–proton collisions at a centre-of-mass energy of 7 TeV. The transverse momentum (pT) distributions were studied at mid-rapidity (|y|<0.5) in the range of 0.6<pT<8.5 GeV/c for Ξ− and Ξ¯+ baryons, and in the range of 0.8<pT<5 GeV/c for Ω− and Ω¯+. Baryons and antibaryons were measured as separate particles and we find that the baryon to antibaryon ratio of both particle species is consistent with unity over the entire range of the measurement. The statistical precision of the current data has allowed us to measure a difference between the mean pT of Ξ− (Ξ¯+) and Ω− (Ω¯+). Particle yields, mean pT, and the spectra in the intermediate pT range are not well described by the PYTHIA Perugia 2011 tune Monte Carlo event generator, which has been tuned to reproduce the early LHC data. The discrepancy is largest for Ω− (Ω¯+). This PYTHIA tune approaches the pT spectra of Ξ− and Ξ¯+ baryons below pT<0.85 GeV/c and describes the Ξ− and Ξ¯+ spectra above pT>6.0 GeV/c. We also illustrate the difference between the experimental data and model by comparing the corresponding ratios of (Ω−+Ω¯+)/(Ξ−+Ξ¯+) as a function of transverse mass.
The ALICE Collaboration has made the first measurement at the LHC of J/ψ photoproduction in ultra-peripheral Pb–Pb collisions at sNN=2.76 TeV. The J/ψ is identified via its dimuon decay in the forward rapidity region with the muon spectrometer for events where the hadronic activity is required to be minimal. The analysis is based on an event sample corresponding to an integrated luminosity of about 55 μb−1. The cross section for coherent J/ψ production in the rapidity interval −3.6<y<−2.6 is measured to be dσJ/ψcoh/dy=1.00±0.18(stat)−0.26+0.24(syst) mb. The result is compared to theoretical models for coherent J/ψ production and found to be in good agreement with those models which include nuclear gluon shadowing.
Poster presentation from Twentieth Annual Computational Neuroscience Meeting: CNS*2011 Stockholm, Sweden. 23-28 July 2011. To truly appreciate the myriad of events which relate synaptic function and vesicle dynamics, simulations should be done in a spatially realistic environment. This holds true in particular in order to explain the rather astonishing motor patterns presented here which we observed within in vivo recordings which underlie peristaltic contractions at a well characterized synapse, the neuromuscular junction (NMJ) of the Drosophila larva. To this end, we have employed a reductionist approach and generated three dimensional models of single presynaptic boutons at the Drosophila larval NMJ. Vesicle dynamics are described by diffusion-like partial differential equations which are solved numerically on unstructured grids using the uG platform. In our model we varied parameters such as bouton-size, vesicle output probability (Po), stimulation frequency and number of synapses, to observe how altering these parameters effected bouton function. Hence we demonstrate that the morphologic and physiologic specialization maybe a convergent evolutionary adaptation to regulate the trade off between sustained, low output, and short term, high output, synaptic signals. There seems to be a biologically meaningful explanation for the co-existence of the two different bouton types as previously observed at the NMJ (characterized especially by the relation between size and Po),the assigning of two different tasks with respect to short- and long-time behaviour could allow for an optimized interplay of different synapse types. As a side product, we demonstrate how advanced methods from numerical mathematics could help in future to resolve also other difficult experimental neurobiological issues.
This is a short summary of a recent survey [FR03] focusing on the observed evidence, that Internet connectivity is positively correlated with spread of democracy at high levels of significance. The results of multivariate correlation analysis and probabilities regression estimate models are based on the combined analysis of mid - 1991’s, to 2001 data series of the Eurostat’s and US Census Bureau, the World Bank, and OECD’s statistical data service which track the growth of information technology and rating of freedom and democracy worldwide.
This article shows that there exist two particular linear orders such that first-order logic with these two linear orders has the same expressive power as first-order logic with the Bit-predicate FO(Bit). As a corollary we obtain that there also exists a built-in permutation such that first-order logic with a linear order and this permutation is as expressive as FO(Bit).
Event-related potentials (ERPs) are widely used in basic neuroscience and in clinical diagnostic procedures. In contrast, neurophysiological insights from ERPs have been limited, as several different mechanisms lead to ERPs. Apart from stereotypically repeated responses (additive evoked responses), these mechanisms are asymmetric amplitude modulations and phase-resetting of ongoing oscillatory activity. Therefore, a method is needed that differentiates between these mechanisms and moreover quantifies the stability of a response. We propose a constrained subspace independent component analysis that exploits the multivariate information present in the all-to-all relationship of recordings over trials. Our method identifies additive evoked activity and quantifies its stability over trials. We evaluate identification performance for biologically plausible simulation data and two neurophysiological test cases: Local field potential (LFP) recordings from a visuo-motor-integration task in the awake behaving macaque and magnetoencephalography (MEG) recordings of steady-state visual evoked fields (SSVEFs). In the LFPs we find additive evoked response contributions in visual areas V2/4 but not in primary motor cortex A4, although visually triggered ERPs were also observed in area A4. MEG-SSVEFs were mainly created by additive evoked response contributions. Our results demonstrate that the identification of additive evoked response contributions is possible both in invasive and in non-invasive electrophysiological recordings.
Rapidity and transverse momentum dependence of inclusive J/ψ production in pp collisions at √s=7 TeV
(2011)
The ALICE experiment at the LHC has studied inclusive J/ψ production at central and forward rapidities in pp collisions at √s=7 TeV. In this Letter, we report on the first results obtained detecting the J/ψ through the dilepton decay into e+e− and μ+μ− pairs in the rapidity ranges |y|<0.9 and 2.5<y<4, respectively, and with acceptance down to zero pT. In the dielectron channel the analysis was carried out on a data sample corresponding to an integrated luminosity Lint=5.6 nb−1 and the number of signal events is NJ/ψ=352±32(stat.)±28(syst.); the corresponding figures in the dimuon channel are Lint=15.6 nb−1 and NJ/ψ=1924±77(stat.)±144(syst.). The measured production cross sections are σJ/ψ(|y|<0.9)=10.7±1.0(stat.)±1.6(syst.)−2.3+1.6(syst.pol.)μb and σJ/ψ(2.5<y<4)=6.31±0.25(stat.)±0.76(syst.)−1.96+0.95(syst.pol.)μb. The differential cross sections, in transverse momentum and rapidity, of the J/ψ were also measured.
Effect sizes in experimental pain produced by gender, genetic variants and sensitization procedures
(2011)
Background: Various effects on pain have been reported with respect to their statistical significance, but a standardized measure of effect size has been rarely added. Such a measure would ease comparison of the magnitude of the effects across studies, for example the effect of gender on heat pain with the effect of a genetic variant on pressure pain. Methodology/Principal Findings: Effect sizes on pain thresholds to stimuli consisting of heat, cold, blunt pressure, punctuate pressure and electrical current, administered to 125 subjects, were analyzed for 29 common variants in eight human genes reportedly modulating pain, gender and sensitization procedures using capsaicin or menthol. The genotype explained 0–5.9% of the total interindividual variance in pain thresholds to various stimuli and produced mainly small effects (Cohen's d 0–1.8). The largest effect had the TRPA1 rs13255063T/rs11988795G haplotype explaining >5% of the variance in electrical pain thresholds and conferring lower pain sensitivity to homozygous carriers. Gender produced larger effect sizes than most variant alleles (1–14.8% explained variance, Cohen's d 0.2–0.8), with higher pain sensitivity in women than in men. Sensitization by capsaicin or menthol explained up to 63% of the total variance (4.7–62.8%) and produced largest effects according to Cohen's d (0.4–2.6), especially heat sensitization by capsaicin (Cohen's d = 2.6). Conclusions: Sensitization, gender and genetic variants produce effects on pain in the mentioned order of effect sizes. The present report may provide a basis for comparative discussions of factors influencing pain.
In dyadic communication, both interlocutors adapt to each other linguistically, that is, they align interpersonally. In this article, we develop a framework for modeling interpersonal alignment in terms of the structural similarity of the interlocutors’ dialog lexica. This is done by means of so-called two-layer time-aligned network series, that is, a time-adjusted graph model. The graph model is partitioned into two layers, so that the interlocutors’ lexica are captured as subgraphs of an encompassing dialog graph. Each constituent network of the series is updated utterance-wise. Thus, both the inherent bipartition of dyadic conversations and their gradual development are modeled. The notion of alignment is then operationalized within a quantitative model of structure formation based on the mutual information of the subgraphs that represent the interlocutor’s dialog lexica. By adapting and further developing several models of complex network theory, we show that dialog lexica evolve as a novel class of graphs that have not been considered before in the area of complex (linguistic) networks. Additionally, we show that our framework allows for classifying dialogs according to their alignment status. To the best of our knowledge, this is the first approach to measuring alignment in communication that explores the similarities of graph-like cognitive representations. Keywords: alignment in communication; structural coupling; linguistic networks; graph distance measures; mutual information of graphs; quantitative network analysis
The first measurement of two-pion Bose–Einstein correlations in central Pb–Pb collisions at √sNN=2.76 TeV at the Large Hadron Collider is presented. We observe a growing trend with energy now not only for the longitudinal and the outward but also for the sideward pion source radius. The pion homogeneity volume and the decoupling time are significantly larger than those measured at RHIC.
Inclusive transverse momentum spectra of primary charged particles in Pb–Pb collisions at √sNN=2.76 TeV have been measured by the ALICE Collaboration at the LHC. The data are presented for central and peripheral collisions, corresponding to 0–5% and 70–80% of the hadronic Pb–Pb cross section. The measured charged particle spectra in |η|<0.8 and 0.3<pT<20 GeV/c are compared to the expectation in pp collisions at the same sNN, scaled by the number of underlying nucleon–nucleon collisions. The comparison is expressed in terms of the nuclear modification factor RAA. The result indicates only weak medium effects (RAA≈0.7) in peripheral collisions. In central collisions, RAA reaches a minimum of about 0.14 at pT=6–7 GeV/c and increases significantly at larger pT. The measured suppression of high-pT particles is stronger than that observed at lower collision energies, indicating that a very dense medium is formed in central Pb–Pb collisions at the LHC.
The inclusive charged particle transverse momentum distribution is measured in proton–proton collisions at s=900 GeV at the LHC using the ALICE detector. The measurement is performed in the central pseudorapidity region (|η|<0.8) over the transverse momentum range 0.15<pT<10 GeV/c. The correlation between transverse momentum and particle multiplicity is also studied. Results are presented for inelastic (INEL) and non-single-diffractive (NSD) events. The average transverse momentum for |η|<0.8 is 〈pT〉INEL=0.483±0.001 (stat.)±0.007 (syst.) GeV/c and 〈pT〉NSD=0.489±0.001 (stat.)±0.007 (syst.) GeV/c, respectively. The data exhibit a slightly larger 〈pT〉 than measurements in wider pseudorapidity intervals. The results are compared to simulations with the Monte Carlo event generators PYTHIA and PHOJET.
Poster presentation: An important challenge in neuroscience is understanding how networks of neurons go about processing information. Synapses are thought to play an essential role in cellular information processing however quantitative and mathematical models of the underlying physiologic processes that occur at synaptic active zones are lacking. We are generating mathematical models of synaptic vesicle dynamics at a well-characterized model synapse, the Drosophila larval neuromuscular junction. This synapse's simplicity, accessibility to various electrophysiological recording and imaging techniques, and the genetic malleability intrinsic to Drosophila system make it ideal for computational and mathematical studies. We have employed a reductionist approach and started by modeling single presynaptic boutons. Synaptic vesicles can be divided into different pools; however, a quantitative understanding of their dynamics at the Drosophila neuromuscular junction is lacking [4]. We performed biologically realistic simulations of high and low release probability boutons [3] using partial differential equations (PDE) taking into account not only the evolution in time but also the spatial structure in two dimensions (the extension to three dimensions will be implemented soon). PDEs are solved using UG, a program library for the calculation of multi-dimensional PDEs solved using a finite volume approach and implicit time stepping methods leading to extended linear equation systems be solvedwith multi-grid methods [3,4]. Numerical calculations are done on multi-processor computers for fast calculations using different parameters in order to asses the biological feasibility of different models. In preliminary simulations, we modeled vesicle dynamics as a diffusion process describing exocytosis as Neumann streams at synaptic active zones. The initial results obtained with these models are consistent with experimental data. However, this should be regarded as a work in progress. Further refinements will be implemented, including simulations using morphologically realistic geometries which were generated from confocal scans of the neuromuscular junction using NeuRA (a Neuron Reconstruction Algorithm). Other parameters such as glutamate diffusion and reuptake dynamics, as well as postsynaptic receptor kinetics will be incorporated as well.
Poster presentation: Introduction The ability of neurons to emit different firing patterns is considered relevant for neuronal information processing. In dopaminergic neurons, prominent patterns include highly regular pacemakers with separate spikes and stereotyped intervals, processes with repetitive bursts and partial regularity, and irregular spike trains with nonstationary properties. In order to model and quantify these processes and the variability of their patterns with respect to pharmacological and cellular properties, we aim to describe the two dimensions of burstiness and regularity in a single model framework. Methods We present a stochastic spike train model in which the degree of burstiness and the regularity of the oscillation are described independently and with two simple parameters. In this model, a background oscillation with independent and normally distributed intervals gives rise to Poissonian spike packets with a Gaussian firing intensity. The variability of inter-burst intervals and the average number of spikes in each burst indicate regularity and burstiness, respectively. These parameters can be estimated by fitting the model to the autocorrelograms. This allows to assign every spike train a position in the two-dimensional space described by regularity and burstiness and thus, to investigate the dependence of the firing patterns on different experimental conditions. Finally, burst detection in single spike trains is possible within the model because the parameter estimates determine the appropriate bandwidth that should be used for burst identification. Results and Discussion We applied the model to a sample data set obtained from dopaminergic substantia nigra and ventral tegmental area neurons recorded extracellularly in vivo and studied differences between the firing activity of dopaminergic neurons in wildtype and K-ATP channel knock-out mice. The model is able to represent a variety of discharge patterns and to describe changes induced pharmacologically. It provides a simple and objective classification scheme for the observed spike trains into pacemaker, irregular and bursty processes. In addition to the simple classification, changes in the parameters can be studied quantitatively, also including the properties related to bursting behavior. Interestingly, the proposed algorithm for burst detection may be applicable also to spike trains with nonstationary firing rates if the remaining parameters are unaffected. Thus, the proposed model and its burst detection algorithm can be useful for the description and investigation of neuronal firing patterns and their variability with cellular and experimental conditions.
Poster presentation: Introduction Dopaminergic neurons in the midbrain show a variety of firing patterns, ranging from very regular firing pacemaker cells to bursty and irregular neurons. The effects of different experimental conditions (like pharmacological treatment or genetical manipulations) on these neuronal discharge patterns may be subtle. Applying a stochastic model is a quantitative approach to reveal these changes. ...
Poster presentation: The analysis of neuronal processes distributed across multiple cortical areas aims at the identification of interactions between signals recorded at different sites. Such interactions can be described by measuring the stability of phase angles in the case of oscillatory signals or other forms of signal dependencies for less regular signals. Before, however, any form of interaction can be analyzed at a given time and frequency, it is necessary to assess whether all potentially contributing signals are present. We have developed a new statistical procedure for the detection of coincident power in multiple simultaneously recorded analog signals, allowing the classification of events as 'non-accidental co-activation'. This method can effectively operate on single trials, each lasting only for a few seconds. Signals need to be transformed into time-frequency space, e.g. by applying a short-time Fourier transformation using a Gaussian window. The discrete wavelet transform (DWT) is used in order to weight the resulting power patterns according to their frequency. Subsequently, the weighted power patterns are binarized via applying a threshold. At this final stage, significant power coincidence is determined across all subgroups of channel combinations for individual frequencies by selecting the maximum ratio between observed and expected duration of co-activation as test statistic. The null hypothesis that the activity in each channel is independent from the activity in every other channel is simulated by independent, random rotation of the respective activity patterns. We applied this procedure to single trials of multiple simultaneously sampled local field potentials (LFPs) obtained from occipital, parietal, central and precentral areas of three macaque monkeys. Since their task was to use visual cues to perform a precise arm movement, co-activation of numerous cortical sites was expected. In a data set with 17 channels analyzed, up to 13 sites expressed simultaneous power in the range between 5 and 240 Hz. On average, more than 50% of active channels participated at least once in a significant power co-activation pattern (PCP). Because the significance of such PCPs can be evaluated at the level of single trials, we are confident that this procedure is useful to study single trial variability with sufficient accuracy that much of the behavioral variability can be explained by the dynamics of the underlying distributed neuronal processes.
Background Although current molecular clock methods offer greater flexibility in modelling historical evolutionary events, calibration of the clock with dates from the fossil record is still problematic for many groups. Here we implement several new approaches in molecular dating to estimate evolutionary ages of Lacertidae, an Old World family of lizards with a poor fossil record and uncertain phylogeny. Four different models of rate variation are tested in a new program for Bayesian phylogenetic analysis called TreeTime, based on a combination of mitochondrial and nuclear gene sequences. We incorporate paleontological uncertainty into divergence estimates by expressing multiple calibration dates as a range of probabilistic distributions. We also test the reliability of our proposed calibrations by exploring effects of individual priors on posterior estimates. Results According to the most reliable model, as indicated by Bayes factor comparison, modern lacertids arose shortly after the K/T transition and entered Africa about 45 million years ago, with the majority of their African radiation occurring in the Eocene and Oligocene. Our findings indicate much earlier origins for these clades than previously reported, and we discuss our results in light of paleogeographic trends during the Cenozoic. Conclusions This study represents the first attempt to estimate evolutionary ages of a specific group of reptiles exhibiting uncertain phylogenetic relationships, molecular rate variation and a poor fossil record. Our results emphasize the sensitivity of molecular divergence dates to fossil calibrations, and support the use of combined molecular data sets and multiple, well-spaced dates from the fossil record as minimum node constraints. The bioinformatics program used here, TreeTime, is publicly available, and we recommend its use for molecular dating of taxa faced with similar challenges.
Exported proteases of Helicobacter pylori (H. pylori) are potentially involved in pathogen-associated disorders leading to gastric inflammation and neoplasia. By comprehensive sequence screening of the H. pylori proteome for predicted secreted proteases, we retrieved several candidate genes. We detected caseinolytic activities of several such proteases, which are released independently from the H. pylori type IV secretion system encoded by the cag pathogenicity island (cagPAI). Among these, we found the predicted serine protease HtrA (Hp1019), which was previously identified in the bacterial secretome of H. pylori. Importantly, we further found that the H. pylori genes hp1018 and hp1019 represent a single gene likely coding for an exported protein. Here, we directly verified proteolytic activity of HtrA in vitro and identified the HtrA protease in zymograms by mass spectrometry. Overexpressed and purified HtrA exhibited pronounced proteolytic activity, which is inactivated after mutation of Ser205 to alanine in the predicted active center of HtrA. These data demonstrate that H. pylori secretes HtrA as an active protease, which might represent a novel candidate target for therapeutic intervention strategies.
Poster presentation: Introduction The brain is a highly interconnected network of constantly interacting units. Understanding the collective behavior of these units requires a multi-dimensional approach. The results of such analyses are hard to visualize and interpret. Hence tools capable of dealing with such tasks become imperative. ....
We present a measurement of e+e− pair production in central PbAu collisions at 158A GeV/c. As reported earlier, a significant excess of the e+e− pair yield over the expectation from hadron decays is observed. The improved mass resolution of the present data set, recorded with the upgraded CERES experiment at the CERN-SPS, allows for a comparison of the data with different theoretical approaches. The data clearly favor a substantial in-medium broadening of the ρ spectral function over a density-dependent shift of the ρ pole mass. The in-medium broadening model implies that baryon induced interactions are the key mechanism to the observed modifications of the ρ meson at SPS energy.
We provide the first non-trivial result on dynamic breadth-first search (BFS) in external-memory: For general sparse undirected graphs of initially $n$ nodes and O(n) edges and monotone update sequences of either $\Theta(n)$ edge insertions or $\Theta(n)$ edge deletions, we prove an amortized high-probability bound of $O(n/B^{2/3}+\sort(n)\cdot \log B)$ I/Os per update. In contrast, the currently best approach for static BFS on sparse undirected graphs requires $\Omega(n/B^{1/2}+\sort(n))$ I/Os. 1998 ACM Subject Classification: F.2.2. Key words and phrases: External Memory, Dynamic Graph Algorithms, BFS, Randomization.
The pathogenesis of nodular lymphocyte–predominant Hodgkin lymphoma (NLPHL) and its relationship to other lymphomas are largely unknown. This is partly because of the technical challenge of analyzing its rare neoplastic lymphocytic and histiocytic (L&H) cells, which are dispersed in an abundant nonneoplastic cellular microenvironment. We performed a genome-wide expression study of microdissected L&H lymphoma cells in comparison to normal and other malignant B cells that indicated a relationship of L&H cells to and/or that they originate from germinal center B cells at the transition to memory B cells. L&H cells show a surprisingly high similarity to the tumor cells of T cell–rich B cell lymphoma and classical Hodgkin lymphoma, a partial loss of their B cell phenotype, and deregulation of many apoptosis regulators and putative oncogenes. Importantly, L&H cells are characterized by constitutive nuclear factor {kappa}B activity and aberrant extracellular signal-regulated kinase signaling. Thus, these findings shed new light on the nature of L&H cells, reveal several novel pathogenetic mechanisms in NLPHL, and may help in differential diagnosis and lead to novel therapeutic strategies.
Attraction and commercial success of web sites depend heavily on the additional values visitors may find. Here, individual, automatically obtained and maintained user profiles are the key for user satisfaction. This contribution shows for the example of a cooking information site how user profiles might be obtained using category information provided by cooking recipes. It is shown that metrical distance functions and standard clustering procedures lead to erroneous results. Instead, we propose a new mutual information based clustering approach and outline its implications for the example of user profiling.
In this contribution we present algorithms for model checking of analog circuits enabling the specification of time constraints. Furthermore, a methodology for defining time-based specifications is introduced. An already known method for model checking of integrated analog circuits has been extended to take into account time constraints. The method will be presented using three industrial circuits. The results of model checking will be compared to verification by simulation.
Succinctness is a natural measure for comparing the strength of different logics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all properties that can be expressed in L_2 can be expressed in L_1 by formulas of (approximately) the same size, but some properties can be expressed in L_1 by (significantly) smaller formulas.
We study the succinctness of logics on linear orders. Our first theorem is concerned with the finite variable fragments of first-order logic. We prove that:
(i) Up to a polynomial factor, the 2- and the 3-variable fragments of first-order logic on linear orders have the same succinctness. (ii) The 4-variable fragment is exponentially more succinct than the 3-variable fragment. Our second main result compares the succinctness of first-order logic on linear orders with that of monadic second-order logic. We prove that the fragment of monadic second-order logic that has the same expressiveness as first-order logic on linear orders is non-elementarily more succinct than first-order logic.
We present a biologically-inspired system for real-time, feed-forward object recognition in cluttered scenes. Our system utilizes a vocabulary of very sparse features that are shared between and within different object models. To detect objects in a novel scene, these features are located in the image, and each detected feature votes for all objects that are consistent with its presence. Due to the sharing of features between object models our approach is more scalable to large object databases than traditional methods. To demonstrate the utility of this approach, we train our system to recognize any of 50 objects in everyday cluttered scenes with substantial occlusion. Without further optimization we also demonstrate near-perfect recognition on a standard 3-D recognition problem. Our system has an interpretation as a sparsely connected feed-forward neural network, making it a viable model for fast, feed-forward object recognition in the primate visual system.
In bioinformatics, biochemical signal pathways can be modeled by many differential equations. It is still an open problem how to fit the huge amount of parameters of the equations to the available data. Here, the approach of systematically obtaining the most appropriate model and learning its parameters is extremely interesting. One of the most often used approaches for model selection is to choose the least complex model which “fits the needs”. For noisy measurements, the model which has the smallest mean squared error of the observed data results in a model which fits too accurately to the data – it is overfitting. Such a model will perform good on the training data, but worse on unknown data. This paper propose as model selection criterion the least complex description of the observed data by the model, the minimum description length. For the small, but important example of inflammation modeling the performance of the approach is evaluated. Keywords: biochemical pathways, differential equations, septic shock, parameter estimation, overfitting, minimum description length.
Data driven automatic model selection and parameter adaptation – a case study for septic shock
(2004)
In bioinformatics, biochemical pathways can be modeled by many differential equations. It is still an open problem how to fit the huge amount of parameters of the equations to the available data. Here, the approach of systematically learning the parameters is necessary. This paper propose as model selection criterion the least complex description of the observed data by the model, the minimum description length. For the small, but important example of inflammation modeling the performance of the approach is evaluated.
In bioinformatics, biochemical pathways can be modeled by many differential equations. It is still an open problem how to fit the huge amount of parameters of the equations to the available data. Here, the approach of systematically learning the parameters is necessary. In this paper, for the small, important example of inflammation modeling a network is constructed and different learning algorithms are proposed. It turned out that due to the nonlinear dynamics evolutionary approaches are necessary to fit the parameters for sparse, given data. Keywords: model parameter adaption, septic shock. coupled differential equations, genetic algorithm.
Since the description of sepsis by Schottmüller in 1914, the amount on knowledge available on sepsis and its underlying pathophysiology has substantially increased. Epidemiologic examinations of abdominal septic shock patients show the potential for high risk posed by and the extensive therapy situation in the intensive care unit (ICU) (5). Unfortunately, until now it has not been possible to significantly reduce the mortality rate of septic shock, which is as high as 50-60% worldwide, although PROWESS' results (1) are encouraging. This paper summarizes the main results of the MEDAN project and their medical impacts. Several aspects are already published, see the references. The heterogeneity of patient groups and the variations in therapy strategies is seen as one of the main problems for sepsis trials. In the MEDAN multi-center study of 71 intensive care units in Germany, a group of 382 patients made up exclusively of abdominal septic shock patients who met the consensus criteria for septic shock (3) was analysed. For use within scores or stand-alone experiments variables are often studied as isolated variables, not as a multidimensional whole, e.g. a recent study takes a look at the role thrombocytes play (15). To avoid this limitation, our study compares several established scores (SOFA, APACHE II, SAPS II, MODS) by a multi-dimensional neuronal network analysis. For outcome prediction the data of 382 patients was analysed by using most of the commonly documented vital parameters and doses of medicine (metric variables). Data was collected in German hospitals from 1998 to 2001. The 382 handwritten patient records were transferred to an electronic database giving the amount of 2.5 million data entries. The metric data contained in the database is composed of daily measurements and doses of medicine. We used range and plausibility checks to allow no faulty data in the electronic database. 187 of the 382 patients are deceased (49 %).
Assessing enhanced knowledge discovery systems (eKDSs) constitutes an intricate issue that is understood merely to a certain extent by now. Based upon an analysis of why it is difficult to formally evaluate eKDSs, it is argued for a change of perspective: eKDSs should be understood as intelligent tools for qualitative analysis that support, rather than substitute, the user in the exploration of the data; a qualitative gap will be identified as the main reason why the evaluation of enhanced knowledge discovery systems is difficult. In order to deal with this problem, the construction of a best practice model for eKDSs is advocated. Based on a brief recapitulation of similar work on spoken language dialogue systems, first steps towards achieving this goal are performed, and directions of future research are outlined.
In bioinformatics, biochemical pathways can be modeled by many differential equations. It is still an open problem how to fit the huge amount of parameters of the equations to the available data. Here, the approach of systematically learning the parameters is necessary. In this paper, for the small, important example of inflammation modeling a network is constructed and different learning algorithms are proposed. It turned out that due to the nonlinear dynamics evolutionary approaches are necessary to fit the parameters for sparse, given data. Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence - ICTAI 2003
We investigate unary regular languages and compare deterministic finite automata (DFA’s), nondeterministic finite automata (NFA’s) and probabilistic finite automata (PFA’s) with respect to their size. Given a unary PFA with n states and an e-isolated cutpoint, we show that the minimal equivalent DFA has at most n exp 1/2e states in its cycle. This result is almost optimal, since for any alpha < 1 a family of PFA’s can be constructed such that every equivalent DFA has at least n exp alpha/2e states. Thus we show that for the model of probabilistic automata with a constant error bound, there is only a polynomial blowup for cyclic languages. Given a unary NFA with n states, we show that efficiently approximating the size of a minimal equivalent NFA within the factor sqrt(n)/ln n is impossible unless P = NP. This result even holds under the promise that the accepted language is cyclic. On the other hand we show that we can approximate a minimal NFA within the factor ln n, if we are given a cyclic unary n-state DFA.
A novel method for identifying the nature of QCD transitions in heavy-ion collision experiments is introduced. PointNet based Deep Learning (DL) models are developed to classify the equation of state (EoS) that drives the hydrodynamic evolution of the system created in Au-Au collisions at 10 AGeV. The DL models were trained and evaluated in different hypothetical experimental situations. A decreased performance is observed when more realistic experimental effects (acceptance cuts and decreased resolutions) are taken into account. It is shown that the performance can be improved by combining multiple events to make predictions. The PointNet based models trained on the reconstructed tracks of charged particles from the CBM detector simulation discriminate a crossover transition from a first order phase transition with an accuracy of up to 99.8%. The models were subjected to several tests to evaluate the dependence of its performance on the centrality of the collisions and physical parameters of fluid dynamic simulations. The models are shown to work in a broad range of centralities (b=0–7 fm). However, the performance is found to improve for central collisions (b=0–3 fm). There is a drop in the performance when the model parameters lead to reduced duration of the fluid dynamic evolution or when less fraction of the medium undergoes the transition. These effects are due to the limitations of the underlying physics and the DL models are shown to be superior in its discrimination performance in comparison to conventional mean observables.
We present a novel parallel one-more signature forgery against blind Okamoto-Schnorr and blind Schnorr signatures in which an attacker interacts some times with a legitimate signer and produces from these interactions signatures. Security against the new attack requires that the following ROS-problem is intractable: find an overdetermined, solvable system of linear equations modulo with random inhomogenities (right sides). There is an inherent weakness in the security result of POINTCHEVAL AND STERN. Theorem 26 [PS00] does not cover attacks with 4 parallel interactions for elliptic curves of order 2200. That would require the intractability of the ROS-problem, a plausible but novel complexity assumption. Conversely, assuming the intractability of the ROS-problem, we show that Schnorr signatures are secure in the random oracle and generic group model against the one-more signature forgery.
Syntactic coindexing restrictions are by now known to be of central importance to practical anaphor resolution approaches. Since, in particular due to structural ambiguity, the assumption of the availability of a unique syntactic reading proves to be unrealistic, robust anaphor resolution relies on techniques to overcome this deficiency.
This paper describes the ROSANA approach, which generalizes the verification of coindexing restrictions in order to make it applicable to the deficient syntactic descriptions that are provided by a robust state-of-the-art parser. By a formal evaluation on two corpora that differ with respect to text genre and domain, it is shown that ROSANA achieves high-quality robust coreference resolution. Moreover, by an in-depth analysis, it is proven that the robust implementation of syntactic disjoint reference is nearly optimal. The study reveals that, compared with approaches that rely on shallow preprocessing, the largely nonheuristic disjoint reference algorithmization opens up the possibility/or a slight improvement. Furthermore, it is shown that more significant gains are to be expected elsewhere, particularly from a text-genre-specific choice of preference strategies.
The performance study of the ROSANA system crucially rests on an enhanced evaluation methodology for coreference resolution systems, the development of which constitutes the second major contribution o/the paper. As a supplement to the model-theoretic scoring scheme that was developed for the Message Understanding Conference (MUC) evaluations, additional evaluation measures are defined that, on one hand, support the developer of anaphor resolution systems, and, on the other hand, shed light on application aspects of pronoun interpretation.
Channel routing is an NP-complete problem. Therefore, it is likely that there is no efficient algorithm solving this problem exactly.In this paper, we show that channel routing is a fixed-parameter tractable problem and that we can find a solution in linear time for a fixed channel width.We implemented our approach for the restricted layer model. The algorithm finds an optimal route for channels with up to 13 tracks within minutes or up to 11 tracks within seconds.Such narrow channels occur for example as a leaf problem of hierarchical routers or within standard cell generators.
One of the most severe short-comings of currently available equivalence checkers is their inability to verify integer multipliers. In this paper, we present a bit level reverse-engineering technique that can be integrated into standard equivalence checking flows. We propose a Boolean mapping algorithm that extracts a network of half adders from the gate netlist of an addition circuit. Once the arithmetic bit level representation of the circuit is obtained, equivalence checking can be performed using simple arithmetic operations. Experimental results show the promise of our approach.
In contrast to the symbolic approach, neural networks seldom are designed to explain what they have learned. This is a major obstacle for its use in everyday life. With the appearance of neuro-fuzzy systems which use vague, human-like categories the situation has changed. Based on the well-known mechanisms of learning for RBF networks, a special neuro-fuzzy interface is proposed in this paper. It is especially useful in medical applications, using the notation and habits of physicians and other medically trained people. As an example, a liver disease diagnosis system is presented.
We present a theoretical analysis of structural FSM traversal, which is the basis for the sequential equivalence checking algorithm Record & Play presented earlier. We compare the convergence behaviour of exact and approximative structural FSM traversal with that of standard BDD-based FSM traversal. We show that for most circuits encountered in practice exact structural FSM traversal reaches the fixed point as fast as symbolic FSM traversal, while approximation can significantly reduce in the number of iterations needed. Our experiments confirm these results.
This paper describes the use of a Radial Basis Function (RBF) neural network in the approximation of process parameters for the extrusion of a rubber profile in tyre production. After introducing the rubber industry problem, the RBF network model and the RBF net learning algorithm are developed, which uses a growing number of RBF units to compensate the approximation error up to the desired error limit. Its performance is shown for simple analytic examples. Then the paper describes the modelling of the industrial problem. Simulations show good results, even when using only a few training samples. The paper is concluded by a discussion of possible systematic error influences, improvements and potential generalisation benefits. Keywords: Adaptive process control; Parameter estimation; RBF-nets; Rubber extrusion
The prevention of credit card fraud is an important application for prediction techniques. One major obstacle for using neural network training techniques is the high necessary diagnostic quality: Since only one financial transaction of a thousand is invalid no prediction success less than 99.9% is acceptable. Due to these credit card transaction proportions complete new concepts had to be developed and tested on real credit card data. This paper shows how advanced data mining techniques and neural network algorithm can be combined successfully to obtain a high fraud coverage combined with a low false alarm rate.
We present the FPGA implementation of an algorithm [4] that computes implications between signal values in a boolean network. The research was performed as a masterrsquos thesis [5] at the University of Frankfurt. The recursive algorithm is rather complex for a hardware realization and therefore the FPGA implementation is an interesting example for the potential of reconfigurable computing beyond systolic algorithms. A circuit generator was written that transforms a boolean network into a network of small processing elements and a global control logic which together implement the algorithm. The resulting circuit performs the computation two orders of magnitudes faster than a software implementation run by a conventional workstation.
In this paper we regard first the situation where parallel channels are disturbed by noise. With the goal of maximal information conservation we deduce the conditions for a transform which "immunizes" the channels against noise influence before the signals are used in later operations. It shows up that the signals have to be decorrelated and normalized by the filter which corresponds for the case of one channel to the classical result of Shannon. Additional simulations for image encoding and decoding show that this constitutes an efficient approach for noise suppression. Furthermore, by a corresponding objective function we deduce the stochastic and deterministic learning rules for a neural network that implements the data orthonormalization. In comparison with other already existing normalization networks our network shows approximately the same in the stochastic case but, by its generic deduction ensures the convergence and enables the use as independent building block in other contexts, e.g. whitening for independent component analysis. Keywords: information conservation, whitening filter, data orthonormalization network, image encoding, noise suppression.
In this paper we present a non-deterministic call-by-need (untyped) lambda calculus lambda nd with a constant choice and a let-syntax that models sharing. Our main result is that lambda nd has the nice operational properties of the standard lambda calculus: confluence on sets of expressions, and normal order reduction is sufficient to reach head normal form. Using a strong contextual equivalence we show correctness of several program transformations. In particular of lambdalifting using deterministic maximal free expressions. These results show that lambda nd is a new and also natural combination of non-determinism and lambda-calculus, which has a lot of opportunities for parallel evaluation. An intended application of lambda nd is as a foundation for compiling lazy functional programming languages with I/O based on direct calls. The set of correct program transformations can be rigorously distinguished from non-correct ones. All program transformations are permitted with the slight exception that for transformations like common subexpression elimination and lambda-lifting with maximal free expressions the involved subexpressions have to be deterministic ones.
A new approach to optimize multilevel logic circuits is introduced. Given a multilevel circuit, the synthesis method optimizes its area while simultaneously enhancing its random pattern testability. The method is based on structural transformations at the gate level. New transformations involving EX-OR gates as well as Reed–Muller expansions have been introduced in the synthesis of multilevel circuits. This method is augmented with transformations that specifically enhance random-pattern testability while reducing the area. Testability enhancement is an integral part of our synthesis methodology. Experimental results show that the proposed methodology not only can achieve lower area than other similar tools, but that it achieves better testability compared to available testability enhancement tools such as tstfx. Specifically for ISCAS-85 benchmark circuits, it was observed that EX-OR gate-based transformations successfully contributed toward generating smaller circuits compared to other state-of-the-art logic optimization tools.
A memory checker for a data structure provides a method to check that the output of the data structure operations is consistent with the input even if the data is stored on some insecure medium. In [8] we present a general solution for all data structures that are based on insert(i,v) and delete(j) commands. In particular this includes stacks, queues, deques (double-ended queues) and lists. Here, we describe more time and space efficient solutions for stacks, queues and deques. Each algorithm takes only a single function evaluation of a pseudorandomlike function like DES or a collision-free hash function like MD5 or SHA for each push/pop resp. enqueue/dequeue command making our methods applicable to smart cards.
The paper focuses on the division of the sensor field into subsets of sensor events and proposes the linear transformation with the smallest achievable error for reproduction: the transform coding approach using the principal component analysis (PCA). For the implementation of the PCA, this paper introduces a new symmetrical, lateral inhibited neural network model, proposes an objective function for it and deduces the corresponding learning rules. The necessary conditions for the learning rate and the inhibition parameter for balancing the crosscorrelations vs. the autocorrelations are computed. The simulation reveals that an increasing inhibition can speed up the convergence process in the beginning slightly. In the remaining paper, the application of the network in picture encoding is discussed. Here, the use of non-completely connected networks for the self-organized formation of templates in cellular neural networks is shown. It turns out that the self-organizing Kohonen map is just the non-linear, first order approximation of a general self-organizing scheme. Hereby, the classical transform picture coding is changed to a parallel, local model of linear transformation by locally changing sets of self-organized eigenvector projections with overlapping input receptive fields. This approach favors an effective, cheap implementation of sensor encoding directly on the sensor chip. Keywords: Transform coding, Principal component analysis, Lateral inhibited network, Cellular neural network, Kohonen map, Self-organized eigenvector jets.
This paper describes the use of a radial basis function (RBF) neural network. It approximates the process parameters for the extrusion of a rubber profile used in tyre production. After introducing the problem, we describe the RBF net algorithm and the modeling of the industrial problem. The algorithm shows good results even using only a few training samples. It turns out that the „curse of dimensions“ plays an important role in the model. The paper concludes by a discussion of possible systematic error influences and improvements.
We analyse a continued fraction algorithm (abbreviated CFA) for arbitrary dimension n showing that it produces simultaneous diophantine approximations which are up to the factor 2^((n+2)/4) best possible. Given a real vector x=(x_1,...,x_{n-1},1) in R^n this CFA generates a sequence of vectors (p_1^(k),...,p_{n-1}^(k),q^(k)) in Z^n, k=1,2,... with increasing integers |q^{(k)}| satisfying for i=1,...,n-1 | x_i - p_i^(k)/q^(k) | <= 2^((n+2)/4) sqrt(1+x_i^2) |q^(k)|^(1+1/(n-1)) By a theorem of Dirichlet this bound is best possible in that the exponent 1+1/(n-1) can in general not be increased.
We present a framework for the self-organized formation of high level learning by a statistical preprocessing of features. The paper focuses first on the formation of the features in the context of layers of feature processing units as a kind of resource-restricted associative multiresolution learning We clame that such an architecture must reach maturity by basic statistical proportions, optimizing the information processing capabilities of each layer. The final symbolic output is learned by pure association of features of different levels and kind of sensorial input. Finally, we also show that common error-correction learning for motor skills can be accomplished also by non-specific associative learning. Keywords: feedforward network layers, maximal information gain, restricted Hebbian learning, cellular neural nets, evolutionary associative learning
After a short introduction into traditional image transform coding, multirate systems and multiscale signal coding the paper focuses on the subject of image encoding by a neural network. Taking also noise into account a network model is proposed which not only learns the optimal localized basis functions for the transform but also learns to implement a whitening filter by multi-resolution encoding. A simulation showing the multi-resolution capabilitys concludes the contribution.
Let b1, . . . , bm 2 IRn be an arbitrary basis of lattice L that is a block Korkin Zolotarev basis with block size ¯ and let ¸i(L) denote the successive minima of lattice L. We prove that for i = 1, . . . ,m 4 i + 3 ° 2 i 1 ¯ 1 ¯ · kbik2/¸i(L)2 · ° 2m i ¯ 1 ¯ i + 3 4 where °¯ is the Hermite constant. For ¯ = 3 we establish the optimal upper bound kb1k2/¸1(L)2 · µ3 2¶m 1 2 1 and we present block Korkin Zolotarev lattice bases for which this bound is tight. We improve the Nearest Plane Algorithm of Babai (1986) using block Korkin Zolotarev bases. Given a block Korkin Zolotarev basis b1, . . . , bm with block size ¯ and x 2 L(b1, . . . , bm) a lattice point v can be found in time ¯O(¯) satisfying kx vk2 · m° 2m ¯ 1 ¯ minu2L kx uk2.
Parallel FFT-hashing
(1994)
We propose two families of scalable hash functions for collision resistant hashing that are highly parallel and based on the generalized fast Fourier transform (FFT). FFT hashing is based on multipermutations. This is a basic cryptographic primitive for perfect generation of diffusion and confusion which generalizes the boxes of the classic FFT. The slower FFT hash functions iterate a compression function. For the faster FFT hash functions all rounds are alike with the same number of message words entering each round.
It is well known that artificial neural nets can be used as approximators of any continuous functions to any desired degree and therefore be used e.g. in high - speed, real-time process control. Nevertheless, for a given application and a given network architecture the non-trivial task remains to determine the necessary number of neurons and the necessary accuracy (number of bits) per weight for a satisfactory operation which are critical issues in VLSI and computer implementations of nontrivial tasks. In this paper the accuracy of the weights and the number of neurons are seen as general system parameters which determine the maximal approximation error by the absolute amount and the relative distribution of information contained in the network. We define as the error-bounded network descriptional complexity the minimal number of bits for a class of approximation networks which show a certain approximation error and achieve the conditions for this goal by the new principle of optimal information distribution. For two examples, a simple linear approximation of a non-linear, quadratic function and a non-linear approximation of the inverse kinematic transformation used in robot manipulator control, the principle of optimal information distribution gives the the optimal number of neurons and the resolutions of the variables, i.e. the minimal amount of storage for the neural net. Keywords: Kolmogorov complexity, e-Entropy, rate-distortion theory, approximation networks, information distribution, weight resolutions, Kohonen mapping, robot control.
The general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on basis reduction algorithms to find short nonzero vectors in special lattices. The Lagarias-Odlyzko algorithm would solve almost all subset sum problems of density < 0.6463 . . . in polynomial time if it could invoke a polynomial-time algorithm for finding the shortest non-zero vector in a lattice. This paper presents two modifications of that algorithm, either one of which would solve almost all problems of density < 0.9408 . . . if it could find shortest non-zero vectors in lattices. These modifications also yield dramatic improvements in practice when they are combined with known lattice basis reduction algorithms.
We present a hierarchy of polynomial time lattice basis reduction algorithms that stretch from Lenstra, Lenstra, Lovász reduction to Korkine–Zolotareff reduction. Let λ(L) be the length of a shortest nonzero element of a lattice L. We present an algorithm which for k∈N finds a nonzero lattice vector b so that |b|2⩽(6k2)nkλ(L)2. This algorithm uses O(n2(kk+o(k))+n2)log B) arithmetic operations on O(n log B)-bit integers. This holds provided that the given basis vectors b1,…,bn∈Zn are integral and have the length bound B. This algorithm successively applies Korkine–Zolotareff reduction to blocks of length k of the lattice basis. We also improve Kannan's algorithm for Korkine-Zolotareff reduction.
Considered are the classes QL (quasilinear) and NQL (nondet quasllmear) of all those problems that can be solved by deterministic (nondetermlnlsttc, respectively) Turmg machines in time O(n(log n) ~) for some k Effloent algorithms have time bounds of th~s type, it is argued. Many of the "exhausUve search" type problems such as satlsflablhty and colorabdlty are complete in NQL with respect to reductions that take O(n(log n) k) steps This lmphes that QL = NQL iff satisfiabdlty is m QL CR CATEGORIES: 5.25