Search

Let $X=X_1\sqcup X_2\sqcup\ldots\sqcup X_k$ be a partitioned set of variables such that the variables in each part $X_i$ are noncommuting but for any $i\neq j$, the variables $x\in X_i$ commute with the variables $x'\in X_j$. Given as input a square matrix $T$ whose entries are linear forms over $\mathbb{Q}\langle{X}\rangle$, we consider the problem of checking if $T$ is invertible or not over the universal skew field of fractions of the partially commutative polynomial ring $\mathbb{Q}\langle{X}\rangle$ [Klep-Vinnikov-Volcic (2020)]. In this paper, we design a deterministic polynomial-time algorithm for this problem for constant $k$. The special case $k=1$ is the noncommutative Edmonds' problem (NSINGULAR) which has a deterministic polynomial-time algorithm by recent results [Garg-Gurvits-Oliveira-Wigderson (2016), Ivanyos-Qiao-Subrahmanyam (2018), Hamada-Hirai (2021)]. En-route, we obtain the first deterministic polynomial-time algorithm for the equivalence testing problem of $k$-tape \emph{weighted} automata (for constant $k$) resolving a long-standing open problem [Harju and Karhum"{a}ki(1991), Worrell (2013)]. Algebraically, the equivalence problem reduces to testing whether a partially commutative rational series over the partitioned set $X$ is zero or not [Worrell (2013)]. Decidability of this problem was established by Harju and Karhum\"{a}ki (1991). Prior to this work, a \emph{randomized} polynomial-time algorithm for this problem was given by Worrell (2013) and, subsequently, a deterministic quasipolynomial-time algorithm was also developed [Arvind et al. (2021)].

Rational Identity Testing (RIT) is the decision problem of determining whether or not a noncommutative rational formula computes zero in the free skew field. It admits a deterministic polynomial-time white-box algorithm [Garg, Gurvits, Oliveira, and Wigderson (2016); Ivanyos, Qiao, Subrahmanyam (2018); Hamada and Hirai (2021)], and a randomized polynomial-time algorithm [Derksen and Makam (2017)] in the black-box setting, via singularity testing of linear matrices over the free skew field. Indeed, a randomized NC algorithm for RIT in the white-box setting follows from the result of Derksen and Makam (2017). Designing an efficient deterministic black-box algorithm for RIT and understanding the parallel complexity of RIT are major open problems in this area. Despite being open since the work of Garg, Gurvits, Oliveira, and Wigderson (2016), these questions have seen limited progress. In fact, the only known result in this direction is the construction of a quasipolynomial-size hitting set for rational formulas of only inversion height two [Arvind, Chatterjee, Mukhopadhyay (2022)]. In this paper, we significantly improve the black-box complexity of this problem and obtain the first quasipolynomial-size hitting set for all rational formulas of polynomial size. Our construction also yields the first deterministic quasi-NC upper bound for RIT in the white-box setting.

We study lattice wouldsheet theory with continuous time describing free motion of a system of bound string bits. We use a non-local lattice derivative that allows us to preserve all the symmetries of the continuum including the worldsheet local symmetries. There exists a ``local correspondence'' between the continuum and lattice theories in the sense that every local dynamical or constraint equation in the continuum also holds true on the lattice, site-wise. We perform a detailed symmetry analysis for the bits and establish conservation laws. In particular, for a bosonic non-linear sigma model with arbitrary target space, we demonstrate both the global symmetry algebra and classical Virasoro algebra (in position space) on the lattice. Our construction is generalizable to higher dimensions for any generally covariant theory that can be studied by expanding around a globally hyperbolic spacetime with conformally flat Cauchy slices., Comment: 43 pages

Let $T$ be a matrix whose entries are linear forms over the noncommutative variables $x_1, x_2, \ldots, x_n$. The noncommutative Edmonds' problem (NSINGULAR) aims to determine whether $T$ is invertible in the free skew field generated by $x_1,x_2,\ldots,x_n$. Currently, there are three different deterministic polynomial-time algorithms to solve this problem: using operator scaling [Garg, Gurvits, Oliveira, and Wigserdon (2016)], algebraic methods [Ivanyos, Qiao, and Subrahmanyam (2018)], and convex optimization [Hamada and Hirai (2021)]. In this paper, we present a simpler algorithm for the NSINGULAR problem. While our algorithmic template is similar to the one in Ivanyos et. al.(2018), it significantly differs in its implementation of the rank increment step. Instead of computing the limit of a second Wong sequence, we reduce the problem to the polynomial identity testing (PIT) of noncommutative algebraic branching programs (ABPs). This enables us to bound the bit-complexity of the algorithm over $\mathbb{Q}$ without requiring special care. Moreover, the rank increment step can be implemented in quasipolynomial-time even without an explicit description of the coefficient matrices in $T$. This is possible by exploiting the connection with the black-box PIT of noncommutative ABPs [Forbes and Shpilka (2013)].

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.

Hrube\v{s} and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, deterministic polynomial-time algorithms are known for this problem following the works of Garg, Gurvits, Oliveira, and Wigderson (2016) and Ivanyos, Qiao, and Subrahmanyam (2018). A central open problem in this area is to design efficient deterministic black-box identity testing algorithm for rational formulas. In this paper, we solve this problem for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomial-time black-box RIT algorithm for noncommutative rational formulas of inversion height two via a hitting set construction. Several new technical ideas are involved in the hitting set construction, including key concepts from matrix coefficient realization theory (Vol\v{c}i\v{c}, 2018) and properties of cyclic division algebra (Lam, 2001). En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas (2013) inside a cyclic division algebra of small index.

We prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond. First, we show that the spanning tree polynomials having $n$ variables and defined over constant-degree expander graphs, have monotone arithmetic complexity $2^{\Omega(n)}$. This yields the first strongly exponential lower bound on the monotone arithmetic circuit complexity for a polynomial in VP. Before this result, strongly exponential size monotone lower bounds were known only for explicit polynomials in VNP (Gashkov-Sergeev'12, Raz-Yehudayoff'11, Srinivasan'20, Cavalar-Kumar-Rossman'20, Hrubes-Yehudayoff'21). Recently, Hrubes'20 initiated a program to prove lower bounds against general arithmetic circuits by proving $\epsilon$-sensitive lower bounds for monotone arithmetic circuits for a specific range of values for $\epsilon \in (0,1)$. We consider the spanning tree polynomial $ST_{n}$ defined over the complete graph on $n$ vertices and show that the polynomials $F_{n-1,n} - \epsilon \cdot ST_{n}$ and $F_{n-1,n} + \epsilon \cdot ST_{n}$ defined over $n^2$ variables, have monotone circuit complexity $2^{\Omega(n)}$ if $\epsilon \geq 2^{-\Omega(n)}$ and $F_{n-1,n} = \prod_{i=2}^n (x_{i,1} +\cdots + x_{i,n})$ is the complete set-multilinear polynomial. This provides the first $\epsilon$-sensitive exponential lower bound for a family of polynomials inside VP. En-route, we consider a problem in 2-party, best partition communication complexity of deciding whether two sets of oriented edges distributed among Alice and Bob form a spanning tree or not. We prove that there exists a fixed distribution, under which the problem has low discrepancy with respect to every nearly-balanced partition. This result could be of interest beyond algebraic complexity., Comment: 20 pages, 3 figures

We study \emph{multiplicity equivalence} testing of automata over partially commutative monoids (pc monoids) and show efficient algorithms in special cases, exploiting the structure of the underlying non-commutation graph of the monoid. Specifically, if the clique cover number of the non-commutation graph (the minimum number of cliques covering the graph) of the pc monoid is a constant, we obtain a deterministic quasi-polynomial time algorithm. As a consequence, we also obtain the first deterministic quasi-polynomial time algorithms for multiplicity equivalence testing of $k$-tape automata and for equivalence testing of deterministic $k$-tape automata for constant $k$. Prior to this, a randomized polynomial-time algorithm for the above problems was shown by Worrell [ICALP 2013]. We also consider pc monoids for which the non-commutation graphs have cover consisting of at most $k$ cliques and star graphs for any constant $k$. We obtain randomized polynomial-time algorithm for multiplicity equivalence testing of automata over such monoids.

We study the arithmetic circuit complexity of some well-known family of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit algebraic branching programs (ABP) for determinant and permanent polynomials of the \emph{rectangular} symbolic matrix in both commutative and noncommutative settings. The main results are: 1. We show an explicit $O^{*}({n\choose {\downarrow k/2}})$-size ABP construction for noncommutative permanent polynomial of $k\times n$ symbolic matrix. We obtain this via an explicit ABP construction of size $O^{*}({n\choose {\downarrow k/2}})$ for $S_{n,k}^*$, noncommutative symmetrized version of the elementary symmetric polynomial $S_{n,k}$. 2. We obtain an explicit $O^{*}(2^k)$-size ABP construction for the commutative rectangular determinant polynomial of the $k\times n$ symbolic matrix. 3. In contrast, we show that evaluating the rectangular noncommutative determinant over rational matrices is $W[1]$-hard.

Hrube\v{s} and Wigderson [HW14] initiated the study of noncommutative arithmetic circuits with division computing a noncommutative rational function in the free skew field, and raised the question of rational identity testing. It is now known that the problem can be solved in deterministic polynomial time in the white-box model for noncommutative formulas with inverses, and in randomized polynomial time in the black-box model [GGOW16, IQS18, DM18], where the running time is polynomial in the size of the formula. The complexity of identity testing of noncommutative rational functions remains open in general (when the formula size is not polynomially bounded). We solve the problem for a natural special case. We consider polynomial expressions in the free group algebra $\mathbb{F}\langle X, X^{-1}\rangle$ where $X=\{x_1, x_2, \ldots, x_n\}$, a subclass of rational expressions of inversion height one. Our main results are the following. 1. Given a degree $d$ expression $f$ in $\mathbb{F}\langle X, X^{-1}\rangle$ as a black-box, we obtain a randomized $\text{poly}(n,d)$ algorithm to check whether $f$ is an identically zero expression or not. We obtain this by generalizing the Amitsur-Levitzki theorem [AL50] to $\mathbb{F}\langle X, X^{-1}\rangle$. This also yields a deterministic identity testing algorithm (and even an expression reconstruction algorithm) that is polynomial time in the sparsity of the input expression. 2. Given an expression $f$ in $\mathbb{F}\langle X, X^{-1}\rangle$ of degree at most $D$, and sparsity $s$, as black-box, we can check whether $f$ is identically zero or not in randomized $\text{poly}(n,\log s, \log D)$ time.

Let $\mathbb{F}[X]$ be the polynomial ring over the variables $X=\{x_1,x_2, \ldots, x_n\}$. An ideal $I=\langle p_1(x_1), \ldots, p_n(x_n)\rangle$ generated by univariate polynomials $\{p_i(x_i)\}_{i=1}^n$ is a \emph{univariate ideal}. We study the ideal membership problem for the univariate ideals and show the following results. \item Let $f(X)\in\mathbb{F}[\ell_1, \ldots, \ell_r]$ be a (low rank) polynomial given by an arithmetic circuit where $\ell_i : 1\leq i\leq r$ are linear forms, and $I=\langle p_1(x_1), \ldots, p_n(x_n)\rangle$ be a univariate ideal. Given $\vec{\alpha}\in {\mathbb{F}}^n$, the (unique) remainder $f(X) \pmod I$ can be evaluated at $\vec{\alpha}$ in deterministic time $d^{O(r)}\cdot poly(n)$, where $d=\max\{\deg(f),\deg(p_1)\ldots,\deg(p_n)\}$. This yields an $n^{O(r)}$ algorithm for minimum vertex cover in graphs with rank-$r$ adjacency matrices. It also yields an $n^{O(r)}$ algorithm for evaluating the permanent of a $n\times n$ matrix of rank $r$, over any field $\mathbb{F}$. Over $\mathbb{Q}$, an algorithm of similar run time for low rank permanent is due to Barvinok[Bar96] via a different technique. \item Let $f(X)\in\mathbb{F}[X]$ be given by an arithmetic circuit of degree $k$ ($k$ treated as fixed parameter) and $I=\langle p_1(x_1), \ldots, p_n(x_n)\rangle$. We show in the special case when $I=\langle x_1^{e_1}, \ldots, x_n^{e_n}\rangle$, we obtain a randomized $O^*(4.08^k)$ algorithm that uses $poly(n,k)$ space. \item Given $f(X)\in\mathbb{F}[X]$ by an arithmetic circuit and $I=\langle p_1(x_1), \ldots, p_k(x_k) \rangle$, membership testing is $W[1]$-hard, parameterized by $k$. The problem is $MINI[1]$-hard in the special case when $I=\langle x_1^{e_1}, \ldots, x_k^{e_k}\rangle$.

Let $C$ be an arithmetic circuit of $poly(n)$ size given as input that computes a polynomial $f\in\mathbb{F}[X]$, where $X=\{x_1,x_2,\ldots,x_n\}$ and $\mathbb{F}$ is any field where the field arithmetic can be performed efficiently. We obtain new algorithms for the following two problems first studied by Koutis and Williams \cite{Kou08, Wi09, KW16}. k-MLC: Compute the sum of the coefficients of all degree-$k$ multilinear monomials in the polynomial $f$. k-MMD: Test if there is a nonzero degree-$k$ multilinear monomial in the polynomial $f$. Our algorithms are based on the fact that the Hadamard product $f\circ S_{n,k}$, is the degree-$k$ multilinear part of $f$, where $S_{n,k}$ is the $k^{th}$ elementary symmetric polynomial. 1. For k-MLC problem, we give a deterministic algorithm of run time $O^*(n^{k/2+c\log k})$ (where $c$ is a constant), answering an open question of Koutis and Williams \cite[ICALP'09]{KW16}. As corollaries, we show $O^*(\binom{n}{\downarrow k/2})$-time exact counting algorithms for several combinatorial problems: k-Tree, t-Dominating Set, m-Dimensional k-Matching. 2. For k-MMD problem, we give a randomized algorithm of run time $4.32^k\cdot poly(n,k)$. Our algorithm uses only $poly(n,k)$ space. This matches the run time of a recent algorithm \cite{BDH18} for $k-MMD$ which requires exponential (in $k$) space. Other results include fast deterministic algorithms for k-MLC and k-MMD problems for depth three circuits., Comment: 26 pages

Let $C$ be a depth-3 arithmetic circuit of size at most $s$, computing a polynomial $ f \in \mathbb{F}[x_1,\ldots, x_n] $ (where $\mathbb{F}$ = $\mathbb{Q}$ or $\mathbb{C}$) and the fan-in of the product gates of $C$ is bounded by $d$. We give a deterministic polynomial identity testing algorithm to check whether $f\equiv 0$ or not in time $ 2^d \text{ poly}(n,s) $., Comment: Result for finite fields has been added

In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10], and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing (PIT) and polynomial factorization over $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$ and show the following results. (1) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F} \{x_1,x_2,\ldots,x_n\}$ of degree $d$, we give a deterministic $poly(n,s,d)$ algorithm to decide if $f$ is identically zero polynomial or not. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz-Shpilka [RS05] for noncommutative ABPs. (2) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F} \{x_1,x_2,\ldots,x_n\}$ of degree $d$, we give an efficient deterministic algorithm to compute circuits for the irreducible factors of $f$ in time $poly(n,s,d)$ when $\mathbb{F}=\mathbb{Q}$. Over finite fields of characteristic $p$, our algorithm runs in time $poly(n,s,d,p)$.

