Article ; Online: Subspace-Invariant AC$^0$ Formulas
Logical Methods in Computer Science, Vol Volume 15, Issue
2019 Volume 3
Abstract: ... invariant depth $d+1$ formula size is at least $2^{d(m^{1/d}-1)}$ where $m$ is the minimum Hamming weight ... known recursive construction of depth $d+1$ formulas of size $O(n{\cdot}2^{dn^{1/d}})$ computing the $n$ ... of even-weight elements of $\{0,1\}^n$. In this paper we establish a nearly matching $2^{d(n^{1/d}-1 ...
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,\overline X_1,\dots,X_n,\overline X_n\}$, where an element $u \in U$ acts on formulas by transposing the $i$th pair of literals for all $i \in [n]$ such that $u_i=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(n{\cdot}2^{dn^{1/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(n^{1/d}-1)}$ lower bound on the $P$-invariant depth $d+1$ formula size of PARITY. Quantitatively this improves the best known $\Omega(2^{\frac{1}{84}d(n^{1/d}-1)})$ lower bound for {\em unrestricted} depth $d+1$ formulas, while avoiding the use of the switching lemma. More generally, for any linear subspaces $U \subset 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(m^{1/d}-1)}$ where $m$ is the minimum Hamming weight of a vector in $U^\bot \setminus V^\bot$. |
---|---|
Keywords | computer science - logic in computer science ; computer science - computational complexity ; Logic ; BC1-199 ; Electronic computers. Computer science ; QA75.5-76.95 |
Subject code | 511 |
Language | English |
Publishing date | 2019-07-01T00:00:00Z |
Publisher | Logical Methods in Computer Science e.V. |
Document type | Article ; Online |
Database | BASE - Bielefeld Academic Search Engine (life sciences selection) |
Full text online
More links
Kategorien
Inter-library loan at ZB MED
Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.