RIA:Complexity Analysis and Optimal Algorithms for NonlinearProblems
{'Code': '05010200', 'Directorate': {'Abbreviation': 'CSE', 'LongName': 'Direct For Computer & Info Scie & Enginr'}, 'Division': {'Abbreviation': 'CCF', 'LongName': 'Division of Computing and Communication Foundations'}}
{'SignBlockName': 'S. Kamal Abdali', 'PO_EMAI': None, 'PO_PHON': None}
This proposal involves complexity analysis and the development of               optimal algorithms for the solution of nonlinear problems.  Unlike most         current research in complexity which is discrete in nature, the                 problems considered in this proposal are (piecewise) continuous                 functions of one or more real variables.  The tools for complexity              analysis of these problems thus differ from traditional complexity              analysis and are based on the ideas of information-based complexity.                                                                                            The development of an upper bound on problem complexity is similar to           classical numerical analysis (and may in fact borrow from previous work         therein).  The derivation of lower bounds on a problem's complexity is          one of the novel aspects of this research, and can be roughly described         as follows:  Using mathematical techniques, one develops a set of               functions with different solutions to the problem but which are                 indistinguishable using a given amount of information.  Unless this set         of functions is a singleton no algorithm can solve the problem.  This           provides lower bounds on the amount of information required to solve            the problems, which in turn bounds the problem complexity from below.           While the concepts are simple, the derivation of a particular bound is          generally quite difficult, and often provides insight useful for                achieving better upper bounds.                                                                                                                                  The nonlinear problems addressed in this research will include both             worst-case and "average"-case analysis of the computation of                    topological degree in one or more dimensions, root-finding for                  Lipschitz function in one two and three dimensions, and                         segmentation/reconstruction of overlapping functions from function              values (with restrictions from computer vision).  These problems have           both theoretical and practical importance, and the techniques developed         for their analysis should be useful elsewhere.
{'FirstName': 'Terrance', 'LastName': 'Boult', 'PI_MID_INIT': 'E', 'PI_SUFX_NAME': None, 'PI_FULL_NAME': 'Terrance E Boult', 'EmailAddress': 'tboult@vast.uccs.edu', 'NSF_ID': '000212325', 'StartDate': '06/01/1988', 'EndDate': None, 'RoleCode': 'Principal Investigator'}
{'Name': 'Columbia University', 'CityName': 'NEW YORK', 'ZipCode': '100277922', 'PhoneNumber': '2128546851', 'StreetAddress': '615 W 131ST ST', 'StreetAddress2': 'MC 8741', 'CountryName': 'United States', 'StateName': 'New York', 'StateCode': 'NY', 'CONGRESSDISTRICT': '13', 'CONGRESS_DISTRICT_ORG': 'NY13', 'ORG_UEI_NUM': 'F4N1QNPB95M4', 'ORG_LGL_BUS_NAME': 'THE TRUSTEES OF COLUMBIA UNIVERSITY IN THE CITY OF NEW YORK', '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': '2865', 'Text': 'NUMERIC, SYMBOLIC & GEO COMPUT'}
{'url': 'https://www.nsf.gov/awardsearch/download?DownloadFileName=1988&All=true', 'xml': '8809022.xml'}