Improved bounds on the sign-rank of AC^0

DOI10.4230/LIPICS.ICALP.2016.37MaRDI QIDQ4598174zbMATH OpenOpenAlexFDO

Authors Mark Bun, Justin Thaler

Publication date 19 December 2017

Full work available at URL https://dblp.uni-trier.de/db/conf/icalp/icalp2016.html#BunT16

zbMATH Keywords

circuit complexitycommunication complexityconstant-depth circuitssign-rank

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Sign-Rank of AC^0
• Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
• A short list of equalities induces large sign-rank
• Sign rank versus Vapnik-Chervonenkis dimension
• Separating AC\(^0\) from depth-2 majority circuits

Cited in

(15)

• The Sign-Rank of AC^0
• Sign rank versus Vapnik-Chervonenkis dimension
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
• Sign-rank can increase under intersection
• A short list of equalities induces large sign-rank
• Sign-rank can increase under intersection
• Sign rank vs discrepancy
• Sign-rank vs. discrepancy
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• On the power of statistical zero knowledge
• The large-error approximate degree of \(\mathrm{AC}^0\)
• Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
• The large-error approximate degree of \(\mathrm{AC}^0\)
• A Borsuk-Ulam lower bound for sign-rank and its applications
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees

This page was built for publication: Improved bounds on the sign-rank of \(\mathrm{AC}^0\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598174)