On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities

Let S⊂ℝ ^k+m be a compact semi-algebraic set defined by P ₁≥0,…,P _ℓ ≥0, where P _i ∈ℝ[X ₁,…,X _k ,Y ₁,…,Y _m ], and deg (P _i )≤2, 1≤i≤ℓ. Let π denote the standard projection from ℝ ^k+m onto ℝ ^m . We prove that for any q>0, the sum of the first q Betti numbers of π(S) is bounded by (k+m) ^{O(q ℓ)}. We also present an algorithm for computing the first q Betti numbers of π(S), whose complexity is . For fixed q and ℓ, both the bounds are polynomial in k+m. The author was supported in part by an NSF Career Award 0133597 and a Sloan Foundation Fellowship.     

In Vitro Renaturation of Alkaline Family G/11 Xylanase via a Folding Intermediate: α-Crystallin Facilitates Refolding in an ATP-Independent Manner

In this study, alkaliphilic family G/11 xylanase from alkali-tolerant filamentous fungi Penicillium citrinum MTCC 6489 was used as a model system to gain insight into the molecular aspects of unfolding/refolding of alkaliphilic glycosyl hydrolase protein family. The intrinsic protein fluorescence suggested a putative intermediate state of protein in presence of 2 M guanidium hydrochloride (GdmCl) with an emission maximum of 353 nm. Here we studied the refolding of GdmCl-denatured alkaline xylanase in the presence and the absence of a multimeric chaperone protein α-crystallin to elucidate the molecular mechanism of intramolecular interactions of the alkaliphilic xylanase protein that dictates its extremophilic character. Our results, based on intrinsic tryptophan fluorescence and hydrophobic fluorophore 8-anilino-1- naphthalene sulfonate-binding studies, suggest that α-crystallin formed a complex with a putative molten globule-like intermediate in the refolding pathway of xylanase in an ATP-independent manner. A 2 M GdmCl is sufficient to denature alkaline xylanase completely. The hydrodynamic radius (R_H) of a native alkaline xylanase is 4.0, which becomes 5.0 in the presence of 2 M GdmCl whereas in presence of the higher concentration of GdmCl R_H value was shifted to 100, indicating the aggregation of denatured xylanase. The α-crystallin·xylanase complex exhibited the recovery of functional activity with the extent of ~43%. Addition of ATP to the complex did not show any significant effect on activity recovery of the denatured protein.     

A Complex Analogue of Toda’s Theorem

Toda (SIAM J. Comput. 20(5):865–877, 1991) proved in 1989 that the (discrete) polynomial time hierarchy, PH, is contained in the class P ^#P , namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class #P. This result, which illustrates the power of counting, is considered to be a seminal result in computational complexity theory. An analogous result (with a compactness hypothesis) in the complexity theory over the reals (in the sense of Blum–Shub–Smale real machines (Blum et al. in Bull. Am. Math. Soc. 21(1):1–46, 1989) was proved in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010). Unlike Toda’s proof in the discrete case, which relied on sophisticated combinatorial arguments, the proof in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010) is topological in nature; the properties of the topological join are used in a fundamental way. However, the constructions used in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010) were semi-algebraic—they used real inequalities in an essential way and as such do not extend to the complex case. In this paper, we extend the techniques developed in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010) to the complex projective case. A key role is played by the complex join of quasi-projective complex varieties. As a consequence, we obtain a complex analogue of Toda’s theorem. The results of this paper, combined with those in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010), illustrate the central role of the Poincaré polynomial in algorithmic algebraic geometry, as well as in computational complexity theory over the complex and real numbers: the ability to compute it efficiently enables one to decide in polynomial time all languages in the (compact) polynomial hierarchy over the appropriate field.