The new complexity landscape around circuit minimization

Accepted manuscript

Open access

Proc. 14th International Conference on Language and Automata Theory and Applications (LATA 2020)

Conference on Language and Automata Theory and Applications (LATA 2020) (Milan)

2020

DOI:

https://doi.org/10.7282/t3-8wab-ry80

Abstract

Complexity theory

Kolmogorov complexity

Minimum circuit size problem

We survey recent developments related to the Minimum Circuit Size Problem.

pdf

lata333.43 kBDownload View

Accepted Manuscript (AM) Open Access

url

https://doi.org/10.1007/978-3-030-40608-0_1View

Version of Record (VoR) Proc. 14th International Conference on Language and Automata Theory and Applications (LATA 2020)

url

Report an accessibility issueView

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

8 File downloads

118 Record Views

Title: Subtitle: The new complexity landscape around circuit minimization
Creators: Eric Allender (Author) - Computer Science (New Brunswick), Rutgers University
Publication Details: Proc. 14th International Conference on Language and Automata Theory and Applications (LATA 2020)
Conference: Conference on Language and Automata Theory and Applications (LATA 2020) (Milan)
Date published: 2020
Publisher: Springer-Verlag";"Springer-Verlag
Number of pages: 1 online resource (14 pages)
Grant note: National Science Foundation - CCF-1909216
Academic Unit: School of Arts and Sciences; Computer Science (SAS)
Language: English
Resource Type: Accepted manuscript
Identifiers: 991031549883904646