Search

The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting variables\cite{HW15}. This rank computation problem has deterministic polynomial-time white-box algorithms \cite{GGOW16, IQS18} and a randomized polynomial-time algorithm in the black-box setting \cite{DM17}. In this paper, we propose a new approach for efficient derandomization of \emph{black-box} RIT. Additionally, we obtain results for matrix rank computation over the free skew field, and construct efficient linear pencil representations for a new class of rational expressions. More precisely, we show the following results: 1. Under the hardness assumption that the ABP (algebraic branching program) complexity of every polynomial identity for the $k\times k$ matrix algebra is $2^{\Omega(k)}$ \cite{BW05}, we obtain a subexponential-time black-box algorithm for RIT in almost general setting. This can be seen as the first "hardness implies derandomization" type theorem for rational formulas. 2. We show that the noncommutative rank of any matrix over the free skew field whose entries have small linear pencil representations can be computed in deterministic polynomial time. Prior to this, an efficient rank computation was only known for matrices with noncommutative formulas as entries\cite{GGOW20}. As special cases of our algorithm, we obtain the first deterministic polynomial-time algorithms for rank computation of matrices whose entries are noncommutative ABPs or rational formulas. 3. Motivated by the definition given by Bergman\cite{Ber76}, we define a new class that contains noncommutative ABPs and rational formulas. We obtain a polynomial-size linear pencil representation for this class. As a by-product, we obtain a white-box deterministic polynomial-time identity testing algorithm for the class.

Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials computed by these structured variants of ROABPs and other well-known classes of polynomials (such as depth-three powering circuits, tensor-rank and Waring rank of polynomials). Our main result concerns commutative ROABPs, where all coefficient matrices commute with each other, and diagonal ROABPs, where all the coefficient matrices are just diagonal matrices. In particular, we show a somewhat surprising connection between these models and the model of depth-three powering circuits that is related to the Waring rank of polynomials. We show that if the dimension of partial derivatives captures Waring rank up to polynomial factors, then the model of diagonal ROABPs efficiently simulates the seemingly more expressive model of commutative ROABPs. Further, a commutative ROABP that cannot be efficiently simulated by a diagonal ROABP will give an explicit polynomial that gives a super-polynomial separation between dimension of partial derivatives and Waring rank. Our proof of the above result builds on the results of Marinari, M\"oller and Mora (1993), and M\"oller and Stetter (1995), that characterise rings of commuting matrices in terms of polynomials that have small dimension of partial derivatives. The algebraic structure of the coefficient matrices of these ROABPs plays a crucial role in our proofs., Comment: Accepted to STACS 2022

The amplitude-dependent frequency of the oscillations, termed \emph{nonisochronicity}, is one of the essential characteristics of nonlinear oscillators. In this paper, the dynamics of the Rossler oscillator in the presence of nonisochronicity is examined. In particular, we explore the appearance of a new fixed point and the emergence of a coexisting limit-cycle and quasiperiodic attractors. We also describe the sequence of bifurcations leading to synchronized, desynchronized attractors and oscillation death states in the coupled Rossler oscillators as a function of the strength of nonisochronicity and coupling parameters. Further, we characterize the multistability of the coexisting attractors by plotting the basins of attraction. Our results open up the possibilities of understanding the emergence of coexisting attractors, and into a qualitative change of the collective states in coupled nonlinear oscillators in the presence of nonisochronicity., Comment: 11 pages, 13 figures. Accepted for publication in Chaos

Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size. In a recent work of Chatterjee and the authors (FOCS 2020), it was shown that the subclasses of VP and VNP consisting of polynomials with bounded integer coefficients do have equations with small algebraic circuits. Their work left open the possibility that these results could perhaps be extended to all of VP or VNP. The results in this paper show that assuming the hardness of Permanent, at least for VNP, allowing polynomials with large coefficients does indeed incur a significant blow up in the circuit complexity of equations., Comment: arXiv admin note: substantial text overlap with arXiv:2004.14147

The concept of matrix rigidity was introduced by Valiant(independently by Grigoriev) in the context of computing linear transformations. A matrix is rigid if it is far(in terms of Hamming distance) from any matrix of low rank. Although we know rigid matrices exist, obtaining explicit constructions of rigid matrices have remained a long-standing open question. This decade has seen tremendous progress towards understanding matrix rigidity. In the past, several matrices such as Hadamard matrices and Fourier matrices were conjectured to be rigid. Very recently, many of these matrices were shown to have low rigidity. Further, several explicit constructions of rigid matrices in classes such as $E$ and $P^{NP}$ were obtained recently. Among other things, matrix rigidity has found striking connections to areas as disparate as communication complexity, data structure lower bounds and error-correcting codes. In this survey, we present a selected set of results that highlight recent progress on matrix rigidity and its remarkable connections to other areas in theoretical computer science.