An efficient randomized polynomial identity test for noncommutative polynomials given by noncommutative arithmetic circuits remains an open problem. The main bottleneck to applying known techniques is that a noncommutative circuit of size $s$ can compute a polynomial of degree exponential in $s$ with a double-exponential number of nonzero monomials. In this paper, we report some progress by dealing with two natural subcases (both allow for polynomials of exponential degree and a double exponential number of monomials): (1) We consider \emph{$+$-regular} noncommutative circuits: these are homogeneous noncommutative circuits with the additional property that all the $+$-gates are layered, and in each $+$-layer all gates have the same syntactic degree. We give a \emph{white-box} polynomial-time deterministic polynomial identity test for such circuits. Our algorithm combines some new structural results for $+$-regular circuits with known results for noncommutative ABP identity testing [RS05PIT], rank bound of commutative depth three identities [SS13], and equivalence testing problem for words [Loh15, MSU97, Pla94]. (2) Next, we consider $\Sigma\Pi^*\Sigma$ noncommutative circuits: these are noncommutative circuits with layered $+$-gates such that there are only two layers of $+$-gates. These $+$-layers are the output $+$-gate and linear forms at the bottom layer; between the $+$-layers the circuit could have any number of $\times$ gates. We given an efficient randomized \emph{black-box} identity testing problem for $\Sigma\Pi^*\Sigma$ circuits. In particular, we show if $f\in F$ is a nonzero noncommutative polynomial computed by a $\Sigma\Pi^*\Sigma$ circuit of size $s$, then $f$ cannot be a polynomial identity for the matrix algebra $\mathbb{M}_s(F)$, where the field $F$ is a sufficiently large extension of $F$ depending on the degree of $f$.

