Complexity of Problems with Hidden Nonlinearities

Fordham University, Bronx NY

Investigators

Abstract

Information-based complexity (IBC) studies the complexity of solving problems for which only partial information is available. Many problems that IBC has successfully handled have been linear, i.e., the solution depends linearly on the input. However, many seemingly-linear problems have hidden nonlinearities. The Investigator proposes to study two such problems. The first is integration, which has several important nonlinear variants (such as Stieltjes and surface integrals); moreover, the integral depends nonlinearly on the domain of integration. The second is linear elliptic partial differential equations, for which there is a nonlinear dependence on the domain of definition and on the coefficients of the linear partial differential operator. Our goals include: determining the problem complexity, finding (nearly-) optimal algorithms), and determining whether adaptive information is better than nonadaptive information.