Journal
SIAM JOURNAL ON COMPUTING
Volume 52, Issue 2, Pages -Publisher
SIAM PUBLICATIONS
DOI: 10.1137/20M1312459
Keywords
constant-depth circuits; sign-rank; threshold degree; sign-representation by polynomials; communication complexity; unbounded-error communication
Ask authors/readers for more resources
The threshold degree and sign-rank of Boolean functions and matrices are important open problems with various applications. This study provides a significant breakthrough by introducing an optimal solution for determining the maximum threshold degree and sign-rank achievable by constant-depth circuits. The results improve upon previous lower bounds and subsume previous work on related quantities.
The threshold degree of a Boolean function f : {0, 1}(n) -> {0, 1} is the minimum degree of a real polynomial p that represents f in sign: sgn p(x) = (-1)(f(x)). A related notion is sign-rank, defined for a Boolean matrix F = [F-ij] as the minimum rank of a real matrix M with sgn Mij = (-1)(Fij). Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits (AC(0)) is a well-known and extensively studied open problem with complexity-theoretic and algorithmic applications. We give an essentially optimal solution to this problem. For any epsilon > 0, we construct an AC(0) circuit in n variables that has threshold degree Omega(n(1-epsilon)) and sign-rank exp(Omega(n(1-epsilon))), improving on the previous best lower bounds of Omega(root n) and exp((Omega) over tilde(root n)), respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of AC(0) circuits of any given depth, with a strict improvement starting at depth 4. As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of AC(0), strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of AC(0).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available