This federal Project Grant award from the National Science Foundation's (NSF) Computer and Information Science and Engineering (CISE) program (CFDA 47.070) provides $460,755 to the University of Wyoming to develop new tools and theories for investigating the computational complexity of total function problems in theoretical computer science. The 3-year project aims to extend resource-bounded measure techniques, which have been effective for studying decision problems, to the more complex setting of function problems. This includes introducing new types of martingales that operate on function values. The research findings will be promoted through a Zoom seminar series and a culminating workshop at the University of Wyoming, engaging graduate students and leading complexity researchers. This work is expected to significantly impact our understanding of pseudorandomness, circuit-size complexity, fine-grained complexity, and the overall complexity landscape of total function complexity classes. No sub-awards are planned for this project.
Generated 4/1/25, 3:26 AM