Bioinformatics analysis and visualization of high-throughput gene expression data require extensive computer programming skills, posing a bottleneck for many wet-lab scientists. In this work, we present an intuitive user-friendly platform for gene expression data analysis and visualization called FungiExpresZ. FungiExpresZ aims to help wet-lab scientists with little to no knowledge of computer programming to become self-reliant in bioinformatics analysis and generating publication-ready figures. The platform contains many commonly used data analysis tools and an extensive collection of pre-processed public ribonucleic acid sequencing (RNA-seq) datasets of many fungal species, including important human, plant and insect pathogens. Users may analyse their data alone or in combination with public RNA-seq data for an integrated analysis. The FungiExpresZ platform helps wet-lab scientists to overcome their limitations in genomics data analysis and can be applied to analyse data of any organism. FungiExpresZ is available as an online web-based tool (https://cparsania.shinyapps.io/FungiExpresZ/) and an offline R-Shiny package (https://github.com/cparsania/FungiExpresZ).

We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is epsilon_d > 0 such that Parity has correlation at most 1/n^{Omega(1)} with depth-d threshold circuits which have at most n^{1+epsilon_d} wires, and the Generalized Andreev Function has correlation at most 1/2^{n^{Omega(1)}} with depth-d threshold circuits which have at most n^{1+epsilon_d} wires. Previously, only worst-case lower bounds in this setting were known [Impagliazzo/Paturi/Saks, SIAM J. Comp., 1997]. We use our ideas to make progress on several related questions. We give satisfiability algorithms beating brute force search for depth-$d$ threshold circuits with a superlinear number of wires. These are the first such algorithms for depth greater than 2. We also show that Parity cannot be computed by polynomial-size AC^0 circuits with n^{o(1)} general threshold gates. Previously no lower bound for Parity in this setting could handle more than log(n) gates. This result also implies subexponential-time learning algorithms for AC^0 with n^{o(1)} threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depth-d threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas ofany depth. Our techniques include adaptive random restrictions, anti-concentration and the structural theory of linear threshold functions, and bounded-read Chernoff bounds.

The study of the worst-case complexity of the Boolean Satisfiability (SAT) problem has seen considerable progress in recent years, for various types of instances including CNFs, Boolean formulas and constant-depth circuits. We systematically investigate the complexity of solving mixed instances, where different parts of the instance come from different types. Our investigation is motivated partly by practical contexts such as SMT (Satisfiability Modulo Theories) solving, and partly by theoretical issues such as the exact complexity of graph problems and the desire to find a unifying framework for known satisfiability algorithms.

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for “easy” Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an n-variate Boolean function f computable by some unknown small circuit from a known class of circuits, find in deterministic time poly(2n) a circuit C (no restriction on the type of C) computing f so that the size of C is less than the trivial circuit size 2n/n. We get nontrivial compression for functions computable by AC0circuits, (de Morgan) formulas, and (read-once) branching programs of the size for which the lower bounds for the corresponding circuit class are known. These compression algorithms rely on the structural characterizations of “easy” functions, which are useful both for proving circuit lower bounds and for designing “meta-algorithms” (such as Circuit-SAT). For (de Morgan) formulas, such structural characterization is provided by the “shrinkage under random restrictions” results [52], [21], strengthened to the “high-probability” version by [48], [26], [33]. We give a new, simple proof of the “high-probability” version of the shrinkage result for (de Morgan) formulas, with improved parameters. We use this shrinkage result to get both compression and #SAT algorithms for (de Morgan) formulas of size about n2. We also use this shrinkage result to get an alternative proof of the recent result by Komargodski and Raz [33] of the average-case lower bound against small (de Morgan) formulas. Finally, we show that the existence of any non-trivial compression algorithm for a circuit class C ⊆ P/poly would imply the circuit lower bound NEXP ⊈ C. This complements Williams's result [55] that any non-trivial Circuit-SAT algorithm for a circuit class C would imply a superpolynomial lower bound against C for a language in NEXP1.

Massive graphs emerge in many real-world applications. Practitioners often find relational databases are inefficient in graph data management. In this paper, we investigate the efficiency issue by analyzing both I/O and CPU costs. First, we find the storage of a graph in relational DBMS violates the locality principle: graph queries will always reference neighbors; however, the data locations of neighbors are almost random. To solve this problem, we introduce partitioned graph storage as a new database design option. It combines database partitioning with available graph-partitioning algorithms to restructure the storage such that neighbors are located close to each other. Second, we find graph queries expressed with SQL introduce unnecessary overheads. To overcome the CPU costs, we propose a new storage access method, which we call graph scan, to retrieve neighbors in one single operation. We show experimentally that partitioned graph storage and graph scan can significantly reduce I/O and CPU costs. We conclude that a relational DBMS could be a good graph store, as long as the storage respects the locality principle and SQL overheads are eliminated.

Under the tuple-level uncertainty paradigm, we introduce a novel graphical model, Generator-Recognizer Network (GRN), as a model for probabilistic databases. The GRN modeling framework extends existing graphical models of probabilistic databases and is capable of representing a much wider range of dependence structures.

Under the tuple-level uncertainty paradigm, we formalize the use of a novel graphical model, Generator-Recognizer Network (GRN), as a model of probabilistic databases. The GRN modeling framework is capable of representing a much wider range of tuple dependency structure. We show that a GRN representation of a probabilistic database may undergo transitions induced by imposing constraints or evaluating queries. We formalize procedures for these two types of transitions such that the resulting graphical models after transitions remain as GRNs. This formalism makes GRN a self-contained modeling framework and a closed representation system for probabilistic databases - a property that is lacking in most existing models. In addition, we show that exploiting the transitional mechanisms allows a systematic approach to constructing GRNs for arbitrary probabilistic data at arbitrary stages. Advantages of GRNs in query evaluation are also demonstrated.