The Library
LEARN-uniform circuit lower bounds and provability in bounded arithmetic
Tools
Tools
Tools
Carmosino, Marco, Kabanets, Valentine, Kolokolova, Antonina and Carboni Oliveira, Igor (2022) LEARN-uniform circuit lower bounds and provability in bounded arithmetic. In: Symposium on Foundations of Computer Science (FOCS), Denver, Colorado, 7-10 Feb 2022. Published in: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) ISSN 2575-8454. doi:10.1109/FOCS52979.2021.00080
|
PDF
WRAP-LEARN-uniform-circuit-lower-bounds-provability-bounded-arithmetic-Carboni-Oliveira-2021.pdf - Accepted Version - Requires a PDF viewer. Download (2493Kb) | Preview |
Official URL: https://doi.org/10.1109/FOCS52979.2021.00080
Abstract
We investigate randomized LEARN-uniformity, which captures the power of randomness and equivalence queries (EQ) in the construction of Boolean circuits for an explicit problem. This is an intermediate notion between P-uniformity and non-uniformity motivated by connections to learning, complexity, and logic. Building on a number of techniques, we establish the first unconditional lower bounds against LEARN-uniform circuits
| 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, Computer algorithms , Computer science -- Mathematics | ||||||||
| Journal or Publication Title: | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) | ||||||||
| Publisher: | IEEE | ||||||||
| ISSN: | 2575-8454 | ||||||||
| Official Date: | 4 March 2022 | ||||||||
| Dates: |
|
||||||||
| Article Number: | 95 | ||||||||
| DOI: | 10.1109/FOCS52979.2021.00080 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Reuse Statement (publisher, data, author rights): | © 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| RIOXX Funder/Project Grant: |
|
||||||||
| Conference Paper Type: | Paper | ||||||||
| Title of Event: | Symposium on Foundations of Computer Science (FOCS) | ||||||||
| Type of Event: | Conference | ||||||||
| Location of Event: | Denver, Colorado | ||||||||
| Date(s) of Event: | 7-10 Feb 2022 | ||||||||
| 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
