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.

Typical and atypical domain combinations in human protein kinases: functions, disease causing mutations and conservation in other primates

Ser/Thr and Tyr protein kinases orchestrate many signalling pathways and hence loss in this balance leads to many disease phenotypes. Due to their high abundance, diversity and importance, efforts have been made in the past to classify kinases and annotate their functions at both gross and fine levels. These kinases are conventionally classified into subfamilies based on the sequences of catalytic domains. Usually the domain architecture of a full-length kinase is consistent with the subfamily classification made based on the sequence of kinase domain. Important contributions of modular domains to the overall function of the kinase are well known. Recently occurrence of two kinds of outlier kinases-''Hybrid'' and ``Rogue'' has been reported. These show considerable deviations in their domain architectures from the typical domain architecture known for the classical kinase subfamilies. This article provides an overview of the different subfamilies of human kinases and the role of non-kinase domains in functions and diseases. Importantly this article provides analysis of hybrid and rogue kinases encoded in the human genome and highlights their conservation in closely related primate species. These kinases are examples of elegant rewiring to bring about subtle functional differences compared to canonical variants.

Novel Functions of (p)ppGpp and Cyclic di-GMP in Mycobacterial Physiology Revealed by Phenotype Microarray Analysis of Wild-Type and Isogenic Strains of Mycobacterium smegmatis

The bacterial second messengers (p)ppGpp and bis-(3'-5')-cyclic dimeric GMP (c-di-GMP) regulate important functions, such as transcription, virulence, biofilm formation, and quorum sensing. In mycobacteria, they regulate long-term survival during starvation, pathogenicity, and dormancy. Recently, a Pseudomonas aeruginosa strain lacking (p) ppGpp was shown to be sensitive to multiple classes of antibiotics and defective in biofilm formation. We were interested to find out whether Mycobacterium smegmatis strains lacking the gene for either (p)ppGpp synthesis (Delta rel(Msm)) or c-di-GMP synthesis (Delta dcpA) would display similar phenotypes. We used phenotype microarray technology to compare the growth of the wild-type and the knockout strains in the presence of several antibiotics. Surprisingly, the Delta rel(Msm) and Delta dcpA strains showed enhanced survival in the presence of many antibiotics, but they were defective in biofilm formation. These strains also displayed altered surface properties, like impaired sliding motility, rough colony morphology, and increased aggregation in liquid cultures. Biofilm formation and surface properties are associated with the presence of glycopeptidolipids (GPLs) in the cell walls of M. smegmatis. Thin-layer chromatography analysis of various cell wall fractions revealed that the levels of GPLs and polar lipids were reduced in the knockout strains. As a result, the cell walls of the knockout strains were significantly more hydrophobic than those of the wild type and the complemented strains. We hypothesize that reduced levels of GPLs and polar lipids may contribute to the antibiotic resistance shown by the knockout strains. Altogether, our data suggest that (p)ppGpp and c-di-GMP may be involved in the metabolism of glycopeptidolipids and polar lipids in M. smegmatis.

A faster algorithm for testing polynomial representability of functions over finite integer rings

Given a function from Z(n) to itself one can determine its polynomial representability by using Kempner function. In this paper we present an alternative characterization of polynomial functions over Z(n) by constructing a generating set for the Z(n)-module of polynomial functions. This characterization results in an algorithm that is faster on average in deciding polynomial representability. We also extend the characterization to functions in several variables. (C) 2015 Elsevier B.V. All rights reserved.

Functions for rice RFL in vegetative axillary meristem specification and outgrowth

