Arithmetic circuit classes over Z m

Eric Allender; Asa Goodwillie

doi:10.7282/00000006

Back

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 .

Files and links (2)

pdf

strict236.13 kBDownload View

Electronic Colloquium on Computational Complexity, TR 15-145; https://eccc.weizmann.ac.il/report/2015/145/ Open Access

url

Report an accessibility issueView

Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

16 File downloads

47 Record Views

Details

Title: Subtitle: Arithmetic circuit classes over Z m
Creators: Eric Allender (Author) - Rutgers University, Computer Science (SAS)
Asa Goodwillie (Author) - Amherst College
Date published: 09/05/2015
Publisher: Rutgers University
Number of pages: 16
Grants: CCF-1555409, National Science Foundation (United States, Arlington) - NSF
Academic Unit: Computer Science (SAS)
Language: English
Resource Type: Technical documentation
Identifiers: 991031602449704646