Complexity Bounds in Parallel Computation
{'Code': '05010100', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'name not available', 'PO_EMAI': None, 'PO_PHON': None}
A new algebraic approach to parallel complexity has recently been               emerging through the work of such investigators as Barrington,                  Razborov, and Smolensky.  In such work use is made of finite                    permutation groups and also of rings of polynomials over fields of              prime order for which the indeterminants are                                    assumed to be idempotent.  The PIs are investigating the complexity of          parallel computation through the analysis of such associated algebraic          structures.  They have also developed a new model of computation that           they                                                                            call the "safe storage machine" which periodically loses all but a              constant amount of its memory.  In progress are characterizations of            classes of languages and predicates definable by means of variations of         this new model.                                                                                                                                                 There is much interest in the theoretical computer science community in         the exploration of the newly developed algebraic view of questions in           parallel computation.  The PIs bring a broad strong collective                  background to this study.
[{'FirstName': 'Michael', 'LastName': 'Fischer', 'PI_MID_INIT': 'J', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Michael J Fischer', 'EmailAddress': 'fischer-michael@cs.yale.edu', 'NSF_ID': '000331611', 'StartDate': '08/01/1987', 'EndDate': None, 'RoleCode': 'Principal Investigator'}, {'FirstName': 'Merrick', 'LastName': 'Furst', 'PI_MID_INIT': 'L', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Merrick L Furst', 'EmailAddress': None, 'NSF_ID': '000221412', 'StartDate': '08/01/1987', 'EndDate': None, 'RoleCode': 'Co-Principal Investigator'}, {'FirstName': 'Jin-Yi', 'LastName': 'Cai', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Jin-Yi Cai', 'EmailAddress': 'jyc@cs.wisc.edu', 'NSF_ID': '000209365', 'StartDate': '08/01/1987', 'EndDate': None, 'RoleCode': 'Co-Principal Investigator'}]
{'Name': 'Yale University', 'CityName': 'NEW HAVEN', 'ZipCode': '065113572', 'PhoneNumber': '2037854689', 'StreetAddress': '150 MUNSON ST', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'Connecticut', 'StateCode': 'CT', 'CONGRESSDISTRICT': '03', 'CONGRESS_DISTRICT_ORG': 'CT03', 'ORG_UEI_NUM': 'FL6GV84CKN57', 'ORG_LGL_BUS_NAME': 'YALE UNIV', 'ORG_PRNT_UEI_NUM': 'FL6GV84CKN57'}
{'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': '8709818.xml'}