Sign in
Back
Arithmetic circuit classes over Z m
Technical documentation   Open access

Arithmetic circuit classes over Z m

Eric Allender and Asa Goodwillie
Rutgers University
09/05/2015
DOI:
https://doi.org/10.7282/00000006

Abstract

Complexity Theory Arithmetic Circuits Computer Theory
We continue the study of the complexity classes VP(Zm) and ΛP(Zm) which was initiated in [AGM15]. We distinguish between " strict " and " lax " versions of these classes and prove some new equalities and inclusions between these arithmetic circuit classes and various subclasses of ACC 1 .
pdf
strict236.13 kBDownloadView
Electronic Colloquium on Computational Complexity, TR 15-145; https://eccc.weizmann.ac.il/report/2015/145/ Open Access

Metrics

13 File downloads
24 Record Views

Details