Research Initiation:  Measure and Category in Complexity    Classes
{'Code': '05010100', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Bruce H. Barnes', 'PO_EMAI': None, 'PO_PHON': None}
A number of problems in computational complexity and pseudorandomness           are being investigated, using new extensions of Lebesgue measure theory         and the Baire category method as tools.  These techniques, recently             developed by the principal investigator, assign probabilistic and               topological "sizes" to subsets of complexity classes.  This approach,           which has already revealed new, quantitative information about the              structure of these classes, is being used to investigate: (1)                   relationships between uniform and nonuniform complexity, with                   particular emphasis on circuit-size and program-size complexities; (2)          quantitative relationships between the "span" of (i.e., the set of              problems efficiently reducible to) a problem and its complexity                 properties, including approximation, complexity cores, and hard                 instances; (3) theoretical aspects of pseudorandomness; and (4) the             adequacy of pseudorandom sources for efficient randomized algorithms.           The complexity-theoretic measure and category methods themselves are            being refined, strengthened, and extended to a wider variety of                 classes.
{'FirstName': 'Jack', 'LastName': 'Lutz', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Jack Lutz', 'EmailAddress': 'lutz@cs.iastate.edu', 'NSF_ID': '000408517', 'StartDate': '09/01/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Iowa State University', 'CityName': 'AMES', 'ZipCode': '500112103', 'PhoneNumber': '5152945225', 'StreetAddress': '1350 BEARDSHEAR HALL', 'StreetAddress2': '515 MORRILL ROAD', 'CountryName': 'United States', 'StateName': 'Iowa', 'StateCode': 'IA', 'CONGRESSDISTRICT': '04', 'CONGRESS_DISTRICT_ORG': 'IA04', 'ORG_UEI_NUM': 'DQDBM7FGJPC5', 'ORG_LGL_BUS_NAME': 'IOWA STATE UNIVERSITY OF SCIENCE AND TECHNOLOGY', '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': '8809238.xml'}