Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).

Juverhälsoproblem orsakade av Streptococcus agalactiae på stora mjölkgårdar med mjölkningsrobot

Streptococcus agalactiae –juverinflammation var tidigare ett stort problem i många länder, inklusive Finland. I och med förbättrad mjölkningshygien och antibiotikabehandlingar har bakterien så gott som eradikerats från mjölkbesättningarna. Nu verkar bakterien i viss mån ha kommit tillbaka till våra stora mjölkgårdar. Avhandlingens experimentella del utfördes på en mjölkgård, med ca 180 mjölkande och tre mjölkningsrobotar, som haft problem med Str. agalactiae. Man hoppades utreda hur stort problemet på gården var samt möjliga smittovägar. Man undersökte också möjligheten att använda mjölkningsrobotens automatiska provtagningsutrustning för provtagning av bakteriella prov. PCRmetoden jämfördes med konventionell odling vid diagnostik av juverinflammationer orsakade av Str. agalactiae. På gården gick man igenom anteckningar samt hälso- och seminkort för att få en bild över situationen. Man gjorde en uppföljning av mjölkningen för tolv kor vid den ena mjölkningsroboten. Man tog 47 stycken kospecifika mjölkprov samt ett prov från mjölktanken. Mjölkprov i tre serier både mjölkade för hand och direkt från mjölkuppsamlaren på mjölkningsroboten togs. Man tog sammanlagt 23 renlighetsprov från mjölkningsroboten, tre från den automatiska provtagningsutrustningen samt två från djurskötarnas händer. Från den automatiska provtagningsutrustningen togs även ett genomsköljningsprov. Av mjölkprov som tidigare tagits på gården hade man hittat Str. agalactiae i ca 17%. I denna studie hittades Str. agalactiae i tre kospecifika mjölkprov, vilket motsvarar en prevalens på ca 2%. Vid uppföljningen av mjölkningarna upptäcktes inget alarmerande, men spenarnas hälsa samt tommjölkningar är något som bör följas upp. Av renlighetsproven hittades Str. agalactiae i ett prov taget från borsthållaren. Svaren från mjölkproven tagna i serier tyder på att den automatiska provtagningsutrustningen inte går att använda till bakteriella prov, eftersom mjölken från en Str. agalactiae –infekterad ko verkar påverka resultatet också hos följande kor. Resultatet är väntat, eftersom mjölkprov alltid skall tas aseptiskt och det går inte med den automatiska provtagningsutrustningen så som den i dagsläget är utvecklad. Från sju av nio mjölkprov, där man hittat Str. agalactiae med PCR-metoden, hittades bakterien också med konventionell odling. Från tankmjölksprovet kunde man inte hitta Str. agalactiae med konventionell odling. PCR-metoden verkar enligt den här studien vara mer känslig att upptäcka Str. agalactiae jämfört med konventionell odling.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

Elewård på finska och pä svenska. En fallstudie som granskar samband mellan socialt kap språk och ungdomars välmående

Forskningen utreder skillnader mellan finsk- och svenskspråkiga skolor i en kommun i Nylands län utgående från elevvårdens synvinkel. Syftet är att kartlägga situationen i en kommun och synliggöra de skillnader och faktorer som påverkar det sociala kapitalets mängd i skolorna. Skillnaderna betraktas utgående från det sociala kapitalets inverkan på gemenskapen och från ekologisk synvinkel. Sambandet mellan det sociala stöd och den sociala kontroll som särskilt de vuxna i skolan producerar, har betydelse för skolelevers välmående. För att kunna bilda en socialt stödande och socialt kontrollerande atmosfär krävs det funktionella förändringar i skolan. Särskilt de vuxna i skolan skulle behöva mera gemenskap. Elevvårdsarbetet och skolarbetet riktar sig främst mot elever i dag, fastän de vuxna skulle behöva stärka sina sociala förhållanden. Bris i uppkomsten av socialt stöd och kontroll beror främst på problem i samarbete och kommunikation mellan de vuxna i skolan. Skolkuratorerna är de enda professionella inom skolan som i sitt arbete tar hela skolan som gemenskap i beaktande. Denna forskning är en abduktiv kvalitativ fallstudie som är tili sin karaktär beskrivande. Som data används intervjuer av elevvärdspersonalen i kommunen och enkäten Hälsa i skolan av Institutet för hälsa och välfärd från år 2008. Viktigaste källan för forskningen är Noora Ellone (2008) forskning "Kasvuyhteisö nuoren turvana".

