Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR14-122 | 13th July 2016 03:30

Dual VP Classes

RSS-Feed




Revision #2
Authors: Eric Allender, Anna Gal, Ian Mertz
Accepted on: 13th July 2016 03:30
Downloads: 127
Keywords: 


Abstract:

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of
a class of high-degree polynomials that can be simulated via arithmetic circuits of much lower degree.



Changes to previous version:

Some minor errors are corrected, and the exposition is clarified in a few places.


Revision #1 to TR14-122 | 24th June 2015 15:13

Dual VP Classes





Revision #1
Authors: Eric Allender, Anna Gal, Ian Mertz
Accepted on: 24th June 2015 15:13
Downloads: 360
Keywords: 


Abstract:

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. We also give characterizations of ACC^1 and TC^1 in terms of circuits consisting only of MOD gates. 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.



Changes to previous version:

There was a mis-statement in Proposition 2; see Proposition 3 and Corollary 2 in the new version.
Several results have been strengthened, including Corollaries 3 and 5, and Theorems 7 and 10. Various improvements have been made to the presentation and exposition.


Paper:

TR14-122 | 30th September 2014 11:04

Dual VP Classes





TR14-122
Authors: Eric Allender, Anna Gal, Ian Mertz
Publication: 30th September 2014 11:04
Downloads: 1230
Keywords: 


Abstract:

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of
a class of high-degree polynomials that can be simulated via arithmetic circuits of much lower degree.



ISSN 1433-8092 | Imprint