Locally checkable proofs

This work studies decision problems from the perspective of nondeterministic distributed algorithms. For a yes-instance there must exist a proof that can be verified with a distributed algorithm: all nodes must accept a valid proof, and at least one node must reject an invalid proof. We focus on locally checkable proofs that can be verified with a constant-time distributed algorithm. For example, it is easy to prove that a graph is bipartite: the locally checkable proof gives a 2-colouring of the graph, which only takes 1 bit per node. However, it is more difficult to prove that a graph is not bipartite—it turns out that any locally checkable proof requires Ω(log n) bits per node. In this work we classify graph problems according to their local proof complexity, i.e., how many bits per node are needed in a locally checkable proof. We establish tight or near-tight results for classical graph properties such as the chromatic number. We show that the proof complexities form a natural hierarchy of complexity classes: for many classical graph problems, the proof complexity is either 0, Θ(1), Θ(log n), or poly(n) bits per node. Among the most difficult graph properties are symmetric graphs, which require Ω(n2) bits per node, and non-3-colourable graphs, which require Ω(n2/log n) bits per node—any pure graph property admits a trivial proof of size O(n2).

Bacteriophage therapy for Staphylococcus aureus bacteremia in streptozotocin-induced diabetic mice

The protective effect of bacteriophage was assessed against experimental Staphylococcus aureus lethal bacteremia in streptozotocin (STZ) induced-diabetic and non-diabetic mice. Intraperitoneal administrations of S. aureus (RCS21) of 2 x 10(8) CFU caused lethal bacteremia in both diabetic and non-diabetic mice. A single administration of a newly isolated lytic phage strain (GRCS) significantly protected diabetic and nondiabetic mice from lethal bacteremia (survival rate 90% and 100% for diabetic and non-diabetic bacteremic groups versus 0% for saline-treated groups). Comparison of phage therapy to oxacillin treatment showed a significant decrease in RCS21 of 5 and 3 log units in diabetic and nondiabetic bacteremic mice, respectively. The same protection efficiency of phage GRCS was attained even when the treatment was delayed up to 4 h in both diabetic and non-diabetic bacteremic mice. Inoculation of mice with a high dose (10(10) PFU) of phage GRCS alone produced no adverse effects attributable to the phage per se. These results suggest that phages could constitute valuable prophylaxis against S. aureus infections, especially in immunocompromised patients. (C) 2010 Institut Pasteur. Published by Elsevier Masson SAS. All rights reserved.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V(G) and edge set E(C). A k-dimensional box is a Cartesian product of closed intervals a(1), b(1)] x a(2), b(2)] x ... x a(k), b(k)]. The boxicity of G, box(G) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes, i.e. each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset where S is the ground set and P is a reflexive, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer l such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with its extended double cover, denoted as G(c). Let P-c be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P-c) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension. In the other direction, using the already known bounds for partial order dimension we get the following: (I) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta) which is an improvement over the best known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0, unless NP=ZPP.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Photocatalytic Inactivation of Escherichia coli with LbL Fabricated Immobilized TiO2 Thin Films

Photocatalysis using semiconductor catalyst such as TiO2, in presence of UV light, is a promising technique for the inactivation of various microorganisms present in water. In the current study, the photocatalytic inactivation of Escherichia coli bacteria was studied with commercial Degussa Aeroxide TiO2 P25 (Aeroxide) and combustion synthesized TiO2 (CS TiO2) catalysts immobilized on glass slides in presence of UV irradiation. Thin films of the catalyst and polyelectrolytes, poly(allyl amine hydrochloride) and poly(styrene sulfonate sodium salt), were deposited on glass slides by layer by layer (LbL) deposition method and characterized by SEM and AFM imaging. The effect of various parameters, namely, catalyst concentration, surface area and number of bilayers, on inactivation was studied. Maximum inactivation of 8-log reduction in the viable count was observed with 1.227 mg/cm(2) of catalyst loaded slides. With this loading, complete inactivation was observed within 90 min and 75 min of irradiation, for Aeroxide and CS TiO2, respectively. Further increase in the catalyst concentration or increasing number of bilayers had no significant effect on inactivation. The effect of surface area on the inactivation was studied by increasing the number of slides and the inactivation was observed to increase with increasing surface area. It was also observed that the immobilized catalyst slides can be used for several cycles leading to an economic process. The study shows potential application of TiO2, for the inactivation of bacteria, in its fixed form by a simple immobilization technique.

