ISI Digital Commons (Indian Statistical Institute )
Not a member yet
7571 research outputs found
Sort by
Faster Counting and Sampling Algorithms Using Colorful Decision Oracle
No full textIn this work, we consider d-Hyperedge Estimation and d-Hyperedge Sample problems that deal with estimation and uniform sampling of hyperedges in a hypergraph H (U (H), F (H)) in the query complexity framework, where U (H) denotes the set of vertices and F (H) denotes the set of hyperedges. The oracle access to the hypergraph is called Colorful Independence Oracle (CID), which takes d (non-empty) pairwise disjoint subsets of vertices A1, . . ., Ad ⊆ U (H) as input and answers whether there exists a hyperedge in H having exactly one vertex in each Ai for all i ∈ {1, 2, . . ., d}. Apart from the fact that d-Hyperedge Estimation and d-Hyperedge Sample problems with CID oracle access seem to be nice combinatorial problems, Dell et al. [SODA’20 & SICOMP’22] established that decision vs. counting complexities of a number of combinatorial optimization problems can be abstracted out as d-Hyperedge Estimation problem with a CID oracle access. The main technical contribution of this article is an algorithm that estimates m = |F (H)| with m̂ such that by using at most Cd logd+2 n CID queries, where n denotes the number of vertices in the hypergraph H and Cd is a constant that depends only on d. Our result, when coupled with the framework proposed by Dell et al. (SODA’20 & SICOMP’22), leads to implies improved bounds for (1 ± ε)-approximation (where ε ∈ (0, 1)) for the following fundamental problems: Edge Estimation using the Bipartite Independent Set (BIS) query. We improve the bound obtained by Beame et al. (ITCS’18 & TALG’20). Triangle Estimation using the Tripartite Independent Set (TIS) query. Currently, Dell et al.’s result gives the best bound for the case of triangle estimation in general graphs (SODA’20 & SICOMP’22). The previous best bound for the case of graphs with low co-degree (co-degree of a graph is the maximum number of triangles incident over any edge of the graph) was due to Bhattacharya et al. (ISAAC’19 & TOCS’21). We improve both of these bounds. Hyperedge Estimation & Sampling using Colorful Independence Oracle (CID). We give an improvement over the bounds obtained by Dell et al. (SODA’20 & SICOMP’22)
FUNCTIONAL DEUTSCH UNCERTAINTY PRINCIPLE
No full textEntropic uncertainty principle for finite dimensional Hilbert spaces (known as Deutsch uncertainty) obtained by Deutsch [Phys. Rev. Lett., 1983] is a foundational result in Mathematics and Physics. We derive the Deutsch uncertainty principle for finite dimensional Banach space and its dual. Our main tool is the notion of Parseval p-frames for Banach spaces. Using the celebrated Buzano inequality in Hilbert spaces, we show that our result reduces to the Deutsch uncertainty principle for Hilbert spaces
High-Dimensional Fuzzy Inference Systems
No full textFuzzy inference systems (FISs) have been developed for many years but the use of FISs for high-dimensional problems is still a challenging task. The most frequently used T-norms for computing the firing strengths are product and minimum operators of which the former is often preferred because of its differentiability. However, for high-dimensional problems, the product T-norm suffers from the numeric underflow problem. Here, we primarily focus on addressing the problem that is associated with the use of the T-norms for designing high-dimensional FISs (HDFISs). For the product T-norm, we construct an HDFIS named HDFIS-prod, which easily escapes from the numeric underflow problem. The main novelty is that we propose an adaptive dimension-dependent membership function (DMF). For the minimum T-norm, an empirical observation led us to develop a mechanism that has the natural ability to deal with super high-dimensional problems, which results in another HDFIS named HDFIS-min. Both HDFIS-prod and HDFIS-min are tested on 18 datasets with feature dimensions varying from 1024 to 120450. The simulation results demonstrate that both of them have competitive performance on handling high-dimensional datasets
Introducing nega-Forrelation: quantum algorithms in analyzing nega-Hadamard and nega-crosscorrelation spectra
No full textAaronson defined Forrelation (2010) as a measure of correlation between a Boolean function f and the Walsh–Hadamard transform of another function g. In a recent work, we have studied different cryptographically important spectra of Boolean functions through the lens of Forrelation. In this paper, we explore a similar kind of correlation in terms of nega-Hadamard transform. We call it nega-Forrelation and obtain a more efficient sampling strategy for nega-Hadamard transform compared to the existing results. Moreover, we present an efficient sampling strategy for nega-crosscorrelation (and consequently nega-autocorrelation) spectra too, by tweaking the nega-Forrelation technique. Finally, we connect the hidden shift finding algorithm for bent functions (Rötteler, 2010) with the Forrelation algorithm and extend it for the negabent functions
Investigating the impact of standard brain atlases and connectivity measures on the accuracy of ADHD detection from fMRI data using deep learning
No full textInattention, hyperactivity, and impulsivity are among the symptoms of Attention Deficit Hyperactivity Syndrome (ADHD). This brain disorder cannot currently be treated or avoided. A kid or adult with ADHD may be able to control their symptoms, though, if they are diagnosed early and have a good treatment and education plan. Functional magnetic resonance imaging (fMRI) is one of the non-invasive imaging techniques used to diagnose ADHD. The blood-oxygen-level-dependent (BOLD) signals extracted from several brain regions (obtained by choosing a brain atlas) are processed to form a brain functional connectivity matrix and fed into a deep learning model for the classification of ADHD. In this paper, we study two things: first, we diagnose the ADHD using fMRI data by proposing two approaches, viz., an image-based approach and a graph-based (network-based) approach. In the image-based approach, the connectivity matrix obtained from the fMRI data is used directly as an image, and the whole image is fed into a deep learning model. In the network-based approach, the connectivity matrix is first converted into an adjacency matrix, which represents an undirected network. After that, several network properties are accumulated as features, and the feature vector is fed into the deep learning model. Second, we study how the choice of a particular brain atlas or connectivity matrix can affect the accuracy of the ADHD diagnosis. The suggested algorithms, along with six different atlases and two different connectivity matrices, are compared using 352 fMRI images and various one- and two-dimensional neural network models. Our finding demonstrates that accuracy varies depending on the atlases and connectivity measurements used. In addition, we have shown that, with a particular setup, our algorithms outperform a number of deep-learning baselines showing the second best (ranging from 74.48% to 90.90%) results most of the time. Application of various atlases and connectivity matrices shows 64% variations in the overall accuracy
Lattices of Logmodular Algebras
No full textA subalgebra A of a C∗-algebra M is logmodular (resp. has factorization) if the set {a∗ a; a ∈ M is invertible with a, a−1 ∈ A} is dense in (resp. equal to) the set of all positive and invertible elements of M. In this paper, we show that the lattice of projections in a (separable) von Neumann algebra M whose ranges are invariant under a logmodular algebra in M, is a commutative subspace lattice. Further, if M is a factor then this lattice is a nest. As a special case, it follows that all reflexive (in particular, completely distributive CSL) logmodular subalgebras of type I factors are nest algebras, thus answering in the affirmative a question by Paulsen and Raghupathi (Trans. Amer. Math. Soc. 363 (2011) 2627–2640). We also give a complete characterization of logmodular subalgebras in finite-dimensional von Neumann algebras
Learning Networks from Gaussian Graphical Models and Gaussian Free Fields
No full textWe investigate the problem of estimating the structure of a weighted network from repeated measurements of a Gaussian graphical model (GGM) on the network. In this vein, we consider GGMs whose covariance structures align with the geometry of the weighted network on which they are based. Such GGMs have been of longstanding interest in statistical physics, and are referred to as the Gaussian free field (GFF). In recent years, they have attracted considerable interest in the machine learning and theoretical computer science. In this work, we propose a novel estimator for the weighted network (equivalently, its Laplacian) from repeated measurements of a GFF on the network, based on the Fourier analytic properties of the Gaussian distribution. In this pursuit, our approach exploits complex-valued statistics constructed from observed data, that are of interest in their own right. We demonstrate the effectiveness of our estimator with concrete recovery guarantees and bounds on the required sample complexity. In particular, we show that the proposed statistic achieves the parametric rate of estimation for fixed network size. In the setting of networks growing with sample size, our results show that for Erdos–Renyi random graphs G(d, p) above the connectivity threshold, network recovery takes place with high probability as soon as the sample size n satisfies n≫d4logd·p-2
Level and pseudo-Gorenstein path polyominoes
No full textWe classify path polyominoes which are level and pseudo-Gorenstein. Moreover, we compute all level and pseudo-Gorenstein simple thin polyominoes with rank less than or equal to 10. We also compute the regularity of the pseudo-Gorenstein simple thin polyominoes in relation to their rank
Likelihood-based inference for semi-parametric transformation cure models with interval censored data
No full textA simple yet effective way of modeling survival data with cure fraction is by considering Box-Cox transformation cure model (BCTM) that unifies mixture and promotion time cure models. In this article, we numerically study the statistical properties of the BCTM when applied to interval censored data. Time-to-events associated with susceptible subjects are modeled through proportional hazards structure that allows for non-homogeneity across subjects, where the baseline hazard function is estimated by distribution-free piecewise linear function with varied degrees of non-parametricity. Due to missing cured statuses for right censored subjects, maximum likelihood estimates of model parameters are obtained by developing an expectation-maximization (EM) algorithm. Under the EM framework, the conditional expectation of the complete data log-likelihood function is maximized by considering all parameters (including the Box-Cox transformation parameter α) simultaneously, in contrast to conventional profile-likelihood technique of estimating α. The robustness and accuracy of the model and estimation method are established through a detailed simulation study under various parameter settings, and an analysis of real-life data obtained from a smoking cessation study
Novel report of Acinetobacter johnsonii as an indole-producing seed endophyte in Tamarindus indica L
No full textPlant–microbe associations have been regarded as an exciting topic of research due to their potential as environment friendly alternatives for stimulating crop growth and development. Seeds of Tamarindus indica L. have been chosen for the present study as seed endophytes prefer larger or nutritive cotyledon and hard seed coats for their colonization. The main objectives of our study were to isolate and identify the seed endophytes, their bioefficacy, and responsible chemical compounds. In a dose-dependent experiment, tamarind seed exudates (TSE) showed plant growth-promoting properties on Oryza sativa (53–81%), Daucus carota (10–31%), and Raphanus sativa (21–42%). Identification of the bacterial load in TSE through 16S rRNA sequencing revealed the existence of two bacterial species, Acinetobacter johnsonii and Niallia nealsonii. This is the first report of these two bacteria as seed endophytes of Tamarindus indica L. HRLC–MS analysis of TSE confirmed the presence of indole derivatives, primarily indole-3-lactic acid (ILA). The quantitative phytochemical estimation of bacterial culture filtrates revealed that indole-like substances were present in the extracts only in A. johnsonii at a concentration of 0.005 mg/ml of indole acetic acid equivalent. Experimental results suggested that the stimulatory activity of TSE was caused by the presence of A. johnsonii, a potential plant growth-promoting bacteria that produced indole-like compounds. This study suggests tamarind seed exudates with its endophytic microbiota as a potent plant growth-promoting agent that may find use as a cheap and sustainable source of metabolites useful in the agro-industries