Research Initiation:  Applications of Kolmogorov Complexity:Pseudorandom Generators, Circuit Complexity, and One-Way    Functions
{'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}
This research centers on the development of generalized Kolmogorov              complexity theory as a tool to apply to problems in various areas of            complexity theory including circuit complexity, pseudorandom                    generators, and one-way functions.  Building on the principal                   investigator's work in circuit complexity, this work seeks to relate            the size of the circuit's description to the complexity of producing            the circuit.  One goal of this work would be to indicate that there is          a theoretical difference between efficient "general purpose" and                "special purpose" parallel computation.  Recent results have shown that         probabilisitic techniques are useful in analyzing the Kolmogorov                complexity of sets in certain well known classes.  This research seeks          to develop the link between probability theory and generalized                  Kolmogorov complexity.  Different hypotheses on the existence of one-           way functions have different necessary conditions in terms of                   generalized Kolmogorov complexity.  Sometimes, these conditions                 conflict.  This work investigates the nature of the conflict.
{'FirstName': 'Eric', 'LastName': 'Allender', 'PI_MID_INIT': 'W', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Eric W Allender', 'EmailAddress': 'Allender@cs.rutgers.edu', 'NSF_ID': '000391611', 'StartDate': '07/01/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Rutgers University New Brunswick', 'CityName': 'NEW BRUNSWICK', 'ZipCode': '089018559', 'PhoneNumber': '8489320150', 'StreetAddress': '3 RUTGERS PLZ', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'New Jersey', 'StateCode': 'NJ', 'CONGRESSDISTRICT': '12', 'CONGRESS_DISTRICT_ORG': 'NJ12', 'ORG_UEI_NUM': 'M1LVPE5GLSD9', 'ORG_LGL_BUS_NAME': 'RUTGERS, THE STATE 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': '8810467.xml'}