Fast and Robust Algorithms with Partial Data Access

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

The demand for fast data handling is prevalent in the use of most new technologies and scientific endeavo­­rs, especially in autonomous systems, communication networks, healthcare, data storage systems, and economic and financial markets. Some of the challenges encountered often stem from the need to quickly recover data, or to quickly make irrevocable decisions, based only on partial information about the input. In addition, information symbols may be misaligned or may contain significant amounts of noise, because of either random physical processes, adversarial behavior, or human or machine errors. Thus, unrestricted access to clean data is often an unrealistic expectation, which leads to a pressing need for creative methods to fight these challenges. The project will address such challenges by developing novel techniques inspired from coding theory, learning theory and machine learning, as well as graph theory and optimization, to build and analyze desirable algorithmic solutions. The outcomes of the project have the potential to be deployed in DNA data storage technologies, communication systems, network systems, and settings in which machine learning may enhance algorithmic guarantees. The project will broaden participation in computing by actively involving in research both undergraduate students and underrepresented minorities. The research will be broadly disseminated through presentations in workshops, seminars, and conferences, and it will be integrated in undergraduate and graduate courses. The project will advance knowledge by developing efficient, robust, and reliable algorithms that can deal with misaligned or badly damaged data and algorithms that only have partial or restricted access to the data. The research will address three specific areas. First, it will focus on error-correcting codes that can withstand adversarial or random insertion and deletion errors, when the algorithm is given only a partial view of the data, namely in the setting of local decoding. Secondly, it will study data recovery in a particular learning model, namely when the noise damages the attributes of the data. Thirdly, it will focus on algorithms that can only access the data in an online fashion and must make irreversible decisions, both in classical settings as well as in settings where the algorithms may be enhanced with machine learning advice. The project aims to develop state-of-the-art tools and techniques to analyze limitations of current algorithmic techniques in the above models, and to propose adequate models that bypass such limitations.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.