We consider the problem of locally describing tubular geometry around a submanifold embedded in a (pseudo)Riemannian manifold in its general form. Given the geometry of ambient space in an arbitrary coordinate system and equations determining the submanifold in the same system, we compute the tubular expansion coefficients in terms of this {\it a priori data}. This is done by using an indirect method that crucially applies the tubular expansion theorem for vielbein previously derived. With an explicit construction involving the relevant coordinate and non-coordinate frames we verify consistency of the whole method up to quadratic order in vielbein expansion. Furthermore, we perform certain (long and tedious) higher order computation which verifies the first non-trivial spin connection term in the expansion for the first time. Earlier a similar method was used to compute tubular geometry in loop space. We explain this work in the light of our general construction., Comment: 40 pages

In this paper we show that the black-box polynomial identity testing for noncommutative polynomials $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ of degree $D$ and sparsity $t$, can be done in randomized $\poly(n,\log t,\log D)$ time. As a consequence, if the black-box contains a circuit $C$ of size $s$ computing $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ which has at most $t$ non-zero monomials, then the identity testing can be done by a randomized algorithm with running time polynomial in $s$ and $n$ and $\log t$. This makes significant progress on a question that has been open for over ten years. The earlier result by Bogdanov and Wee [BW05], using the classical Amitsur-Levitski theorem, gives a randomized polynomial-time algorithm only for circuits of polynomially bounded syntactic degree. In our result, we place no restriction on the degree of the circuit. Our algorithm is based on automata-theoretic ideas introduced in [AMS08,AM08]. In those papers, the main idea was to construct deterministic finite automata that isolate a single monomial from the set of nonzero monomials of a polynomial $f$ in $\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$. In the present paper, since we need to deal with exponential degree monomials, we carry out a different kind of monomial isolation using nondeterministic automata., Comment: As the number of monomials in a noncommutative polynomial which has anarithmetic circuit of size $s$ can actually be doubly exponential in $s$, our result does not imply a randomized polynomial-time identity test for all size s noncommutative circuits. The algorithm works only for noncommutative size s circuits which computes a polynomial with exp(s) many monomials

