Math @ Duke

Publications [#348676] of Benjamin Rossman
Papers Published
 Rossman, B, Subspaceinvariant AC^{0} formulas,
Leibniz International Proceedings in Informatics, Lipics, vol. 80
(July, 2017), ISBN 9783959770415 [doi]
(last updated on 2022/05/21)
Abstract: The nvariable PARITY function is computable (by a wellknown recursive construction) by AC0 formulas of depth d + 1 and leafsize n·2dn1/d. These formulas are seen to possess a certain symmetry: they are syntactically invariant under the subspace P of evenweight elements in {0, 1}n, which acts (as a group) on formulas by toggling negations on input literals. In this paper, we prove a 2d(n1/d1) lower bound on the size of syntactically Pinvariant depth d + 1 formulas for PARITY. Quantitatively, this beats the best 2ω(d(n1/d1)) lower bound in the noninvariant setting [16].


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

