Source author record

Adrian She

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity math.CO

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A Quadratic Lower Bound for Algebraic Branching Programs and Formulas

We show that any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $Ω(n^2)$ vertices. This improves upon the lower bound of $Ω(n\log n)$ , which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results in [K19], which showed a quadratic lower bound for \emph{homogeneous} ABPs computing the same polynomial. Our proof relies on a notion of depth reduction which is reminiscent of similar statements in the context of matrix rigidity, and shows that any small enough ABP computing the polynomial $\sum_{i=1}^n x_i^n$ can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial $\sum_{i = 1}^n x_i^n + ε(x_1, \ldots, x_n)$ , for a structured "error polynomial" $ε(x_1, \ldots, x_n)$ . To complete the proof, we then observe that the lower bound in [K19] is robust enough and continues to hold for all polynomials $\sum_{i = 1}^n x_i^n + ε(x_1, \ldots, x_n)$ , where $ε(x_1, \ldots, x_n)$ has the appropriate structure. We also use our ideas to show an $Ω(n^2)$ lower bound of the size of algebraic formulas computing the elementary symmetric polynomial of degree $0.1n$ on $n$ variables. This is a slight improvement upon the prior best known formula lower bound (proved for a different polynomial) of $Ω(n^2/\log n)$ [Nec66, K85, SY10]. Interestingly, this lower bound is asymptotically better than $n^2/\log n$ , the strongest lower bound that can be proved using previous methods. This lower bound also matches the upper bound, due to Ben-Or, who showed that elementary symmetric polynomials can be computed by algebraic formula (in fact depth- $3$ formula) of size $O(n^2)$ . Prior to this work, Ben-Or's construction was known to be optimal only for algebraic formulas of depth- $3$ [SW01].

preprint2020arXiv

Chromatic Posets

In 1995 Stanley introduced the chromatic symmetric function $X_G$ of a graph $G$ , whose $e$ -positivity and Schur-positivity has been of large interest. In this paper we study the relative $e$ -positivity and Schur-positivity between connected graphs on $n$ vertices. We define and investigate two families of posets on distinct chromatic symmetric functions. The relations depend on the $e$ -positivity or Schur-positivity of a weighed subtraction between $X_G$ and $X_H$ . We find a biconditional condition between $e$ -positivity or Schur-positivity and the relation to the complete graph. This gives a new paradigm for $e$ -positivity and for Schur-positivity. We show many other interesting properties of these posets including that trees form an independent set and are maximal elements. Additionally, we find that stars are independent elements, the independence number increases as we increase in the poset and that the family of lollipop graphs form a chain.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.