Motivated by the computation of loop space quantum mechanics as indicated in [7], here we seek a better understanding of the tubular geometry of loop space ${\cal L}{\cal M}$ corresponding to a Riemannian manifold ${\cal M}$ around the submanifold of vanishing loops. Our approach is to first compute the tubular metric of $({\cal M}^{2N+1})_{C}$ around the diagonal submanifold, where $({\cal M}^N)_{C}$ is the Cartesian product of $N$ copies of ${\cal M}$ with a cyclic ordering. This gives an infinite sequence of tubular metrics such that the one relevant to ${\cal L}{\cal M}$ can be obtained by taking the limit $N\to \infty$. Such metrics are computed by adopting an indirect method where the general tubular expansion theorem of [12] is crucially used. We discuss how the complete reparametrization isometry of loop space arises in the large-$N$ limit and verify that the corresponding Killing equation is satisfied to all orders in tubular expansion. These tubular metrics can alternatively be interpreted as some natural Riemannian metrics on certain bundles of tangent spaces of ${\cal M}$ which, for ${\cal M} \times {\cal M}$, is the tangent bundle $T{\cal M}$., Comment: 54 pages. A footnote and acknowledgement added. Journal version

Recently, Gupta et.al. [GKKS2013] proved that over Q any $n^{O(1)}$-variate and $n$-degree polynomial in VP can also be computed by a depth three $\Sigma\Pi\Sigma$ circuit of size $2^{O(\sqrt{n}\log^{3/2}n)}$. Over fixed-size finite fields, Grigoriev and Karpinski proved that any $\Sigma\Pi\Sigma$ circuit that computes $Det_n$ (or $Perm_n$) must be of size $2^{\Omega(n)}$ [GK1998]. In this paper, we prove that over fixed-size finite fields, any $\Sigma\Pi\Sigma$ circuit for computing the iterated matrix multiplication polynomial of $n$ generic matrices of size $n\times n$, must be of size $2^{\Omega(n\log n)}$. The importance of this result is that over fixed-size fields there is no depth reduction technique that can be used to compute all the $n^{O(1)}$-variate and $n$-degree polynomials in VP by depth 3 circuits of size $2^{o(n\log n)}$. The result [GK1998] can only rule out such a possibility for depth 3 circuits of size $2^{o(n)}$. We also give an example of an explicit polynomial ($NW_{n,\epsilon}(X)$) in VNP (not known to be in VP), for which any $\Sigma\Pi\Sigma$ circuit computing it (over fixed-size fields) must be of size $2^{\Omega(n\log n)}$. The polynomial we consider is constructed from the combinatorial design. An interesting feature of this result is that we get the first examples of two polynomials (one in VP and one in VNP) such that they have provably stronger circuit size lower bounds than Permanent in a reasonably strong model of computation. Next, we prove that any depth 4 $\Sigma\Pi^{[O(\sqrt{n})]}\Sigma\Pi^{[\sqrt{n}]}$ circuit computing $NW_{n,\epsilon}(X)$ (over any field) must be of size $2^{\Omega(\sqrt{n}\log n)}$. To the best of our knowledge, the polynomial $NW_{n,\epsilon}(X)$ is the first example of an explicit polynomial in VNP such that it requires $2^{\Omega(\sqrt{n}\log n)}$ size depth four circuits, but no known matching upper bound.

