Benjamin Rossman - Subspace-Invariant AC0 Formulas

lmcs:4588 - Logical Methods in Computer Science, July 24, 2019, Volume 15, Issue 3 - https://doi.org/10.23638/LMCS-15(3:3)2019
Subspace-Invariant AC0 FormulasArticle

Authors: Benjamin Rossman

    We consider the action of a linear subspace U of {0,1}n on the set of AC0 formulas with inputs labeled by literals in the set {X1,¯X1,,Xn,¯Xn}, where an element uU acts on formulas by transposing the ith pair of literals for all i[n] such that ui=1. A formula is {\em U-invariant} if it is fixed by this action. For example, there is a well-known recursive construction of depth d+1 formulas of size O(n2dn1/d) computing the n-variable PARITY function; these formulas are easily seen to be P-invariant where P is the subspace of even-weight elements of {0,1}n. In this paper we establish a nearly matching 2d(n1/d1) lower bound on the P-invariant depth d+1 formula size of PARITY. Quantitatively this improves the best known Ω(2184d(n1/d1)) lower bound for {\em unrestricted} depth d+1 formulas, while avoiding the use of the switching lemma. More generally, for any linear subspaces UV, we show that if a Boolean function is U-invariant and non-constant over V, then its U-invariant depth d+1 formula size is at least 2d(m1/d1) where m is the minimum Hamming weight of a vector in UV.


    Volume: Volume 15, Issue 3
    Published on: July 24, 2019
    Accepted on: January 30, 2019
    Submitted on: June 14, 2018
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    Classifications

    Consultation statistics

    This page has been seen 1827 times.
    This article's PDF has been downloaded 310 times.