2026-08-12T09:11:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6317 2024-03-06T10:37:42Z ddc:004 open_access

Improved Bounds on the Sign-Rank of AC^0 Bun, Mark Thaler, Justin Sign-rank circuit complexity communication complexity constant-depth circuits The sign-rank of a matrix A with entries in {-1, +1} is the least rank of a real matrix B with A_{ij}*B_{ij} > 0 for all i, j. Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in AC^0, answering an old question of Babai, Frankl, and Simon (1986). Specifically, they exhibited a matrix A = [F(x,y)]_{x,y} for a specific function F:{-1,1}^n*{-1,1}^n -> {-1,1} in AC^0, such that A has sign-rank exp(Omega(n^{1/3}). We prove a generalization of Razborov and Sherstov’s result, yielding exponential sign-rank lower bounds for a non-trivial class of functions (that includes the function used by Razborov and Sherstov). As a corollary of our general result, we improve Razborov and Sherstov's lower bound on the sign-rank of AC^0 from exp(Omega(n^{1/3})) to exp(~Omega(n^{2/5})). We also describe several applications to communication complexity, learning theory, and circuit complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark Bun and Justin Thaler 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.37 urn:nbn:de:0030-drops-63173 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.37 eng https://creativecommons.org/licenses/by/3.0/legalcode