The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity

DOI10.1145/3519935.3520010OpenAlexW4281753531MaRDI QIDQ6083551

Unnamed Author, Tianqi Yang, Unnamed Author

Publication date: 8 December 2023

Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3519935.3520010

zbMATH Keywords

pseudorandom functionscircuit complexityrandom restrictionsBoolean circuitsthreshold circuitsnatural proofs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Oblivious transfer with constant computational overhead

This page was built for publication: The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity