Abstract | ||
---|---|---|
A PAC learning model involves two worst-case requirements: a learner must learn all functions in a class on all example distributions. However, basing the hardness of learning on NP-hardness has remained a key challenge for decades. In fact, recent progress in computational complexity suggests the possibility that a weaker assumption might be sufficient for worst-case learning than the feasibility... |
Year | DOI | Venue |
---|---|---|
2021 | 10.1109/FOCS52979.2021.00078 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Computer science,Heuristic algorithms,Computational modeling,Switches,Picture archiving and communication systems,Time complexity | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shuichi Hirahara | 1 | 3 | 7.48 |
Mikito Nanashima | 2 | 0 | 0.34 |