The query complexity of certification

DOI10.1145/3519935.3519993arXiv2201.07736OpenAlexW4226180252MaRDI QIDQ6083517

Caleb M. Koch, Guy Blanc, Li-Yang Tan, Jane Lange

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://arxiv.org/abs/2201.07736

zbMATH Keywords

monotone functionsquery algorithmscertificate complexityBoolean function complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)