License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.22
URN: urn:nbn:de:0030-drops-115844
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11584/
Limaye, Nutan ;
Srinivasan, Srikanth ;
Tripathi, Utkarsh
More on AC^0[oplus] and Variants of the Majority Function
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 |
|
Collection: |
|
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.12.2019 |
