Improved Bounds on the Sign-Rank of AC^0

DOI10.4230/LIPIcs.ICALP.2016.37zbMath1388.68106OpenAlexW2547369620MaRDI QIDQ4598174

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

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

Related Items (8)

A Short List of Equalities Induces Large Sign-Rank ⋮ Unnamed Item ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ On the Power of Statistical Zero Knowledge ⋮ Unnamed Item ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Sign rank vs discrepancy ⋮ Unnamed Item

This page was built for publication: Improved Bounds on the Sign-Rank of AC^0