Number of Queries:  A Measure of Complexity
{'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}
Complexity theory deals with how hard problems are.  Dr. Beigel's               research addresses the following question: When is it significantly             harder to solve k+1 instances of a problem than to solve only k                 instances?  The answer to this question is not obvious because there            are hard problems for which solving n instances is not much harder than         solving 1 instance.  Recently, various researchers have looked at the           number of queries that must be made to an oracle in order to solve a            problem as a measure of that problem's difficulty.  Counting oracle             queries provides a way of formalizing the main question posed in this           research and leads naturally to the definition of cheatable sets, p-            terse sets, and p-superterse sets.  The study of these sets makes it            possible to prove that it is significantly harder to solve k+1                  instances of certain kinds of important problems than k instances.  Dr.         Beigel is also investigating how these notions are related to other             important concepts in complexity theory.
{'FirstName': 'Richard', 'LastName': 'Beigel', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Richard Beigel', 'EmailAddress': 'professorb@gmail.com', 'NSF_ID': '000111674', 'StartDate': '06/01/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Johns Hopkins University', 'CityName': 'BALTIMORE', 'ZipCode': '212182608', 'PhoneNumber': '4439971898', 'StreetAddress': '3400 N CHARLES ST', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'Maryland', 'StateCode': 'MD', 'CONGRESSDISTRICT': '07', 'CONGRESS_DISTRICT_ORG': 'MD07', 'ORG_UEI_NUM': 'FTMTDMBR29C7', 'ORG_LGL_BUS_NAME': 'THE JOHNS HOPKINS 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': '8808949.xml'}