The framework of algebraically natural proofs was independently introduced in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017), to study the efficacy of commonly used techniques for proving lower bounds in algebraic complexity. We use the known connections between algebraic hardness and pseudorandomness to shed some more light on the question relating to this framework, as follows. 1. The subclass of $\mathsf{VP}$ that contains polynomial families with bounded coefficients, has efficient equations. Over finite fields, this result holds without any restriction on coefficients. Further, both these results extend to \emph{any} class that admits a low-variate, low-degree universal map: a generator for all polynomials in the class. Most well-studied classes have this property, e.g. \textsf{VNP}, \textsf{VBP}, \textsf{VF}. 2. Over fields of characteristic zero, $\mathsf{VNP}$ does not have any efficient equations, if the Permanent is exponentially hard for algebraic circuits. Moreover, exponential hardness of the Permanent in the approximative sense, even rules out efficient equations of large degree. This gives the only known barrier to ``natural'' lower bound techniques (that follows from believable hardness assumptions), and also shows that the restriction on coefficients in the first category of results about $\mathsf{VNP}$ is necessary. The first set of results follows essentially by algebraizing the well-known method of generating hardness from non-trivial hitting sets (e.g. Heintz and Schnorr 1980). The conditional hardness of equations for $\mathsf{VNP}$ uses the fact that pseudorandomness against a class can be extracted from a polynomial that is (sufficiently) hard for that class (Kabanets and Impagliazzo, 2004)., Comment: The work arXiv:2012.07056 "If VNP is hard, then so are equations for it" has been combined with the previous version of this work (CKRST 2020). Further, this version generalizes the main results in the earlier versions (both CKRST 2020 and KRST 2022), and also includes more detailed definitions of algebraic natural proofs and other related concepts

Proving super-polynomial size lower bounds for syntactic multilinear Algebraic Branching Programs(smABPs) computing an explicit polynomial is a challenging problem in Algebraic Complexity Theory. The order in which variables in $\{x_1,\ldots,x_n\}$ appear along source to sink paths in any smABP can be viewed as a permutation in $S_n$. In this article, we consider the following special classes of smABPs where the order of occurrence of variables along a source to sink path is restricted: Strict circular-interval ABPs: For every subprogram the index set of variables occurring in it is contained in some circular interval of $\{1,\ldots,n\}$. L-ordered ABPs: There is a set of L permutations of variables such that every source to sink path in the ABP reads variables in one of the L orders. We prove exponential lower bound for the size of a strict circular-interval ABP computing an explicit n-variate multilinear polynomial in VP. For the same polynomial, we show that any sum of L-ordered ABPs of small size will require exponential ($2^{n^{\Omega(1)}}$) many summands, when $L \leq 2^{n^{1/2-\epsilon}}, \epsilon>0$. At the heart of above lower bound arguments is a new decomposition theorem for smABPs: We show that any polynomial computable by an smABP of size S can be written as a sum of O(S) many multilinear polynomials where each summand is a product of two polynomials in at most 2n/3 variables computable by smABPs. As a corollary, we obtain a low bottom fan-in version of the depth reduction by Tavenas [MFCS 2013] in the case of smABPs. In particular, we show that a polynomial having size S smABPs can be expressed as a sum of products of multilinear polynomials on $O(\sqrt{n})$ variables, where the total number of summands is bounded by $2^{O(\sqrt{n}\log n \log S)}$. Additionally, we show that L-ordered ABPs can be transformed into L-pass smABPs with a polynomial blowup in size.

Algebraic Branching Programs(ABPs) are standard models for computing polynomials. Syntactic multilinear ABPs (smABPs) are restrictions of ABPs where every variable is allowed to occur at most once in every path from the start to the terminal node. Proving lower bounds against syntactic multilinear ABPs remains a challenging open question in Algebraic Complexity Theory. The current best known bound is only quadratic [Alon-Kumar-Volk, ECCC 2017]. In this article we develop a new approach upper bounding the rank of the partial derivative matrix of syntactic multlinear ABPs: Convert the ABP to a syntactic mulilinear formula with a super polynomial blow up in the size and then exploit the structural limitations of resulting formula to obtain a rank upper bound. Using this approach, we prove exponential lower bounds for special cases of smABPs and circuits - namely sum of Oblivious Read-Once ABPs, r-pass mulitlinear ABPs and sparse ROABPs. En route, we also prove super-polynomial lower bound for a special class of syntactic multilinear arithmetic circuits.

An n-variate Vandermonde polynomial is the determinant of the n x n matrix where the ith column is the vector (1, x_i, x_i^2, ...., x_i^{n-1})^T. Vandermonde polynomials play a crucial role in the theory of alternating polynomials and occur in Lagrangian polynomial interpolation as well as in the theory of error correcting codes. In this work we study structural and computational aspects of linear projections of Vandermonde polynomials. Firstly, we consider the problem of testing if a given polynomial is linearly equivalent to the Vandermonde polynomial. We obtain a deterministic polynomial time algorithm to test if the polynomial f is linearly equivalent to the Vandermonde polynomial when f is given as product of linear factors. In the case when the polynomial f is given as a black-box our algorithm runs in randomized polynomial time. Exploring the structure of projections of Vandermonde polynomials further, we describe the group of symmetries of a Vandermonde polynomial and show that the associated Lie algebra is simple., Comment: Submitted to a conference

