Name
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 again... |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1109/FOCS52979.2021.00080 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Computer science,Upper bound,Computational modeling,Buildings,Complexity theory,Data mining,Integrated circuit modeling | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marco Carmosino | 1 | 0 | 0.34 |
| Valentine Kabanets | 2 | 0 | 0.34 |
| Antonina Kolokolova | 3 | 50 | 10.09 |
| Igor C. Oliveira | 4 | 0 | 0.34 |