ITR: Efficient Algorithms with Implicit Input Data

点击翻译按钮获取中文摘要

The main objective of this research is to establish methods fortheoretical study of algorithms for which the access to the input data isprovided in an implicit way. Such models of computations arise naturallyin the context of algorithms working with large data sets. The implicitinput may correspond either to a partial data in situations when theentire data cannot be directly accessed (for example, because it isprohibitively expensive), or it may correspond to compressed or codeddata. It happens when only such data is stored in the system and no directaccess to the real data is provided or is available.Traditionally, complexity theory deals with the classical definition ofthe explicitly given input data: the input is given explicitly and thegenerally accepted standard is to search for algorithms having thecomplexity linear, or at least polynomial in terms of the input size. Suchalgorithms are viewed usually as the most efficient. However, thissignificantly changes if we deal with massive data. It is sometimesnecessary to find good algorithms which deal with implicitly given dataand access only small part of the data (e.g., a random sample), or smallcompressed or encoded representation of the data. The information which wehave about the data is now of size which would be substantially muchsmaller than the size of the whole original input. In the extremesituations it can be even constant (small sample sufficiently wellapproximating, with high probability, the exact output).The main theme of this research is to understand the relation between thecomplexity of the problems in the classical model (where the access todata is given explicitly) and the problems in the model in which theaccess to the input is implicit. The main focus is on study algorithms forone- and two-dimensional compressed texts, algorithms for propertytesting, and sampling-based approximation algorithms. In case of texts theimplicit input is the compressed version of the input and in the case ofproperty testing the reduced input is usually a small sample of the input.In the latter case, the we also deal with the problems on preprocessedinput: an oracle provides fast answers to some basic structures underlyingthe input data, e.g., (in geometric setting) orthogonal range queries. Inthis case the implicit access to the input is constrained by range ofallowable queries and by the input data representation. The goals for thisresearch are to advance the state-of-the art in algorithms with restrictedaccess to the input data in general, in particular algorithms forcompressed texts and sampling-based property testing and approximationalgorithms.The intellectual merit of this proposal is wide and it involves advancesin computational complexity of new classes of problems: pattern-matchingin compressed or fully compressed one and two-dimensional texts, propertytesting with access only to a small portion of the input data and abstractcombinatorial algorithms dealing with implicit input data. It is a beliefof the investigators that new aspects of the algorithmic efficiencyexplored in this research may initiate an important and novel area ofcomputer science. This would be of great importance in time and spaceeffective processing of massive data, as well as of great importance inpure theory. The end-result of this research effort are an understandingof the effects of special access to the input data on the efficiency ofrelated algorithms.