Presidential Young Investigator Award: Randomness and       Parallelism in the Solution of Computational Problems
{'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}
The number of solutions of a computational problem and their                    distribution                                                                    have fundamental implications upon its computational efficiency.  When          the                                                                             solutions are symmetrically located an algorithm that cannot                    distinguish                                                                     between two solutions cannot (by symmetry) converge to either answer.           Randomization is often effective precisely because it can break such            symmetries.  In joint work, the PI has shown that an adversary source           of randomness is sufficient to break symmetries (thus showing RP =              SRP).                                                                           What is novel about this approach is that identifying symmetry breaking         as the essential task of randomization allows one to ask more precisely         how much randomness is really needed for efficient computation.  Two            related questions now being addressed are:  What are necessary and              sufficient conditions for a source of randomness to be a universal              symmetry breaker?  How many random bits are necessary?  A pseudo-random         number generator is quasi-perfect if its output satisfies universal             symmetry breaking properties.  The PI has recently proposed a simple            and efficient pseudo-random number generator.  An attempt is now being          made to settle the associated conjecture that this generator is                 quasi-perfect.                                                                                                                                                  Massively parallel computation provides another context where the               difficulty can lie in the task of selecting one solution among many.            In joint work the PI has given a general scheme for isolating one               solution in parallel (obtaining a parallel algorithm for the maximum            matching problem).  Further applications of this isolating scheme               are now being explored.                                                                                                                                         The PI has been judged to be an outstanding computer scientist by               the Presidential Young Investigators panel.
{'FirstName': 'Umesh', 'LastName': 'Vazirani', 'PI_MID_INIT': 'V', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Umesh V Vazirani', 'EmailAddress': 'vazirani@cs.berkeley.edu', 'NSF_ID': '000453519', 'StartDate': '08/01/1987', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Harvard University', 'CityName': 'CAMBRIDGE', 'ZipCode': '021385366', 'PhoneNumber': '6174955501', 'StreetAddress': '1033 MASSACHUSETTS AVE STE 3', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'Massachusetts', 'StateCode': 'MA', 'CONGRESSDISTRICT': '05', 'CONGRESS_DISTRICT_ORG': 'MA05', 'ORG_UEI_NUM': 'LN53LCFJFL45', 'ORG_LGL_BUS_NAME': 'PRESIDENT AND FELLOWS OF HARVARD COLLEGE', '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': '286000', 'Text': 'THEORY OF COMPUTING'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1986&All=true', 'xml': '8658143.xml'}