Tavenas has recently proved that any n^{O(1)}-variate and degree n polynomial in VP can be computed by a depth-4 circuit of size 2^{O(\sqrt{n}\log n)}. So to prove VP not equal to VNP, it is sufficient to show that an explicit polynomial in VNP of degree n requires 2^{\omega(\sqrt{n}\log n)} size depth-4 circuits. Soon after Tavenas's result, for two different explicit polynomials, depth-4 circuit size lower bounds of 2^{\Omega(\sqrt{n}\log n)} have been proved Kayal et al. and Fournier et al. In particular, using combinatorial design Kayal et al.\ construct an explicit polynomial in VNP that requires depth-4 circuits of size 2^{\Omega(\sqrt{n}\log n)} and Fournier et al.\ show that iterated matrix multiplication polynomial (which is in VP) also requires 2^{\Omega(\sqrt{n}\log n)} size depth-4 circuits. In this paper, we identify a simple combinatorial property such that any polynomial f that satisfies the property would achieve similar circuit size lower bound for depth-4 circuits. In particular, it does not matter whether f is in VP or in VNP. As a result, we get a very simple unified lower bound analysis for the above mentioned polynomials. Another goal of this paper is to compare between our current knowledge of depth-4 circuit size lower bounds and determinantal complexity lower bounds. We prove the that the determinantal complexity of iterated matrix multiplication polynomial is \Omega(dn) where d is the number of matrices and n is the dimension of the matrices. So for d=n, we get that the iterated matrix multiplication polynomial achieves the current best known lower bounds in both fronts: depth-4 circuit size and determinantal complexity. To the best of our knowledge, a \Theta(n) bound for the determinantal complexity for the iterated matrix multiplication polynomial was known only for constant d>1 by Jansen., Comment: Extension of the previous upload

