Skip to main content

Subspace-invariant AC0 formulas

Publication ,  Journal Article
Rossman, B
Published in: Logical Methods in Computer Science
January 1, 2019

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 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·2dn1/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/d−1) lower bound on the P-invariant 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 U-invariant and non-constant over V, then its U-invariant 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⊥.

Duke Scholars

Published In

Logical Methods in Computer Science

DOI

EISSN

1860-5974

Publication Date

January 1, 2019

Volume

15

Issue

3

Start / End Page

3:1-3:12

Related Subject Headings

  • 0803 Computer Software
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2019). Subspace-invariant AC0 formulas. Logical Methods in Computer Science, 15(3), 3:1-3:12. https://doi.org/10.23638/LMCS-15(3:3)2019
Rossman, B. “Subspace-invariant AC0 formulas.” Logical Methods in Computer Science 15, no. 3 (January 1, 2019): 3:1-3:12. https://doi.org/10.23638/LMCS-15(3:3)2019.
Rossman B. Subspace-invariant AC0 formulas. Logical Methods in Computer Science. 2019 Jan 1;15(3):3:1-3:12.
Rossman, B. “Subspace-invariant AC0 formulas.” Logical Methods in Computer Science, vol. 15, no. 3, Jan. 2019, pp. 3:1-3:12. Scopus, doi:10.23638/LMCS-15(3:3)2019.
Rossman B. Subspace-invariant AC0 formulas. Logical Methods in Computer Science. 2019 Jan 1;15(3):3:1-3:12.

Published In

Logical Methods in Computer Science

DOI

EISSN

1860-5974

Publication Date

January 1, 2019

Volume

15

Issue

3

Start / End Page

3:1-3:12

Related Subject Headings

  • 0803 Computer Software
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics