CAREER: Information, Optimization and Approximation

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

As the capability of data acquisition has increased over the last few years, the challenges of computing with these large datasets has increased as well. In many scenarios investigating the entire data repeatedly to answer questions is becoming an infeasible strategy. The emerging trend in these contexts is to summarize the information content, perhaps with some loss, such that reasonably accurate answers can still be provided but the algorithm will only inspect the summarized representation. This approach has already gained currency in database query optimizers, network monitoring, and sensor networks. For the above two phase strategy to work the summarization should be geared towards the end use of the information. However, in many scenarios the two phases are being investigated separately and their development is not being guided by end use but by mathematical and algorithmic tractability. As a consequence the solutions obtained are far from optimal. The goal of this project is to investigate the finer mathematical structure of several of these problems and provide provably near optimal solutions. Intellectually this project seeks to develop algorithmic understanding of several representation problems that arise from the interaction of approximation theory and information theory. The existing analytical treatment of these problems, typically, does not consider computational efficiency which is necessary to cope with the ever increasing problem sizes. The focus this research is to use techniques from combinatorial optimization as well as recent developments in sampling, embeddings, and approximate data structures to develop efficient approximation algorithms for these problems. These representation problems are ubiquitous in a broad range of areas such as signal processing, networks, databases. Efficient solutions to these problems will play a significant role in monitoring, reconnaissance and network forensics and is likely to impact practice.