Roles for the transcription factor RFL in rice axillary meristem development were studied. Its regulatory effects on LAX1, CUC1, and OsPIN3 reveal its functions in axillary meristem specification and outgrowth.Axillary meristems (AMs) are secondary shoot meristems whose outgrowth determines plant architecture. In rice, AMs form tillers, and tillering mutants reveal an interplay between transcription factors and the phytohormones auxin and strigolactone as some factors that underpin this developmental process. Previous studies showed that knockdown of the transcription factor gene RFL reduced tillering and caused a very large decrease in panicle branching. Here, the relationship between RFL, AM initiation, and outgrowth was examined. We show that RFL promotes AM specification through its effects on LAX1 and CUC genes, as their expression was modulated on RFL knockdown, on induction of RFL:GR fusion protein, and by a repressive RFL-EAR fusion protein. Further, we report reduced expression of auxin transporter genes OsPIN1 and OsPIN3 in the culm of RFL knockdown transgenic plants. Additionally, subtle change in the spatial pattern of IR4 DR5:GFP auxin reporter was observed, which hints at compromised auxin transport on RFL knockdown. The relationship between RFL, strigolactone signalling, and bud outgrowth was studied by transcript analyses and by the tillering phenotype of transgenic plants knocked down for both RFL and D3. These data suggest indirect RFL-strigolactone links that may affect tillering. Further, we show expression modulation of the auxin transporter gene OsPIN3 upon RFL:GR protein induction and by the repressive RFL-EAR protein. These modified forms of RFL had only indirect effects on OsPIN1. Together, we have found that RFL regulates the LAX1 and CUC genes during AM specification, and positively influences the outgrowth of AMs though its effects on auxin transport.

Outer Bounds on the Secrecy Rate of the 2-User Symmetric Deterministic Interference Channel with Transmitter Cooperation

This paper derives outer bounds for the 2-user symmetric linear deterministic interference channel (SLDIC) with limited-rate transmitter cooperation and perfect secrecy constraints at the receivers. Five outer bounds are derived, under different assumptions of providing side information to receivers and partitioning the encoded message/output depending on the relative strength of the signal and the interference. The usefulness of these outer bounds is shown by comparing the bounds with the inner bound on the achievable secrecy rate derived by the authors in a previous work. Also, the outer bounds help to establish that sharing random bits through the cooperative link can achieve the optimal rate in the very high interference regime.

A hidden symmetry of AdS resonances

Recent investigations have revealed powerful selection rules for resonant energy transfer between modes of nonlinear perturbations in global anti-de Sitter (AdS) space-time. It is likely that these selection rules are due to the highly symmetric nature of the underlying AdS background, though the precise relation has remained unclear. In this article, we demonstrate that the equation satisfied by the scalar field mode functions in AdS(d+1) has a hidden SU(d) symmetry, and explicitly specify the multiplets of this SU(d) symmetry furnished by the mode functions. We also comment on the role this structure might play in explaining the selection rules.

Symmetric Supercapacitor Based on Reduced Graphene Oxide in Non-Aqueous Electrolyte

Reduced graphene oxide (RGO) is prepared by thermal exfoliation of graphite oxide in air. Symmetric RGO/RGO supercapacitors are constructed in a non-aqueous electrolyte and characterized. The values of energy density are 44 Wh kg(-1) and 15 Wh kg(-1), respectively at 0.15 and 8.0 kW kg(-1). The symmetric supercapacitor exhibits stable charge/discharge cycling tested up to 3000 cycles. The low-temperature thermal exfoliation approach is convenient for mass production of RGO at low cost and it can be used as electrode material for energy storage applications. (c) The Author(s) 2015. Published by ECS. All rights reserved.

Splicing Functions and Global Dependency on Fission Yeast Slu7 Reveal Diversity in Spliceosome Assembly

The multiple short introns in Schizosaccharomyces pombe genes with degenerate cis sequences and atypically positioned polypyrimidine tracts make an interesting model to investigate canonical and alternative roles for conserved splicing factors. Here we report functions and interactions of the S. pombe slu7(+) (spslu7(+)) gene product, known from Saccharomyces cerevisiae and human in vitro reactions to assemble into spliceosomes after the first catalytic reaction and to dictate 3' splice site choice during the second reaction. By using a missense mutant of this essential S. pombe factor, we detected a range of global splicing derangements that were validated in assays for the splicing status of diverse candidate introns. We ascribe widespread, intron-specific SpSlu7 functions and have deduced several features, including the branch nucleotide-to-3' splice site distance, intron length, and the impact of its A/U content at the 5' end on the intron's dependence on SpSlu7. The data imply dynamic substrate-splicing factor relationships in multiintron transcripts. Interestingly, the unexpected early splicing arrest in spslu7-2 revealed a role before catalysis. We detected a salt-stable association with U5 snRNP and observed genetic interactions with spprp1(+), a homolog of human U5-102k factor. These observations together point to an altered recruitment and dependence on SpSlu7, suggesting its role in facilitating transitions that promote catalysis, and highlight the diversity in spliceosome assembly.

