The Library
Majority vs. approximate linear sum and average-case complexity below NC1
Tools
Chen, Lijie, Lu, Zhenjian, Lyu, Xin and Oliveira, Igor C. (2021) Majority vs. approximate linear sum and average-case complexity below NC1. In: International Colloquium on Automata, Languages and Programming (ICALP), Virtual conference, 12-16 Jul 2021. Published in: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 198 51:1-51:20. ISBN 9783959771955. doi:10.4230/LIPIcs.ICALP.2021.51 ISSN 1868-8969.
|
PDF
WRAP-Majority-vs-approximate-linear-sum-average-case-complexity-NC1-2021.pdf - Accepted Version - Requires a PDF viewer. Download (1461Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.51
Abstract
We develop a general framework that characterizes strong average-case lower bounds against circuit classes
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Data structures (Computer science), Computer Communication Networks, Computer science -- Statistical methods | ||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Journal or Publication Title: | 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) | ||||||
Publisher: | Leibniz International Proceedings in Informatics | ||||||
ISBN: | 9783959771955 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 1 July 2021 | ||||||
Dates: |
|
||||||
Volume: | 198 | ||||||
Page Range: | 51:1-51:20 | ||||||
DOI: | 10.4230/LIPIcs.ICALP.2021.51 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 18 May 2021 | ||||||
Date of first compliant Open Access: | 18 May 2021 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | International Colloquium on Automata, Languages and Programming (ICALP) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Virtual conference | ||||||
Date(s) of Event: | 12-16 Jul 2021 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year