Department of Computer Science
Dual VP Classes
- Publication Type: Journal Publications
- Publication Date: 2016-10-01
- Journal Volume: Computational Complexity
- Link to Content 1: Dual VP Classes
- Abstract:
We consider the complexity class ACC1 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. We draw attention to the strong connections that exist between ACC1 and VP, via connections to the classes CC1[m] for various m. These results tend to support a conjecture regarding the computational power of the complexity class VP over finite algebras, and they also highlight the significance of a class of arithmetic circuits that is in some sense dual to VP. In particular, these dual-VP classes provide new characterizations of ACC1 and TC1 in terms of circuits of semiunbounded fan-in. As a corollary, we show that ACCi = CCi for all i ≥ 1.
Upcoming Events
| 05 May 2026; - 11:00AM - 12:00PM Advances in Watermarking Large Language Models |
| 05 May 2026; - 11:20AM - 12:20PM Trustworthy AI for Structured Reasoning: Conformal Guarantees in Knowledge Graph Question Answering |
| 06 May 2026; - 03:30PM - 04:30PM Towards Universal and Interactive Medical Image Segmentation |