Inner Bound on the GDOF of the K-User MIMO Gaussian Symmetric Interference Channel

The K-user multiple input multiple output (MIMO) Gaussian symmetric interference channel where each transmitter has M antennas and each receiver has N antennas is studied from a generalized degrees of freedom (GDOF) perspective. An inner bound on the GDOF is derived using a combination of techniques such as treating interference as noise, zero forcing (ZF) at the receivers, interference alignment (IA), and extending the Han-Kobayashi (HK) scheme to K users, as a function of the number of antennas and the log INR/log SNR level. Several interesting conclusions are drawn from the derived bounds. It is shown that when K > N/M + 1, a combination of the HK and IA schemes performs the best among the schemes considered. When N/M < K <= N/M + 1, the HK-scheme outperforms other schemes and is found to be GDOF optimal in many cases. In addition, when the SNR and INR are at the same level, ZF-receiving and the HK-scheme have the same GDOF performance.

Average Overlap for Clustering Incomplete Data using Symmetric Non-Negative Matrix Factorization

Clustering techniques which can handle incomplete data have become increasingly important due to varied applications in marketing research, medical diagnosis and survey data analysis. Existing techniques cope up with missing values either by using data modification/imputation or by partial distance computation, often unreliable depending on the number of features available. In this paper, we propose a novel approach for clustering data with missing values, which performs the task by Symmetric Non-Negative Matrix Factorization (SNMF) of a complete pair-wise similarity matrix, computed from the given incomplete data. To accomplish this, we define a novel similarity measure based on Average Overlap similarity metric which can effectively handle missing values without modification of data. Further, the similarity measure is more reliable than partial distances and inherently possesses the properties required to perform SNMF. The experimental evaluation on real world datasets demonstrates that the proposed approach is efficient, scalable and shows significantly better performance compared to the existing techniques.

Simultaneous nonvanishing of Dirichlet L-functions and twists of Hecke-Maass L-functions

We prove that given a Hecke-Maass form f for SL(2, Z) and a sufficiently large prime q, there exists a primitive Dirichlet character chi of conductor q such that the L-values L(1/2, f circle times chi) and L(1/2, chi) do not vanish.

An Open-End winding IM drive with Multilevel 12-sided Polygonal Vectors with Symmetric Triangles

Multilevel inverters with hexagonal voltage space vector structures have improved performance of induction motor drives compared to that of the two level inverters. Further reduction in the torque ripple on the motor shaft is possible by using multilevel dodecagonal (12-sided polygon) voltage space vector structures. The advantages of dodecagonal voltage space vector based PWM techniques are the complete elimination of fifth and seventh harmonics in phase voltages for the full modulation range and the extension of linear modulation range. This paper proposes an inverter circuit topology capable of generating multilevel dodecagonal voltage space vectors with symmetric triangles, by cascading two asymmetric three level inverters with isolated H-Bridges. This is made possible by proper selection of DC link voltages and the selection of resultant switching states for the inverters. In this paper, a simple PWM timing calculation method is proposed. Experimental results have also been presented in this paper to validate the proposed concept.

Thermalization of Green functions and quasinormal modes

We develop a new method to study the thermalization of time dependent retarded Green function in conformal field theories holographically dual to thin shell AdS Vaidya space times. The method relies on using the information of all time derivatives of the Green function at the shell and then evolving it for later times. The time derivatives of the Green function at the shell is given in terms of a recursion formula. Using this method we obtain analytic results for short time thermalization of the Green function. We show that the late time behaviour of the Green function is determined by the first quasinormal mode. We then implement the method numerically. As applications of this method we study the thermalization of the retarded time dependent Green function corresponding to a minimally coupled scalar in the AdS 3 and AdS 5 thin Vaidya shells. We see that as expected the late time behaviour is determined by the first quasinormal mode. We apply the method to study the late time behaviour of the shear vector mode in AdS 5 Vaidya shell. At small momentum the corresponding time dependent Green function is expected to relax to equilibrium by the shear hydrodynamic mode. Using this we obtain the universal ratio of the shear viscosity to entropy density from a time dependent process.