Transport coefficients for the shear dynamo problem at small Reynolds numbers

We build on the formulation developed in S. Sridhar and N. K. Singh J. Fluid Mech. 664, 265 (2010)] and present a theory of the shear dynamo problem for small magnetic and fluid Reynolds numbers, but for arbitrary values of the shear parameter. Specializing to the case of a mean magnetic field that is slowly varying in time, explicit expressions for the transport coefficients alpha(il) and eta(iml) are derived. We prove that when the velocity field is nonhelical, the transport coefficient alpha(il) vanishes. We then consider forced, stochastic dynamics for the incompressible velocity field at low Reynolds number. An exact, explicit solution for the velocity field is derived, and the velocity spectrum tensor is calculated in terms of the Galilean-invariant forcing statistics. We consider forcing statistics that are nonhelical, isotropic, and delta correlated in time, and specialize to the case when the mean field is a function only of the spatial coordinate X-3 and time tau; this reduction is necessary for comparison with the numerical experiments of A. Brandenburg, K. H. Radler, M. Rheinhardt, and P. J. Kapyla Astrophys. J. 676, 740 (2008)]. Explicit expressions are derived for all four components of the magnetic diffusivity tensor eta(ij) (tau). These are used to prove that the shear-current effect cannot be responsible for dynamo action at small Re and Rm, but for all values of the shear parameter.

Three- and Seven-Point Optimally Weighted Recursive Median Filters for Gas Turbine Diagnostics

Measured health signals incorporate significant details about any malfunction in a gas turbine. The attenuation of noise and removal of outliers from these health signals while preserving important features is an important problem in gas turbine diagnostics. The measured health signals are a time series of sensor measurements such as the low rotor speed, high rotor speed, fuel flow, and exhaust gas temperature in a gas turbine. In this article, a comparative study is done by varying the window length of acausal and unsymmetrical weighted recursive median filters and numerical results for error minimization are obtained. It is found that optimal filters exist, which can be used for engines where data are available slowly (three-point filter) and rapidly (seven-point filter). These smoothing filters are proposed as preprocessors of measurement delta signals before subjecting them to fault detection and isolation algorithms.

Noise and outlier removal from jet engine health signals using weighted FIR median hybrid filters

The removal of noise and outliers from measurement signals is a major problem in jet engine health monitoring. Topical measurement signals found in most jet engines include low rotor speed, high rotor speed. fuel flow and exhaust gas temperature. Deviations in these measurements from a baseline 'good' engine are often called measurement deltas and the health signals used for fault detection, isolation, trending and data mining. Linear filters such as the FIR moving average filter and IIR exponential average filter are used in the industry to remove noise and outliers from the jet engine measurement deltas. However, the use of linear filters can lead to loss of critical features in the signal that can contain information about maintenance and repair events that could be used by fault isolation algorithms to determine engine condition or by data mining algorithms to learn valuable patterns in the data, Non-linear filters such as the median and weighted median hybrid filters offer the opportunity to remove noise and gross outliers from signals while preserving features. In this study. a comparison of traditional linear filters popular in the jet engine industry is made with the median filter and the subfilter weighted FIR median hybrid (SWFMH) filter. Results using simulated data with implanted faults shows that the SWFMH filter results in a noise reduction of over 60 per cent compared to only 20 per cent for FIR filters and 30 per cent for IIR filters. Preprocessing jet engine health signals using the SWFMH filter would greatly improve the accuracy of diagnostic systems. (C) 2002 Published by Elsevier Science Ltd.