We consider tubular neighborhood of an arbitrary submanifold embedded in a (pseudo-)Riemannian manifold. This can be described by Fermi normal coordinates (FNC) satisfying certain conditions as described by Florides and Synge in \cite{FS}. By generalizing the work of Muller {\it et al} in \cite{muller} on Riemann normal coordinate expansion, we derive all order FNC expansion of vielbein in this neighborhood with closed form expressions for the curvature expansion coefficients. Our result is shown to be consistent with certain integral theorem for the metric proved in \cite{FS}., Comment: 27 pages. Corrected an error in a class of coefficients resulting from a typo. Integral theorem and all other results remain unchanged

Following earlier work, we view two dimensional non-linear sigma model with target space $\cM$ as a single particle relativistic quantum mechanics in the corresponding free loop space $\cLM$. In a natural semi-classical limit ($\hbar=\alpha' \to 0$) of this model the wavefunction localizes on the submanifold of vanishing loops which is isomorphic to $\cM$. One would expect that the relevant semi-classical expansion should be related to the tubular expansion of the theory around the submanifold and an effective dynamics on the submanifold is obtainable using Born-Oppenheimer approximation. In this work we develop a framework to carry out such an analysis at the leading order in $\alpha'$-expansion. In particular, we show that the linearized tachyon effective equation is correctly reproduced up to divergent terms all proportional to the Ricci scalar of $\cM$. The steps leading to this result are as follows: first we define a finite dimensional analogue of the loop space quantum mechanics (LSQM) where we discuss its tubular expansion and how that is related to a semi-classical expansion of the Hamiltonian. Then we study an explicit construction of the relevant tubular neighborhood in $\cLM$ using exponential maps. Such a tubular geometry is obtained from a Riemannian structure on the tangent bundle of $\cM$ which views the zero-section as a submanifold admitting a tubular neighborhood. Using this result and exploiting an analogy with the toy model we arrive at the final result for LSQM., Comment: 35 pages, 2 figures, some changes for better readability