Dual VP Classes

Eric Allender, Anna Gál & Ian Mertz
We consider the complexity class ACC^1 and related families of arithmetic circuits. We prove a variety of collapse results, showing several settings in which no loss of computational power results if fan-in of gates is severely restricted, as well as presenting a natural class of arithmetic circuits in which no expressive power is lost by severely restricting the algebraic degree of the circuits. These results tend to support a conjecture regarding the computational power of...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.