Constraints

9 November 2010

New ACC circuit lower bounds

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

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…)

Blog at WordPress.com.