We study limitations of polynomials computed by depth two circuits built over read-once polynomials (ROPs) and depth three syntactically multi-linear formulas. We prove an exponential lower bound for the size of the $\Sigma\Pi^{[N^{1/30}]}$ arithmetic circuits built over syntactically multi-linear $\Sigma\Pi\Sigma^{[N^{8/15}]}$ arithmetic circuits computing a product of variable disjoint linear forms on $N$ variables. We extend the result to the case of $\Sigma\Pi^{[N^{1/30}]}$ arithmetic circuits built over ROPs of unbounded depth, where the number of variables with $+$ gates as a parent in an proper sub formula is bounded by $N^{1/2+1/30}$. We show that the same lower bound holds for the permanent polynomial. Finally we obtain an exponential lower bound for the sum of ROPs computing a polynomial in ${\sf VP}$ defined by Raz and Yehudayoff. Our results demonstrate a class of formulas of unbounded depth with exponential size lower bound against the permanent and can be seen as an exponential improvement over the multilinear formula size lower bounds given by Raz for a sub-class of multi-linear and non-multi-linear formulas. Our proof techniques are built on the one developed by Raz and later extended by Kumar et. al.\cite{KMS13} and are based on non-trivial analysis of ROPs under random partitions. Further, our results exhibit strengths and limitations of the lower bound techniques introduced by Raz\cite{Raz04a}., Comment: Submitted to a conference

In this paper, we propose ART1 neural network clustering algorithm to group users according to their Web access patterns. We compare the quality of clustering of our ART1 based clustering technique with that of the K-Means and SOM clustering algorithms in terms of inter-cluster and intra-cluster distances. The results show the average inter-cluster distance of ART1 is high compared to K-Means and SOM when there are fewer clusters. As the number of clusters increases, average inter-cluster distance of ART1 is low compared to K-Means and SOM which indicates the high quality of clusters formed by our approach.

In this paper, a complete preprocessing methodology for discovering patterns in web usage mining process to improve the quality of data by reducing the quantity of data has been proposed. A dynamic ART1 neural network clustering algorithm to group users according to their Web access patterns with its neat architecture is also proposed. Several experiments are conducted and the results show the proposed methodology reduces the size of Web log files down to 73-82% of the initial size and the proposed ART1 algorithm is dynamic and learns relatively stable quality clusters., Comment: 6 pages; International Conference on Information Processing, august-2011

Web log data is usually diverse and voluminous. This data must be assembled into a consistent, integrated and comprehensive view, in order to be used for pattern discovery. Without properly cleaning, transforming and structuring the data prior to the analysis, one cannot expect to find meaningful patterns. As in most data mining applications, data preprocessing involves removing and filtering redundant and irrelevant data, removing noise, transforming and resolving any inconsistencies. In this paper, a complete preprocessing methodology having merging, data cleaning, user/session identification and data formatting and summarization activities to improve the quality of data by reducing the quantity of data has been proposed. To validate the efficiency of the proposed preprocessing methodology, several experiments are conducted and the results show that the proposed methodology reduces the size of Web access log files down to 73-82% of the initial size and offers richer logs that are structured for further stages of Web Usage Mining (WUM). So preprocessing of raw data in this WUM process is the central theme of this paper.

In the present paper, an effort has been made for storing and recalling images with Hopfield Neural Network Model of auto-associative memory. Images are stored by calculating a corresponding weight matrix. Thereafter, starting from an arbitrary configuration, the memory will settle on exactly that stored image, which is nearest to the starting configuration in terms of Hamming distance. Thus given an incomplete or corrupted version of a stored image, the network is able to recall the corresponding original image. The storing of the objects has been performed according to the Hopfield algorithm explained below. Once the net has completely learnt this set of input patterns, a set of testing patterns containing degraded images will be given to the net. Then the Hopfield net will tend to recall the closest matching pattern for the given degraded image. The simulated results show that Hopfield model is the best for storing and recalling images.

Web log data is usually diverse and voluminous. This data must be assembled into a consistent, integrated and comprehensive view, in order to be used for pattern discovery. Without properly cleaning, transforming and structuring the data prior to the analysis, one cannot expect to find meaningful patterns. As in most data mining applications, data preprocessing involves removing and filtering redundant and irrelevant data, removing noise, transforming and resolving any inconsistencies. In this paper, a complete preprocessing methodology having merging, data cleaning, user/session identification and data formatting and summarization activities to improve the quality of data by reducing the quantity of data has been proposed. To validate the efficiency of the proposed preprocessing methodology, several experiments are conducted and the results show that the proposed methodology reduces the size of Web access log files down to 73-82% of the initial size and offers richer logs that are structured for further stages of Web Usage Mining (WUM). So preprocessing of raw data in this WUM process is the central theme of this paper., Comment: 5 pages