License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.22
URN: urn:nbn:de:0030-drops-115844
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11584/
Go to the corresponding LIPIcs Volume Portal


Limaye, Nutan ; Srinivasan, Srikanth ; Tripathi, Utkarsh

More on AC^0[oplus] and Variants of the Majority Function

pdf-format:
LIPIcs-FSTTCS-2019-22.pdf (0.6 MB)


Abstract

In this paper we prove two results about AC^0[oplus] circuits. (1) We show that for d(N) = o(sqrt(log N/log log N)) and N <= s(N) <= 2^(dN^(1/4d^2)) there is an explicit family of functions {f_N:{0,1}^N - > {0,1}} such that - f_N has uniform AC^0 formulas of depth d and size at most s; - f_N does not have AC^0[oplus] formulas of depth d and size s^epsilon, where epsilon is a fixed absolute constant. This gives a quantitative improvement on the recent result of Limaye, Srinivasan, Sreenivasaiah, Tripathi, and Venkitesh, (STOC, 2019), which proved a similar Fixed-Depth Size-Hierarchy theorem but for d << log log N and s << exp(N^(1/2^Omega(d))). As in the previous result, we use the Coin Problem to prove our hierarchy theorem. Our main technical result is the construction of uniform size-optimal formulas for solving the coin problem with improved sample complexity (1/delta)^O(d) (down from (1/delta)^(2^O(d)) in the previous result). (2) In our second result, we show that randomness buys depth in the AC^0[oplus] setting. Formally, we show that for any fixed constant d >= 2, there is a family of Boolean functions that has polynomial-sized randomized uniform AC^0 circuits of depth d but no polynomial-sized (deterministic) AC^0[oplus] circuits of depth d. Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least 2) is essential to avoid superpolynomial blow-up while derandomizing randomized AC^0 circuits. We show that an increase in depth (by at least 1) is essential even for AC^0[oplus]. As in Viola's result, the separating examples are promise variants of the Majority function on N inputs that accept inputs of weight at least N/2 + N/(log N)^(d-1) and reject inputs of weight at most N/2 - N/(log N)^(d-1).

BibTeX - Entry

@InProceedings{limaye_et_al:LIPIcs:2019:11584,
  author =	{Nutan Limaye and Srikanth Srinivasan and Utkarsh Tripathi},
  title =	{{More on AC^0[oplus] and Variants of the Majority Function}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11584},
  URN =		{urn:nbn:de:0030-drops-115844},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.22},
  annote =	{Keywords: AC^0[oplus], Coin Problem, Promise Majority}
}

Keywords: AC^0[oplus], Coin Problem, Promise Majority
Seminar: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 10.12.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI