Ryan Williams recently published a draft proving new lower bounds for ACC circuits. ACC (often known as ACC0) is the class of constant depth circuits with unbounded fan-in gates, where the usual AND/OR/NOT gates are supplemented by MODm gates for some constant m.
(more…)
New ACC circuit lower bounds
Tags: papers
Ryan Williams recently published a draft proving new lower bounds for ACC circuits. ACC (often known as ACC0) is the class of constant depth circuits with unbounded fan-in gates, where the usual AND/OR/NOT gates are supplemented by MODm gates for some constant m.
(more…)