Improved velocity method for the determination of coefficient of consolidation

Parkin (1978) suggested the velocity method based on the observation that the theoretical rate of consolidation and time factor plot on a log-log scale yields an initial slope of 1:2 up to 50% consolidation. A new method is proposed that is an improvement over Parkin's velocity method because it minimizes the problems encountered in using that method. The results obtained agree with the other methods in use.

Vertical uplift capacity of horizontal anchors

The method of characteristics coupled with a log-spiral failure surface was used to develop a theory for vertical uplift capacity of shallow horizontal strip anchors in a general c-phi soil. Uplift-capacity factors F(c), F(q) and F(gamma), for the effects of cohesion, surcharge, and density, respectively, have been established as functions of embedment ratio lambda and angle of friction phi. The extent of the failure surface at the ground has also been determined. Comparisons made with existing test results support the predictive capability of the theory, and comparisons with the analysis proposed by Meyerhof and Adams show the proposed analysis provides slightly more conservative predictions of pullout capacity.

Bloch-Nordsieck thermometers: One-loop exponentiation in finite temperature QED

We study the scattering of hard external particles in a heat bath in a real-time formalism for finite temperature QED. We investigate the distribution of the 4-momentum difference of initial and final hard particles in a fully covariant manner when the scale of the process, Q, is much larger than the temperature, T. Our computations are valid for all T subject to this constraint. We exponentiate the leading infra-red term at one-loop order through a resummation of soft (thermal) photon emissions and absorptions. For T > 0, we find that tensor structures arise which are not present at T = 0. These carry thermal signatures. As a result, external particles can serve as thermometers introduced into the heat bath. We investigate the phase space origin of log (Q/M) and log (Q/T) terms.

Consolidation behavior of clayey soils under radial drainage

For Barren's degree of consolidation, U-r, versus the time factor, T-r, relationship for soils undergoing consolidation with radial drainage for the equal vertical strain condition, a simple method has been developed to determine the value of the coefficient of consolidation with radial drainage c(r). Theoretical log(10)(d(e)(2)/t) versus U-r curves where d(e) is the diameter of influence and r is the real time for the different known value of c(r) have been generated. A method has been developed wherein both the theoretical and experimental behaviors of soils undergoing consolidation with radial drainage can be simultaneously compared and studied on the same plot. The experimental log(10)(d(e)(2)/t) versus U-r curves have been compared with the theoretical curves. Effects of initial compression, secondary compression, and duration of load increment are studied. Simple procedures are presented for calculating the values of c(r) using the experimental log(10)(d(e)(2)/t) versus U-r curves. A comparative study of the coefficient of consolidation and the coefficient of permeability between the cases of vertical and radial drainage has been done.

Electrical transport studies in alkali borovanadate glasses

The ac conductivity and dielectric behaviors of sodium borovanadate glasses have been studied over wide ranges of composition and frequency. The de activation energies calculated from the complex impedance plots decrease linearly with the Na2O concentration, indicating that ionic conductivity dominates in these glasses. The possible origin of low-temperature departures of conductivity curves (from linearity) of vanadium-rich glasses in log sigma versus 1/T plots is discussed. The ac conductivities have been fitted to the Almond-West type power law expression with use of a single value of s. It is found that in most of the glasses s exhibits a temperature-dependent minimum. The dielectric data are converted into moduli (M*) and are analyzed using the Kohlrausch-William-Watts stretched exponential function, The activation barriers, W, calculated from the temperature-dependent dielectric loss peaks compare well with the activation barriers calculated from the de conductivity plots. The stretching exponent beta is found to be temperature independent and is not likely to be related as in the equation beta = 1 - s, An attempt is made to elucidate the origin of the stretching phenomena. It appears that either a model of the increased contribution of polarization energy (caused by the increased modifier concentration) and hence the increased monopole-induced dipole interactions or a model based on increased intercationic interactions can explain the slowing down of the primitive relaxation in ionically conducting glasses.

Variable Sparsity Kernel Learning

