We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tests better than bounded uniformity. We prove this for threshold tests, small-space algorithms, and small-depth circuits. In particular, we obtain small-bias distributions that - achieve an optimal lower bound on their statistical distance to any bounded-uniform distribution. This closes a line of research initiated by Alon, Goldreich, and Mansour in 2003, and improves on a result by O'Donnell and Zhao. - have heavier tail mass than the uniform distribution. This answers a question posed by several researchers including Bun and Steinke. - rule out a popular paradigm for constructing pseudorandom generators, originating in a 1989 work by Ajtai and Wigderson. This again answers a question raised by several researchers. For branching programs, our result matches a bound by Forbes and Kelley. Our small-bias distributions above are symmetric. We show that the xor of any two symmetric small-bias distributions fools any bounded function. Hence our examples cannot be extended to the xor of two small-bias distributions, another popular paradigm whose power remains unknown. We also generalize and simplify the proof of a result of Bazzi.

We study the communication complexity of multiplying$k\times t$elements from the group$H$= SL$(2, q)$in the number-on-forehead model with$k$parties. We prove a lower bound of$(t\log H)/c^{k}$. This is an exponential improvement over previous work, and matches the state-of-the-art in the area. Relatedly, we show that the convolution of$k^{c}$independent copies of a 3-uniform distribution over$H^{m}$is close to a$k$- uniform distribution. This is again an exponential improvement over previous work which needed$c^{k}$copies. The proofs are remarkably simple; the results extend to other quasirandom groups. We also show that for any group$LI$, any distribution over$H^{m}$whose weight-k Fourier coefficients are small is close to a k-uniform distribution. This generalizes previous work in the abelian setting, and the proof is simpler.

A model's interpretability is essential to many practical applications such as clinical decision support systems. In this article, a novel interpretable machine learning method is presented, which can model the relationship between input variables and responses in humanly understandable rules. The method is built by applying tropical geometry to fuzzy inference systems, wherein variable encoding functions and salient rules can be discovered by supervised learning. Experiments using synthetic datasets were conducted to demonstrate the performance and capacity of the proposed algorithm in classification and rule discovery. Furthermore, we present a pilot application in identifying heart failure patients that are eligible for advanced therapies as proof of principle. From our results on this particular application, the proposed network achieves the highest F1 score. The network is capable of learning rules that can be interpreted and used by clinical providers. In addition, existing fuzzy domain knowledge can be easily transferred into the network and facilitate model training. In our application, with the existing knowledge, the F1 score was improved by over 5%. The characteristics of the proposed network make it promising in applications requiring model reliability and justification.

