Lower bounds for testing triangle-freeness in Boolean functions

Given a Boolean function , we say a triple (x, y, x + y) is a triangle in f if . A triangle-free function contains no triangle. If f differs from every triangle-free function on at least points, then f is said to be -far from triangle-free. In this work, we analyze the query complexity of testers that, with constant probability, distinguish triangle-free functions from those -far from triangle-free. Let the canonical tester for triangle-freeness denotes the algorithm that repeatedly picks x and y uniformly and independently at random from , queries f(x), f(y) and f(x + y), and checks whether f(x) = f(y) = f(x + y) = 1. Green showed that the canonical tester rejects functions -far from triangle-free with constant probability if its query complexity is a tower of 2's whose height is polynomial in . Fox later improved the height of the tower in Green's upper bound to . A trivial lower bound of on the query complexity is immediate. In this paper, we give the first non-trivial lower bound for the number of queries needed. We show that, for every small enough , there exists an integer such that for all there exists a function depending on all n variables which is -far from being triangle-free and requires queries for the canonical tester. We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square root of the query complexity of the corresponding canonical tester. Consequently, this means that any one-sided tester for triangle-freeness must make at least queries.

Series-connected substrate-integrated lead-carbon hybrid ultracapacitors with voltage-management circuit

Cell voltage for a fully charged-substrate-integrated lead-carbon hybrid ultracapacitor is about 2.3 V. Therefore, for applications requiring higher DC voltage, several of these ultracapacitors need to be connected in series. However, voltage distribution across each series-connected ultracapacitor tends to be uneven due to tolerance in capacitance and parasitic parallel-resistance values. Accordingly, voltage-management circuit is required to protect constituent ultracapacitors from exceeding their rated voltage. In this study, the design and characterization of the substrate-integrated lead-carbon hybrid ultracapacitor with co-located terminals is discussed. Voltage-management circuit for the ultracapacitor is presented, and its effectiveness is validated experimentally.

Fabrication of back contacts using laser writer and photolithography for inscribing textured solar cells

Semiconductor fabrication process begins with photolithography. Preparing a photo mask is the key process step in photolithography. The photo mask was fabricated by inscribing patterns directly onto a soda lime glass with the help of a laser beam, as it is easily controllable. Laser writer LW405-A was used for preparing the mask in this study. Exposure wavelength of 405 nm was used, with which 1.2 mu m feature size can be written in direct write-mode over the soda lime glass plate. The advantage of using the fabricated mask is that it can be used to design back contacts for thin film Photovoltaic (PV) solar cells. To investigate the process capability of LW405-A, same pattern with different line widths was written on soda lime glass samples at different writing speeds. The pattern was inscribed without proximity effect and stitching errors, which was characterized using optical microscope and field emission scanning electron microscope (FE-SEM). It was proven that writing speed of a mask-writer is decided according to the intended feature size and line width. As the writing speed increases, the edges of the patterns become rougher due to uneven scattering of the laser beam. From the fabricated mask, the solar cell can be developed embedding both the contacts at the bottom layer, to increase the absorption of solar radiation on the top surface effectively by increasing light absorption area.

Modification of crosslinked chitosan membrane using NaY zeolite for pervaporation separation of water-isopropanol mixtures

The blocked diisocyanate crosslinked chitosan membrane was modified by incorporating different mass% of NaY zeolite. The physico-chemical properties of resulting composite membranes were studied using Fourier transform infrared spectroscopy (FTIR), wide-angle X-ray diffraction (WAXD), thermogravimetric analysis (TGA), differential scanning calorimetry (DSC) and scanning electron microscopy (SEM). The mechanical properties of the membranes were studied using universal testing machine (UTM). After measuring the equilibrium swelling, membranes were subjected to pervaporation for separation of water-isopropanol mixtures. Both flux and selectivity were increased with increasing NaY zeolite content in the membranes. The membrane containing 40 mass% of NaY zeolite exhibited the highest separation selectivity of 11,241 with a flux of 11.37 x 10(-2) kg/m(2) h for 10 mass% of water in the feed. The total flux and flux of water are almost overlapping each other, suggesting that these membranes could be effectively used to break the azeotropic point of water-isopropanol mixture. From the temperature dependent diffusion and permeation values, the Arrhenius activation parameters were estimated. All the composite membranes exhibited lower activation energy compared to crosslinked membrane, indicating that the permeants require less energy during the process because of molecular sieving action attributed to the presence of sodalite and super cages in the framework of Nay zeolite. The Henry's mode of sorption dominates the process, giving an endothermic contribution. (C) 2014 The Institution of Chemical Engineers. Published by Elsevier B.V. All rights reserved.

Modeling of solar radiation management: a comparison of simulations using reduced solar constant and stratospheric sulphate aerosols

