Topics in Computational Complexity
{'Code': '05010100', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Krishna M. Kavi', 'PO_EMAI': None, 'PO_PHON': None}
The inherent complexity of various computational problems will be               investigated, in the hope that a deeper understanding may be gained as          to why certain problems seem to require a nontrivial amount of                  computing resources for their solution.  Complementary to this effort,          the expected performance of a number of existing algorithms will also           be studied.  The principal mathematical tools needed for this research          are likely to be combinatorial and probabilistic techniques.  To                delineate the scope of this investigation, representative problems are          given from Boolean circuits, decision trees, data structures, geometric         computations, and the mathematical analysis of algorithms.
{'FirstName': 'Andrew', 'LastName': 'Yao', 'PI_MID_INIT': 'C', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Andrew C Yao', 'EmailAddress': 'yao@cs.princeton.edu', 'NSF_ID': '000173766', 'StartDate': '07/15/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Princeton University', 'CityName': 'PRINCETON', 'ZipCode': '085442001', 'PhoneNumber': '6092583090', 'StreetAddress': '1 NASSAU HALL', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'New Jersey', 'StateCode': 'NJ', 'CONGRESSDISTRICT': '12', 'CONGRESS_DISTRICT_ORG': 'NJ12', 'ORG_UEI_NUM': 'NJ1YPQXQG7U5', 'ORG_LGL_BUS_NAME': 'THE TRUSTEES OF PRINCETON UNIVERSITY', 'ORG_PRNT_UEI_NUM': None}
{'Name': None, 'CityName': None, 'StateCode': None, 'ZipCode': None, 'StreetAddress': None, 'CountryCode': None, 'CountryName': None, 'StateName': None, 'CountryFlag': None, 'CONGRESSDISTRICT': None, 'CONGRESS_DISTRICT_PERF': '""'}
{'Code': '2860', 'Text': 'THEORY OF COMPUTING'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8813283.xml'}