Since the seminal works of Strassen and Valiant it has been a central theme in algebraic complexity theory to understand the relative complexity of algebraic problems, that is, to understand which algebraic problems (be it bilinear maps like matrix multiplication in Strassen’s work, or the determinant and permanent polynomials in Valiant’s) can be reduced to each other (under the appropriate notion of reduction). In this paper we work in the setting of bilinear maps and with the usual notion of reduction that allows applying linear maps to the inputs and output of a bilinear map in order to compute another bilinear map. As our main result we determine precisely how many independent scalar multiplications can be reduced to a given bilinear map (this number is called the subrank, and extends the concept of matrix diagonalization to tensors), for essentially all (i.e. generic) bilinear maps. Namely, we prove for a generic bilinear map T : V × V → V where dim(V ) = n that θ(√n) independent scalar multiplications can be reduced to T. Our result significantly improves on the previous upper bound from the work of Strassen (1991) and Bürgisser (1990) which was n^{2/3+o(1} . Our result is very precise and tight up to an additive constant. Our full result is much more general and applies not only to bilinear maps and 3-tensors but also to k-tensors, for which we find that the generic subrank is θ(n^{1/(k−1}). Moreover, as an application we prove that the subrank is not additive under the direct sum. The subrank plays a central role in several areas of complexity theory (matrix multiplication algorithms, barrier results) and combinatorics (e.g., the cap set problem and sunflower problem). As a consequence of our result we obtain several large separations between the subrank and tensor methods that have received much interest recently, notably the slice rank (Tao, 2016), analytic rank (Gowers–Wolf, 2011; Lovett, 2018; Bhrushundi–Harsha–Hatami–Kopparty–Kumar, 2020), geometric rank (Kopparty–Moshkovitz–Zuiddam, 2020), and G-stable rank (Derksen, 2020). Our proofs of the lower bounds rely on a new technical result about an optimal decomposition of tensor space into structured subspaces, which we think may be of independent interest.

We revisit the problem of constructing explicit pseudorandom generators that fool with error ϵ degree-d polynomials in n variables over the field Fq, in the case of large q. Previous constructions either have seed length $\geq 2^{d}\log q$, and thus are only non-trivial when $d\lt \log n$, or else rely on a seminal reduction by Bogdanov (STOC 2005). This reduction yields seed length not less than $d^{4}\log n+\log q$ and requires fields of size $q\geq d^{6}/\epsilon^{2}$; and explicit generators meeting such bounds are known.Departing from Bogdanov’s reduction, we develop an algebraic analogue of the Bogdanov-Viola paradigm (FOCS 2007, SICOMP 2010) of summing generators for degree-one polynomials. Whereas previous analyses of the paradigm are restricted to degree $d\lt \log n$, we give a new analysis which handles large degrees. A main new idea is to show that the construction preserves indecomposability of polynomials. Apparently for the first time in the area, the proof uses invariant theory.Our approach in particular yields several new pseudorandom generators. In particular, for large enough fields we obtain seed length $O(d\log n+\log q)$ which is optimal up to constant factors. We also construct generators for fields of size as small as $O(d^{4})$. Further reducing the field size requires a significant change in techniques: Most or all generators for large-degree polynomials rely on Weil bounds; but such bounds are only applicable when $q\gt d^{4}$

Patients recovering from cardiovascular surgeries may develop life-threatening complications such as hemodynamic decompensation, making the monitoring of patients for such complications an essential component of postoperative care. However, this need has given rise to an inexorable increase in the number and modalities of data points collected, making it challenging to effectively analyze in real time. While many algorithms exist to assist in monitoring these patients, they often lack accuracy and specificity, leading to alarm fatigue among healthcare practitioners. In this study we propose a multimodal approach that incorporates salient physiological signals and EHR data to predict the onset of hemodynamic decompensation. A retrospective dataset of patients recovering from cardiac surgery was created and used to train predictive models. Advanced signal processing techniques were employed to extract complex features from physiological waveforms, while a novel tensor-based dimensionality reduction method was used to reduce the size of the feature space. These methods were evaluated for predicting the onset of decompensation at varying time intervals, ranging from a half-hour to 12 h prior to a decompensation event. The best performing models achieved AUCs of 0.87 and 0.80 for the half-hour and 12-h intervals respectively. These analyses evince that a multimodal approach can be used to develop clinical decision support systems that predict adverse events several hours in advance.

Predicting the interactions between drugs and targets plays an important role in the process of new drug discovery, drug repurposing (also known as drug repositioning). There is a need to develop novel and efficient prediction approaches in order to avoid the costly and laborious process of determining drug-target interactions (DTIs) based on experiments alone. These computational prediction approaches should be capable of identifying the potential DTIs in a timely manner. Matrix factorization methods have been proven to be the most reliable group of methods. Here, we first propose a matrix factorization-based method termed 'Coupled Matrix-Matrix Completion' (CMMC). Next, in order to utilize more comprehensive information provided in different databases and incorporate multiple types of scores for drug-drug similarities and target-target relationship, we then extend CMMC to 'Coupled Tensor-Matrix Completion' (CTMC) by considering drug-drug and target-target similarity/interaction tensors. Results: Evaluation on two benchmark datasets, DrugBank and TTD, shows that CTMC outperforms the matrix-factorization-based methods: GRMF, $L_{2,1}$-GRMF, NRLMF and NRLMF$\beta $. Based on the evaluation, CMMC and CTMC outperform the above three methods in term of area under the curve, F1 score, sensitivity and specificity in a considerably shorter run time.

In this paper, based on ideas from lossy data coding and compression, we present a simple but surprisingly effective technique for segmenting multivariate mixed data that are drawn from a mixture of Gaussian distributions or linear subspaces. The goal is to find the optimal segmentation that minimizes the overall coding length of the segmented data, subject to a given distortion. We show that deterministic segmentation minimizes an upper bound on the (asymptotically) optimal solution. The proposed algorithm does not require any prior knowledge of the number or dimension of the groups, nor does it involve any parameter estimation. Simulation results reveal intriguing phase-transition behaviors of the number of segments when changing the level of distortion or the amount of outliers. Finally, we demonstrate how this technique can be readily applied to segment real imagery and bioinformatic data.

We consider the problem of simultaneously segmenting data samples drawn from multiple linear subspaces and estimating model parameters for those subspaces. This "subspace segmentation" problem naturally arises in many computer vision applications such as motion and video segmentation, and in the recognition of human faces, textures, and range data. Generalized Principal Component Analysis (GPCA) has provided an effective way to resolve the strong coupling between data segmentation and model estimation inherent in subspace segmentation. Essentially, GPCA works by first finding a global algebraic representation of the unsegmented data set, and then decomposing the model into irreducible components, each corresponding to exactly one subspace. We provide a summary of important algebraic properties and statistical facts that are crucial for making GPCA both efficient and robust, even when the given data are corrupted with noise or contaminated by outliers. We demonstrate the effectiveness of GPCA using a large testbed of synthetic and real experiments.

In this paper, based on ideas from lossy data coding and compression, we present a simple but effective technique for segmenting multivariate mixed data that are drawn from a mixture of Gaussian distributions, which are allowed to be almost degenerate. The goal is to find the optimal segmentation that minimizes the overall coding length of the segmented data, subject to a given distortion. By analyzing the coding length/rate of mixed data, we formally establish some strong connections of data segmentation to many fundamental concepts in lossy data compression and rate distortion theory. We show that a deterministic segmentation is approximately the (asymptotically) optimal solution for compressing mixed data. We propose a very simple and effective algorithm which depends on a single parameter, the allowable distortion. At any given distortion, the algorithm automatically determines the corresponding number and dimension of the groups and does not involve any parameter estimation. Simulation results reveal intriguing phase-transition-like behaviors of the number of segments when changing the level of distortion or the amount of outliers. Finally, we demonstrate how this technique can be readily applied to segment real imagery and bioinformatic data.

We construct error-correcting (nonlinear) binary codes using a construction of Bose and Chowla in additive number theory. Our method extends a construction of Graham and Sloane for constant weight codes. The new codes improve 1028 of the 7168 best known h-error-correcting codes of word length /spl les/512 with 1/spl les/h/spl les/14. We give asymptotical comparisons to shortened Bose-Chaudhuri-Hocquenghem (BCH) codes.