The climatic effects of Solar Radiation Management (SRM) geoengineering have been often modeled by simply reducing the solar constant. This is most likely valid only for space sunshades and not for atmosphere and surface based SRM methods. In this study, a global climate model is used to evaluate the differences in the climate response to SRM by uniform solar constant reduction and stratospheric aerosols. Our analysis shows that when global mean warming from a doubling of CO2 is nearly cancelled by both these methods, they are similar when important surface and tropospheric climate variables are considered. However, a difference of 1 K in the global mean stratospheric (61-9.8 hPa) temperature is simulated between the two SRM methods. Further, while the global mean surface diffuse radiation increases by similar to 23 % and direct radiation decreases by about 9 % in the case of sulphate aerosol SRM method, both direct and diffuse radiation decrease by similar fractional amounts (similar to 1.0 %) when solar constant is reduced. When CO2 fertilization effects from elevated CO2 concentration levels are removed, the contribution from shaded leaves to gross primary productivity (GPP) increases by 1.8 % in aerosol SRM because of increased diffuse light. However, this increase is almost offset by a 15.2 % decline in sunlit contribution due to reduced direct light. Overall both the SRM simulations show similar decrease in GPP (similar to 8 %) and net primary productivity (similar to 3 %). Based on our results we conclude that the climate states produced by a reduction in solar constant and addition of aerosols into the stratosphere can be considered almost similar except for two important aspects: stratospheric temperature change and the consequent implications for the dynamics and the chemistry of the stratosphere and the partitioning of direct versus diffuse radiation reaching the surface. Further, the likely dependence of global hydrological cycle response on aerosol particle size and the latitudinal and height distribution of aerosols is discussed.

Modifications in Trypsin Digestion Protocol for Increasing the Efficiency and Coverage

