Bounded Queries in Complexity Theory
{'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}
Complexity theory deals with how hard problems are.  Recently various           researchers have looked at the number of queries which must be made to          an oracle in order to solve a problem as a measure of that problem's            difficulty. A set is cheatable if membership of 2k strings can be               determined by querying only k strings.  We investigate structure,               closure properties, complexity, and naturalness of both cheatable and           terse sets.  We also compare these notions to other concepts such as            polynomial size circuits, near-testability, and-selectivity.
[{'FirstName': 'Amihood', 'LastName': 'Amir', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Amihood Amir', 'EmailAddress': 'amir@cc.gatech.edu', 'NSF_ID': '000107184', 'StartDate': '09/01/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}, {'FirstName': 'William', 'LastName': 'Gasarch', 'PI_MID_INIT': None, 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'William Gasarch', 'EmailAddress': 'gasarch@umd.edu', 'NSF_ID': '000147394', 'StartDate': '09/01/1988', 'EndDate': None, 'RoleCode': 'Co-Principal Investigator'}]
{'Name': 'University of Maryland, College Park', 'CityName': 'COLLEGE PARK', 'ZipCode': '207425100', 'PhoneNumber': '3014056269', 'StreetAddress': '3112 LEE BUILDING', 'StreetAddress2': None, 'CountryName': 'United States', 'StateName': 'Maryland', 'StateCode': 'MD', 'CONGRESSDISTRICT': '04', 'CONGRESS_DISTRICT_ORG': 'MD04', 'ORG_UEI_NUM': 'NPU8ULVAAS23', 'ORG_LGL_BUS_NAME': 'UNIVERSITY OF MARYLAND, COLLEGE PARK', 'ORG_PRNT_UEI_NUM': 'NPU8ULVAAS23'}
{'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'}, {'Code': '9120', 'Text': 'CROSS-DIRECTORATE PROGRAMS'}]
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8803641.xml'}