Math @ Duke

Publications [#348668] of Benjamin Rossman
Papers Published
 Rossman, B, Subspaceinvariant AC^{0} formulas,
Logical Methods in Computer Science, vol. 15 no. 3
(January, 2019),
pp. 3:13:12 [doi]
(last updated on 2022/05/19)
Abstract: 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 (formula presented), where an element u ∈ U acts on formulas by transposing the ith pair of literals for all i ∈ [n] such that ui = 1. A formula is Uinvariant if it is fixed by this action. For example, there is a wellknown recursive construction of depth d + 1 formulas of size O(n·2dn1/d) computing the nvariable parity function; these formulas are easily seen to be Pinvariant where P is the subspace of evenweight elements of {0, 1}n. In this paper we establish a nearly matching 2d(n1/d−1) lower bound on the Pinvariant depth d + 1 formula size of parity. Quantitatively this improves the best known (formula presented) lower bound for unrestricted depth d + 1 formulas [Ros15], while avoiding the use of the switching lemma. More generally, for any linear subspaces U ⊂ V, we show that if a Boolean function is Uinvariant and nonconstant over V, then its Uinvariant depth d + 1 formula size is at least 2d(m1/d−1) where m is the minimum Hamming weight of a vector in U⊥\V⊥.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

