Header menu link for other important links
X
Lower bounds for sum and sum of products of read-once formulas
Published in Association for Computing Machinery
2019
Volume: 11
   
Issue: 2
Abstract
We study limitations of polynomials computed by depth-2 circuits built over read-once formulas (ROFs). In particular: • We prove a 2Ω(n) lower bound for the sum of ROFs computing the 2n-variate polynomial in VP defined by Raz and Yehudayoff [21]. • We obtain a 2Ω(n) lower bound on the size of ΣΠ[n1/15] arithmetic circuits built over restricted ROFs of unbounded depth computing the permanent of an n × n matrix (superscripts on gates denote bound on the fan-in). The restriction is that the number of variables with + gates as a parent in a proper sub formula of the ROF has to be bounded by n. This proves an exponential lower bound for a subclass of possibly non-multilinear formulas of unbounded depth computing the permanent polynomial. • We also show an exponential lower bound for the above model against a polynomial in VP. • Finally, we observe that the techniques developed yield an exponential lower bound on the size of ΣΠ[N1/30] arithmetic circuits built over syntactically multi-linear ΣΠΣ[N1/4] arithmetic circuits computing a product of variable disjoint linear forms on N variables, where the superscripts on gates denote bound on the fan-in. Our proof techniques are built on the measure developed by Kumar et al. [14] and are based on a non-trivial analysis of ROFs under random partitions. Further, our results exhibit strengths and provide more insight into the lower bound techniques introduced by Raz [19]. © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.
About the journal
JournalData powered by TypesetACM Transactions on Computation Theory
PublisherData powered by TypesetAssociation for Computing Machinery
ISSN19423454
Open AccessNo
Concepts (12)
  •  related image
    Electric network analysis
  •  related image
    Logic circuits
  •  related image
    Polynomials
  •  related image
    ALGEBRAIC COMPLEXITY THEORIES
  •  related image
    Arithmetic circuit
  •  related image
    ARITHMETIC FORMULAS
  •  related image
    LOWER BOUND TECHNIQUES
  •  related image
    Lower bounds
  •  related image
    RANDOM PARTITIONS
  •  related image
    READ-ONCE FORMULAS
  •  related image
    SUM OF PRODUCTS
  •  related image
    Computer circuits