Standard trypsin digestion protocol of proteins followed by MALDI-MS analysis has been realized as an important tool for the identification and characterization of proteins. In this article, we proposed the elimination of the step of `staining/de-staining of gel pieces' in in-gel digestion protocol in order to improve the efficiency of trypsin digestion. Coomassie dye is known to interfere with digestion of proteins by trypsin and the procedure of staining-de-staining could result in loss of photoaffinity probe, post translational modifications and catalytic activities of enzymes. Further, we studied parameters like hydrophobicity and isoelectric point, and attempted to quantitatively relate it to the efficiency of trypsin digestion. We suggest that properties of proteins should be considered and trypsin digestion protocol should be appropriately modified as per sequence and other information.

Phase stability of silver particles embedded calcium phosphate bioceramics

In this paper, we report the compositional variation-dependent phase stability of hydroxyapatite (Ca-10(PO4)(6)(OH)(2)) on doping with silver. The transformation of hydroxyapatite to (beta/alpha) tricalcium phosphate phases during sintering has been explored using Raman spectroscopy and X-ray diffraction techniques. The optical absorption spectroscopy analysis reveals the presence of Ag+ ions at low doping levels. As the doping increases, abundance of Ag particles is enhanced.

A Family of Domains Associated with mu-Synthesis

We introduce a family of domains-which we call the -quotients-associated with an aspect of -synthesis. We show that the natural association that the symmetrized polydisc has with the corresponding spectral unit ball is also exhibited by the -quotient and its associated unit `` -ball''. Here, is the structured singular value for the case Specifically: we show that, for such an E, the Nevanlinna-Pick interpolation problem with matricial data in a unit `` -ball'', and in general position in a precise sense, is equivalent to a Nevanlinna-Pick interpolation problem for the associated -quotient. Along the way, we present some characterizations for the -quotients.

Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph G. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of G - the minimum number of distinct colors occurring at edges incident to any vertex of G - denoted by v(G). Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph G would be 2v(G)/3]. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph G is at least v(G) - 1, if 1 <= v(G) <= 7, and at least 3v(G)/5] + 1 if v(G) >= 8. They conjectured that the tight lower bound would be v(G) - 1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if v(G) >= 8, then G contains a heterochromatic path of length at least 120 + 1. In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if G has no four cycles, then it contains a heterochromatic path of length at least v(G) - o(v(G)) and if the girth of G is at least 4 log(2)(v(G)) + 2, then it contains a heterochromatic path of length at least v(G) - 2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of 5v(G)/6] and for bipartite graphs we obtain a lower bound of 6v(G)-3/7]. In this paper, it is also shown that if the coloring is such that G has no heterochromatic triangles, then G contains a heterochromatic path of length at least 13v(G)/17)]. This improves the previously known 3v(G)/4] bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph G contains a heterochromatic path of length at least (C) 2015 Elsevier Ltd. All rights reserved.

Estimation of Aboveground Phytomass of Plantations Using Digital Photogrammetry and High Resolution Remote Sensing Data

The study follows an approach to estimate phytomass using recent techniques of remote sensing and digital photogrammetry. It involved tree inventory of forest plantations in Bhakra forest range of Nainital district. Panchromatic stereo dataset of Cartosat-1 was evaluated for mean stand height retrieval. Texture analysis and tree-tops detection analyses were done on Quick-Bird PAN data. The composite texture image of mean, variance and contrast with a 5x5 pixel window was found best to separate tree crowns for assessment of crown areas. Tree tops count obtained by local maxima filtering was found to be 83.4 % efficient with an RMSE+/-13 for 35 sample plots. The predicted phytomass ranged from 27.01 to 35.08 t/ha in the case of Eucalyptus sp. while in the case of Tectona grandis from 26.52 to 156 t/ha. The correlation between observed and predicted phytomass in Eucalyptus sp. was 0.468 with an RMSE of 5.12. However, the phytomass predicted in Tectona grandis was fairly strong with R-2=0.65 and RMSE of 9.89 as there was no undergrowth and the crowns were clearly visible. Results of the study show the potential of Cartosat-1 derived DSM and Quick-Bird texture image for the estimation of stand height, stem diameter, tree count and phytomass of important timber species.

HIF-1 alpha (1772C > T) polymorphism as marker for breast cancer development

Hypoxia-inducible factor 1 alpha (HIF-1 alpha) is an important transcription factor that regulates different cellular responses to hypoxia. HIF-1 alpha is rapidly degraded by von Hippel-Lindau (VHL) protein under normoxic conditions and stabilized under hypoxia. A common variant of HIF-1 alpha (1772C > T) (rs 11549465) polymorphism, corresponding to an amino acid change from proline to serine at 582 position within the oxygen-dependent degradation domain, results in increased stability of the protein and altered transactivation of its target genes. The present study was aimed to find the association between HIF-1 alpha (1772C > T) (rs 11549465) polymorphism and breast cancer development. For this purpose, 348 primary breast cancer patients and 320 healthy and age-matched controls were genotyped through PCR-RFLP method. The genotype frequencies were compared between patients and controls, and their influence on clinical characteristics of breast cancer patients was analyzed. Our study revealed a significant increase of TT genotype in breast cancer patients compared to controls (p = 0.038). Further, TT genotype and T allele were found to be associated with progesterone receptor (PR)-negative status (p < 0.09). None of the clinical variables revealed significant association with HIF-1 alpha (1772C > T) (rs 11549465) polymorphism.

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

Autonomous Star Camera Calibration and Spacecraft Attitude Determination

This paper presents two methods of star camera calibration to determine camera calibrating parameters (like principal point, focal length etc) along with lens distortions (radial and decentering). First method works autonomously utilizing star coordinates in three consecutive image frames thus independent of star identification or biased attitude information. The parameters obtained in autonomous self-calibration technique helps to identify the imaged stars with the cataloged stars. Least Square based second method utilizes inertial star coordinates to determine satellite attitude and star camera parameters with lens radial distortion, both independent of each other. Camera parameters determined by the second method are more accurate than the first method of camera self calibration. Moreover, unlike most of the attitude determination algorithms where attitude of the satellite depend on the camera calibrating parameters, the second method has the advantage of computing spacecraft attitude independent of camera calibrating parameters except lens distortions (radial). Finally Kalman filter based sequential estimation scheme is employed to filter out the noise of the LS based estimation.

Synergistic effect of colchicine and iodide ions on the corrosion of mild steel in 0.5 M H2SO4

The inhibition behavior of colchicine (CC) on the corrosion of mild steel in 0.5 M H2SO4 was evaluated by electrochemical methods such as potentiodynamic polarization and electrochemical impedance spectroscopic measurements. The inhibition efficiency increases with increasing concentration of CC. The potentiodynamic polarization results reveal that CC act as a mixed-type inhibitor by retarding both cathodic and anodic corrosion reactions. Additionally, the synergism was carried out between CC and KI to improve the corrosion inhibition behavior of CC on mild steel. The adsorption of both CC alone and the combined inhibitor (CC + KI) on mild steel surface follows Langmuir adsorption isotherm. The synergism parameter (S (theta) ) was calculated to recognize the existence of synergism between CC and iodide ions. Lastly, an adsorption mechanism of CC molecules with iodide ions is discussed.

Synthetic image super resolution using FeatureMatch

In this paper, we propose a super resolution (SR) method for synthetic images using FeatureMatch. Existing state-of-the-art super resolution methods are learning based methods, where a pair of low-resolution and high-resolution dictionary pair are trained, and this trained pair is used to replace patches in low-resolution image with appropriate matching patches from the high-resolution dictionary. In this paper, we show that by using Approximate Nearest Neighbour Fields (ANNF), and a common source image, we can by-pass the learning phase, and use a single image for dictionary. Thus, reducing the dictionary from a collection obtained from hundreds of training images, to a single image. We show that by modifying the latest developments in ANNF computation, to suit super resolution, we can perform much faster and more accurate SR than existing techniques. To establish this claim we will compare our algorithm against various state-of-the-art algorithms, and show that we are able to achieve better and faster reconstruction without any training phase.