Dynamics of pulled desorption with effects of excluded-volume interaction: The p-Laplacian diffusion equation and its exact solution

We analyze the dynamics of desorption of a polymer molecule which is pulled at one of its ends with force f, trying to desorb it. We assume a monomer to desorb when the pulling force on it exceeds a critical value f(c). We formulate an equation for the average position of the n-th monomer, which takes into account excluded-volume interaction through the blob-picture of a polymer under external constraints. The approach leads to a diffusion equation with a p-Laplacian for the propagation of the stretching along the chain. This has to be solved subject to a moving boundary condition. Interestingly, within this approach, the problem can be solved exactly in the trumpet, stem-flower and stem regimes. In the trumpet regime, we get tau = tau(0)n(d)(2), where n(d) is the number of monomers that have desorbed at the time tau. tau(0) is known only numerically, but for f close to f(c), it is found to be tau(0) similar to f(c)/(f(2/3) - f(c)(2/3)) If one used simple Rouse dynamics, this result would change to tau similar to f(c)n(d)(2)/(f - f(c)). In the other regimes too, one can find exact solution, and interestingly, in all regimes tau similar to n(d)(2). Copyright (C) EPLA, 2011

Interaction Signatures Stabilizing the NAD(P)-Binding Rossmann Fold: A Structure Network Approach

The fidelity of the folding pathways being encoded in the amino acid sequence is met with challenge in instances where proteins with no sequence homology, performing different functions and no apparent evolutionary linkage, adopt a similar fold. The problem stated otherwise is that a limited fold space is available to a repertoire of diverse sequences. The key question is what factors lead to the formation of a fold from diverse sequences. Here, with the NAD(P)-binding Rossmann fold domains as a case study and using the concepts of network theory, we have unveiled the consensus structural features that drive the formation of this fold. We have proposed a graph theoretic formalism to capture the structural details in terms of the conserved atomic interactions in global milieu, and hence extract the essential topological features from diverse sequences. A unified mathematical representation of the different structures together with a judicious concoction of several network parameters enabled us to probe into the structural features driving the adoption of the NAD(P)-binding Rossmann fold. The atomic interactions at key positions seem to be better conserved in proteins, as compared to the residues participating in these interactions. We propose a ``spatial motif'' and several ``fold specific hot spots'' that form the signature structural blueprints of the NAD(P)-binding Rossmann fold domain. Excellent agreement of our data with previous experimental and theoretical studies validates the robustness and validity of the approach. Additionally, comparison of our results with statistical coupling analysis (SCA) provides further support. The methodology proposed here is general and can be applied to similar problems of interest.

Free turbulent shear layer in a point vortex gas as a problem in nonequilibrium statistical mechanics

