Skip to content Skip to navigation

EAGER: New approaches to hardness for circuit minimization

Principal Investigator: 
Grant Agency: 
Grant Duration: 
09/01/2015 to 01/31/2017

NSF Link

The goal of this activity is to understand the structure of complexity classes.  Complexity classes provide the best tool currently available for understanding the computational complexity of real-world computational problems.  Some of these problems are notoriously difficult, but recent progress justifies some optimism that additional useful insight about these complexity classes can be obtained.

The Minimum Circuit Size Problem (MCSP) is a well-known example of an apparently-intractable problem in NP that is not widely believed to be NP-complete.  Until now, all of the evidence that has been gathered -- trying to indicate that MCSP is hard to compute -- has followed the same path, invoking the connections between derandomization techniques and cryptographically-secure one-way functions.  This proposal will focus on developing a direct approach to reduce seemingly-hard problems to MCSP, and thereby set the stage for a more thorough understanding of the complexity of MCSP. The research results will be broadly disseminated, both through journal publications as well as through survey articles in various venues. The long-term goals of research in computational complexity, if finally achieved, will have profound impact on society (for instance, by providing firm mathematical underpinnings to public-key cryptography, which currently rests upon many unproven conjectures).


Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval). 

Some links on this page may take you to non-federal websites. Their policies may differ from this site. 

Allender, Eric and Holden, Dhiraj and Kabanets, Valentine. "The Minimum Oracle Circuit Size Problem," computational complexity, 2016. doi:10.1007/s00037-016-0124-0  Citation details 




Please report errors in award information by writing to: