Parallelism, Communication and Randomness in Models of      Computation, and Efficient Computation in Permutation Groups
{'Code': '05010100', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'Dana S. Richards', 'PO_EMAI': None, 'PO_PHON': None}
Research is being conducted into the power of fundamental                       features of computation carried out according to various                        models.  The PIs and others have recently defined new                           classes in communication complexity theory and also in                          Turing Complexity.  Among such new classes are those defined                    by Arthur-Merlin protocols which are close relatives of                         interactive proof systems.  Both interaction and randomness                     play important roles in most of these new classes.                              Separation properties for these new classes are being                           studied.  Of particular interest are the separation problem                     of the polynomial time hierarchy in communication complexity                    theory and the relation of the class of languages determined                    by Arthur-Merlin protocols to the class of almost-NP                            languages.  The PIs are also continuing their investigation                     of reliability problems in asynchronous distributed networks.                                                                                                   The PIs have recently completed the proof that permutation                      group membership is in the class NC.  Their methods appear                      to have implications for the sequential case and they are                       exploring the possibility of obtaining a substantial speedup                    for the sequential situation.                                                                                                                                   The roles of interaction and randomness in computation are of                   crucial interest to the theory community at this time.  The                     PIs are leading figures in the development of the                               understanding of these roles.
[{'FirstName': 'Laszlo', 'LastName': 'Babai', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Laszlo Babai', 'EmailAddress': 'lbabai@gmail.com', 'NSF_ID': '000345452', 'StartDate': '07/15/1987', 'EndDate': None, 'RoleCode': 'Co-Principal Investigator'}, {'FirstName': 'Janos', 'LastName': 'Simon', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Janos Simon', 'EmailAddress': 'simon@cs.uchicago.edu', 'NSF_ID': '000172012', 'StartDate': '07/15/1987', 'EndDate': None, 'RoleCode': 'Principal Investigator'}]
{'Name': 'University of Chicago', 'CityName': 'CHICAGO', 'ZipCode': '606375418', 'PhoneNumber': '7737028669', 'StreetAddress': '5801 S ELLIS AVE', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'Illinois', 'StateCode': 'IL', 'CONGRESSDISTRICT': '01', 'CONGRESS_DISTRICT_ORG': 'IL01', 'ORG_UEI_NUM': 'ZUE9HKT2CLC9', 'ORG_LGL_BUS_NAME': 'UNIVERSITY OF CHICAGO', 'ORG_PRNT_UEI_NUM': 'ZUE9HKT2CLC9'}
{'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=1987&All=true', 'xml': '8710078.xml'}