This paper attempts to unravel any relations that may exist between turbulent shear flows and statistical mechanics through a detailed numerical investigation in the simplest case where both can be well defined. The flow considered for the purpose is the two-dimensional (2D) temporal free shear layer with a velocity difference Delta U across it, statistically homogeneous in the streamwise direction (x) and evolving from a plane vortex sheet in the direction normal to it (y) in a periodic-in-x domain L x +/-infinity. Extensive computer simulations of the flow are carried out through appropriate initial-value problems for a ``vortex gas'' comprising N point vortices of the same strength (gamma = L Delta U/N) and sign. Such a vortex gas is known to provide weak solutions of the Euler equation. More than ten different initial-condition classes are investigated using simulations involving up to 32 000 vortices, with ensemble averages evaluated over up to 10(3) realizations and integration over 10(4)L/Delta U. The temporal evolution of such a system is found to exhibit three distinct regimes. In Regime I the evolution is strongly influenced by the initial condition, sometimes lasting a significant fraction of L/Delta U. Regime III is a long-time domain-dependent evolution towards a statistically stationary state, via ``violent'' and ``slow'' relaxations P.-H. Chavanis, Physica A 391, 3657 (2012)], over flow time scales of order 10(2) and 10(4)L/Delta U, respectively (for N = 400). The final state involves a single structure that stochastically samples the domain, possibly constituting a ``relative equilibrium.'' The vortex distribution within the structure follows a nonisotropic truncated form of the Lundgren-Pointin (L-P) equilibrium distribution (with negatively high temperatures; L-P parameter lambda close to -1). The central finding is that, in the intermediate Regime II, the spreading rate of the layer is universal over the wide range of cases considered here. The value (in terms of momentum thickness) is 0.0166 +/- 0.0002 times Delta U. Regime II, extensively studied in the turbulent shear flow literature as a self-similar ``equilibrium'' state, is, however, a part of the rapid nonequilibrium evolution of the vortex-gas system, which we term ``explosive'' as it lasts less than one L/Delta U. Regime II also exhibits significant values of N-independent two-vortex correlations, indicating that current kinetic theories that neglect correlations or consider them as O(1/N) cannot describe this regime. The evolution of the layer thickness in present simulations in Regimes I and II agree with the experimental observations of spatially evolving (3D Navier-Stokes) shear layers. Further, the vorticity-stream-function relations in Regime III are close to those computed in 2D Navier-Stokes temporal shear layers J. Sommeria, C. Staquet, and R. Robert, J. Fluid Mech. 233, 661 (1991)]. These findings suggest the dominance of what may be called the Kelvin-Biot-Savart mechanism in determining the growth of the free shear layer through large-scale momentum and vorticity dispersal.

Cubic Sieve Congruence of the Discrete Logarithm Problem, and fractional part sequences

The Cubic Sieve Method for solving the Discrete Logarithm Problem in prime fields requires a nontrivial solution to the Cubic Sieve Congruence (CSC) x(3) equivalent to y(2)z (mod p), where p is a given prime number. A nontrivial solution must also satisfy x(3) not equal y(2)z and 1 <= x, y, z < p(alpha), where alpha is a given real number such that 1/3 < alpha <= 1/2. The CSC problem is to find an efficient algorithm to obtain a nontrivial solution to CSC. CSC can be parametrized as x equivalent to v(2)z (mod p) and y equivalent to v(3)z (mod p). In this paper, we give a deterministic polynomial-time (O(ln(3) p) bit-operations) algorithm to determine, for a given v, a nontrivial solution to CSC, if one exists. Previously it took (O) over tilde (p(alpha)) time in the worst case to determine this. We relate the CSC problem to the gap problem of fractional part sequences, where we need to determine the non-negative integers N satisfying the fractional part inequality {theta N} < phi (theta and phi are given real numbers). The correspondence between the CSC problem and the gap problem is that determining the parameter z in the former problem corresponds to determining N in the latter problem. We also show in the alpha = 1/2 case of CSC that for a certain class of primes the CSC problem can be solved deterministically in <(O)over tilde>(p(1/3)) time compared to the previous best of (O) over tilde (p(1/2)). It is empirically observed that about one out of three primes is covered by the above class. (C) 2013 Elsevier B.V. All rights reserved.

Performance evaluation of typical approximation algorithms for nonconvex l(p)-minimization in diffuse optical tomography

The sparse estimation methods that utilize the l(p)-norm, with p being between 0 and 1, have shown better utility in providing optimal solutions to the inverse problem in diffuse optical tomography. These l(p)-norm-based regularizations make the optimization function nonconvex, and algorithms that implement l(p)-norm minimization utilize approximations to the original l(p)-norm function. In this work, three such typical methods for implementing the l(p)-norm were considered, namely, iteratively reweighted l(1)-minimization (IRL1), iteratively reweighted least squares (IRLS), and the iteratively thresholding method (ITM). These methods were deployed for performing diffuse optical tomographic image reconstruction, and a systematic comparison with the help of three numerical and gelatin phantom cases was executed. The results indicate that these three methods in the implementation of l(p)-minimization yields similar results, with IRL1 fairing marginally in cases considered here in terms of shape recovery and quantitative accuracy of the reconstructed diffuse optical tomographic images. (C) 2014 Optical Society of America