Department of Computer Science
slider.jpeg
previous arrow
next arrow
PlayPause

Department of Computer Science

  • Publication Type: Journal Publications
  • Author Name:

    Eric Allender, Anna Gal, and Ian Mertz

  • 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. 

We are committed to fostering a safe environment while upholding the principles of academic freedom and free expression of our community.

We're Hiring

Hiring CompSci

Undergraduate

Undergrad CompSci

Graduate

Grad CompSci 2016 06 17 0136 Rutgers SAS SQ

Research

Research CompSci 2018 08 29 0224 RU SAS SQ