This paper(1) presents novel algorithms and applications for a particular class of mixed-norm regularization based Multiple Kernel Learning (MKL) formulations. The formulations assume that the given kernels are grouped and employ l(1) norm regularization for promoting sparsity within RKHS norms of each group and l(s), s >= 2 norm regularization for promoting non-sparse combinations across groups. Various sparsity levels in combining the kernels can be achieved by varying the grouping of kernels-hence we name the formulations as Variable Sparsity Kernel Learning (VSKL) formulations. While previous attempts have a non-convex formulation, here we present a convex formulation which admits efficient Mirror-Descent (MD) based solving techniques. The proposed MD based algorithm optimizes over product of simplices and has a computational complexity of O (m(2)n(tot) log n(max)/epsilon(2)) where m is no. training data points, n(max), n(tot) are the maximum no. kernels in any group, total no. kernels respectively and epsilon is the error in approximating the objective. A detailed proof of convergence of the algorithm is also presented. Experimental results show that the VSKL formulations are well-suited for multi-modal learning tasks like object categorization. Results also show that the MD based algorithm outperforms state-of-the-art MKL solvers in terms of computational efficiency.

Long term monitering of vegetation in a tropical deciduous forest in Mudumalai,southern India

As part of an international network of large plots to study tropical vegetation dynamics on a long-term basis, a 50-hectare permanent plot was set up during 1988-89 in the deciduous forests of Mudumalai, southern India. Within this plot 25,929 living woody plants (71 species) above 1 cm DBH (diameter at breast height) were identified, measured, tagged and mapped. Species abundances corresponded to the characteristic log-normal distribution. The four most abundant species (Kydia calycina, Lagerstroemia microcarpa, Terminalia crenulata and Helicteres isora) constituted nearly 56% of total stems, while seven species were represented by only one individual each in the plot. Variance/mean ratios of density showed most species to have clumped distributions. The population declined overall by 14% during the first two years, largely due to elephant and fire-mediated damage to Kydia calycina and Helicteres isora. In this article we discuss the need for large plots to study vegetation dynamics.

Hierarchies of circuit classes that are closed under complement

We examine three hierarchies of circuit classes and show they are closed under complementation. (1) The class of languages recognized by a family of polynomial size skew circuits with width O(w), are closed under complement. (2) The class of languages recognized by family of polynomial size circuits with width O(w) and polynomial tree-size, are closed under complement. (3) The class of languages recognized by a family of polynomial size, O(log(n)) depth, bounded AND fan-in with OR fan-in f (f⩾log(n)) circuits are closed under complement. These improve upon the results of (i) Immerman (1988) and Szelepcsenyi (1988), who show that 𝒩L𝒪𝒢 is closed under complementation, and (ii) Borodin et al. (1989), who show that L𝒪𝒢𝒞ℱL is closed under complement

Role of Li+ ions in corrosion behaviour of 8090 Al-Li alloy and aluminium in pH 12 aqueous solutions

The influence of Li+ ions on the corrosion behaviour of the Al-Li alloy 8090-T851 and of commercially pure aluminium in aqueous solutions at pH 12 was studied by weight loss and electrochemical polarisation methods. The inhibiting role of Li+ was concentration dependent, corrosion rate decreasing lineally with log[Li+] in the concentration range 10(-4)-10(-1) mol L(-1). A change from general to pitting corrosion was evident from scanning election microscopy studies. Polarisation studies revealed that Li+ primarily acts as an anodic inhibitor (passivator). Passive film formation and stability also become more feasible with increasing Li+ concentration. Fitting potential was dependent on the Cl- ion concentration in the solution. Both materials were affected similarly by the presence of Li+ ions, the corrosion rate of the alloy being slightly lower. This is attributed to the lithium in the alloy acting as a source of lithium for passive film formation. (C) 1995 The Institute of Materials.

Maintaining dynamic sequences under equality tests in polylogarithmic time

We present a randomized and a deterministic data structure for maintaining a dynamic family of sequences under equality tests of pairs of sequences and creations of new sequences by joining or splitting existing sequences. Both data structures support equality tests in O(1) time. The randomized version supports new sequence creations in O(log(2) n) expected time where n is the length of the sequence created. The deterministic solution supports sequence creations in O(log n (log m log* m + log n)) time for the mth operation.