Paper Info
Title
SUBSPACE-INVARIANT AC(0 )FORMULAS
Abstract
We consider the action of a linear subspace U of {0, 1}(n) on the set of AC(0) formulas with inputs labeled by literals in the set {X-1, (X) over bar (1), . . . , X-n, (X) over bar (n)}, where an element u is an element of U acts on formulas by transposing the ith pair of literals for all i is an element of [n] such that u(i) = 1. A formula is 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(n.2(dn1/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 2(d(n1/d-1)) lower bound on the P-invariant depth d + 1 formula size of PARITY. Quantitatively this improves the best known Omega(2(1/84)(d(n1/d-1))) lower bound for unrestricted depth d + 1 formulas [Ros15], while avoiding the use of the switching lemma More generally, for any linear subspaces U subset of V, 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 2(d(m1/d-1)) where m is the minimum Hamming weight of a vector in U-perpendicular to\V-perpendicular to.
Year
DOI
Venue
2019
10.23638/LMCS-15(3:3)2019
LOGICAL METHODS IN COMPUTER SCIENCE
Keywords
DocType
Volume
circuit complexity,formula size,AC(0),parity,symmetric computation
Journal
15
Issue
ISSN
Citations 
3
1860-5974
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Benjamin Rossman144.28