A Caltech Library Service

The Complexity of DNF of Parities

Cohen, Gil and Shinkar, Igor (2016) The Complexity of DNF of Parities. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery , New York, NY, pp. 47-58. ISBN 978-1-4503-4057-1.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We study depth 3 circuits of the form OR-AND-XOR, or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a 2^({Ω(n)) lower bound, using graph theoretic arguments, for explicit functions. Several related models have gained attention in the last few years, such as parity decision trees, the parity kill number and AC^0-XOR circuits. For a Boolean function f on the n dimensional Boolean cube, we denote by DNFParity(f) the least integer s for which there exists an OR-AND-XOR circuit, with OR gate of fan-in s, that computes f. We summarize some of our results: • For any affine disperser f for dimension k, it holds that DNFParity(f) is bounded below by 2^({n-2k). By plugging Shaltiel's affine disperser (FOCS'11) we obtain an explicit 2^({n-no(1)) lower bound. • We give a non-trivial general upper bound by showing that DNFParity(f) < O(2^(n/n)) for any function f on n bits. This bound is shown to be tight up to an O(log n) factor. • We show that for any symmetric function f it holds that DNFParity(f) < 1.5^(n poly(n)). Furthermore, there exists a symmetric function f for which this bound is tight up to a polynomial factor. • For threshold functions we show tighter bounds. For example, we show that the majority function has DNFParity complexity of 2^({n/2) poly(n). This is also tight up to a polynomial factor. • For the inner product function IP on n inputs we show that DNFParity(IP) = 2^({n/2}-1). Previously, Jukna gave a lower bound of Ω(2^(n/4)) for the DNFParity complexity of this function. We further give bounds for any low degree polynomial. • Finally, we obtain a 2^(n-o(n)) average case lower bound for the parity decision tree model using affine extractors.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM. We wish to thank Elazar Goldenberg for discussions at early stages of this work. We thank Johan Håstad for some helpful conversations regarding this work, in particular for a key idea which enabled us to prove Theorem 1.4.
Record Number:CaltechAUTHORS:20160120-112434887
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:63802
Deposited By: Tony Diaz
Deposited On:20 Jan 2016 20:18
Last Modified:04 Jan 2017 23:48

Repository Staff Only: item control page