Mathematical Sciences: Probability and Statistics Applied tothe Theory of Algorithms
{'Code': '03040107', 'Directorate': {'Abbreviation': 'MPS', 'LongName': 'Direct For Mathematical & Physical Scien'}, 'Division': {'Abbreviation': 'DMS', 'LongName': 'Division Of Mathematical Sciences'}}
{'SignBlockName': 'Peter Arzberger', 'PO_EMAI': None, 'PO_PHON': None}
The project will explore seven explicit conjectures in three               broad areas of probabilistic analysis of algorithms, empirical                  processes and random graphs.  Several connections between these                 apparently different areas will be clarified and used in the                    solutions of the conjectures.  Karp's probabilistic polynomial                  time algorithm for the traveling salesman problem, leads to                     considerations of random graphs with special properties.  Thus                  the central limit theorem and the large deviation theory of the                 traveling salesman problem have connections with quantities of                  interest in the random graph theory such as minimal spanning                    trees, and minimal matchings.  Some of the new techniques used                  include the theory of Sobolov inequalities and the Efron-Stein                  inequality.  Theory of random trees is developed by putting                     specific probability distributions on the trees with n vertices.                It will be shown that the use of Harper's method leads to a                     richer theory of random trees.  Harper's method in turn leads to                connections with the empirical process of lines.  The novelty of                the research is its problem-driven approach and the elucidation                 and exploitation of the interconnections of seemingly divergent                 fields.
{'FirstName': 'J. Michael', 'LastName': 'Steele', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'J. Michael Steele', 'EmailAddress': 'Steele@Wharton.upenn.edu', 'NSF_ID': '000377025', 'StartDate': '07/01/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': '1263', 'Text': 'PROBABILITY'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8812868.xml'}