9 November 2010

New ACC circuit lower bounds

Filed under: Commentary — András Salamon @ 17:25

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.


Create a free website or blog at