We focus on energy complexity, a Boolean function measure related closely to Boolean circuit design. Given a circuit C over the standard basis { ∨ 2, ∧ 2, ¬ } , the energy complexity of C, denoted by EC(C), is the maximum number of its activated inner gates over all inputs. The energy complexity of a Boolean function f, denoted by EC(f), is the minimum of EC(C) over all circuits C computing f. Recently, K. Dinesh et al. (International computing and combinatorics conference, Springer, Berlin, 738–750, 2018) gave EC(f) an upper bound by the decision tree complexity, EC(f)=O(D(f)3). On the input size n, They also showed that EC(f) is at most 3 n- 1. For the lower bound side, they showed that EC(f)≥13psens(f), where psens(f) is called positive sensitivity. A remained open problem is whether the energy complexity of a Boolean function has a polynomial relationship with its decision tree complexity. Our results for energy complexity can be listed below.For the lower bound, we prove the equation that EC(f)=Ω(D(f)), which answers the above open problem.For upper bounds, EC(f)≤min{12D(f)2+O(D(f)),n+2D(f)-2} holds.For non-degenerated functions, we also provide another lower bound EC(f)=Ω(logn) where n is the input size.We also discuss the energy complexity of two specific function classes, OR functions and ADDRESS functions, which implies the tightness of our two lower bounds respectively. In addition, the former one answers another open question in Dinesh et al. (International computing and combinatorics conference, Springer, Berlin, 738–750, 2018) asking for non-trivial lower bound for energy complexity of OR functions.

Reversible Boolean function (RBF) is a one-to-one function which maps n-bit input to n-bit output. Reversible logic synthesis has been widely studied due to its connection with low-energy computation as well as quantum computation. In this paper, we give a structured decomposition for even RBFs. Specifically, for n≥q 6, any even n-bit RBF can be decomposed to 7 blocks of (n-1)-bit RBF, where 7 is a constant independent of n and the positions of these blocks have a large degree of freedom. Moreover, if the (n-1)-bit RBFs are required to be even as well, we show for n≥q 10, even n-bit RBF can be decomposed to 10 even (n-1)-bit RBFs. In short, our decomposition has block depth 7 and even block depth 10. Our result improves Selinger's work in block depth model, by reducing the constant from 9 to 7 and from 13 to 10, when the blocks are limited to be even. We emphasize that our setting is a bit different from Selinger's work. In Selinger's constructive proof, each block is placed in one of two specific positions and thus the decomposition has an alternating structure. We relax this restriction and allow each block to act on arbitrary (n-1) bits. This relaxation keeps the block structure and provides more candidates when choosing the positions of blocks.

Background

Body mass index (BMI) and diabetes are established risk factors for colorectal cancer (CRC), likely through perturbations in metabolic traits (e.g. insulin resistance and glucose homeostasis). Identification of interactions between variation in genes and these metabolic risk factors may identify novel biologic insights into CRC etiology.

Methods

To improve statistical power and interpretation for gene-environment interaction (G × E) testing, we tested genetic variants that regulate expression of a gene together for interaction with BMI (kg/m² ) and diabetes on CRC risk among 26 017 cases and 20 692 controls. Each variant was weighted based on PrediXcan analysis of gene expression data from colon tissue generated in the Genotype-Tissue Expression Project for all genes with heritability ≥1%. We used a mixed-effects model to jointly measure the G × E interaction in a gene by partitioning the interactions into the predicted gene expression levels (fixed effects), and residual G × E effects (random effects). G × BMI analyses were stratified by sex as BMI-CRC associations differ by sex. We used false discovery rates to account for multiple comparisons and reported all results with FDR <0.2.

Results

Among 4839 genes tested, genetically predicted expressions of FOXA1 (P = 3.15 × 10^-5 ), PSMC5 (P = 4.51 × 10^-4 ) and CD33 (P = 2.71 × 10^-4 ) modified the association of BMI on CRC risk for men; KIAA0753 (P = 2.29 × 10^-5 ) and SCN1B (P = 2.76 × 10^-4 ) modified the association of BMI on CRC risk for women; and PTPN2 modified the association between diabetes and CRC risk in both sexes (P = 2.31 × 10^-5 ).

Conclusions

Aggregating G × E interactions and incorporating functional information, we discovered novel genes that may interact with BMI and diabetes on CRC risk.