New Horizons in Multivariate Preprocessing (MULTIPROCESS)

在各种真实的应用中，数据预处理或数据压缩是一种普遍存在的科普计算困难的策略。这里的目标是有效地计算原始数据的简洁表示，其中表示的信息的准确性只有很小的损失。这是通过各种步骤来实现的，例如简化输入的结构，减小大小或维度，去除冗余约束等。预处理算法在实践中的重要性得到了广泛的认可，开发数学框架，在其中可以进行严格的分析，提供性能保证，并比较针对特定计算问题提出的各种预处理算法的质量。在参数化复杂性（或多变量复杂性）领域，通过内核框架提供了对这一挑战的部分答案。这个框架已经导致了一个充满活力的新的算法子领域-核化。核化领域在过去的二十年中已经取得了巨大的成功，因为对NP难的“无损”预处理的分析和理解（预计不具有理论上有效性的计算问题，即，所谓的多项式时间算法）决策问题。然而，在实践中，预处理被大量用于具有理论上有效的（多项式时间）算法的问题的大数据集，以及希望在输入数据上优化某些目标函数的NP难题。在这些情况下，内核化的框架福尔斯非常短，并且不能与近似算法或算法学很好地结合联合收割机。该提案旨在通过提供有效预处理的新配方，克服困扰多项式时间预处理的经典理论的上述基本限制，在预处理的数学理论方面取得重大进展。该项目将导致新的预处理算法和基本计算问题的分析，并将严格的预处理分析的范围扩展到高影响力的大数据范例，如流算法。这将通过提供新的预处理设计技术以及新的数学机器来实现，该机器允许人们正式描述各种问题的预处理的局限性。该项目将通过为一种新的预处理理论奠定基础来实现范式转变，该理论将能够抽象和统一所有有效的预处理。这只是一个及时的旅程的开始，进入一个几乎未被探索的宇宙，充满了计算机科学不同子领域之间的可能性和未被发现的联系。

Data preprocessing or data compression is a ubiquitous strategy to cope with computational hardness in various real world applications. The goal here is to efficiently compute a succinct representation of the original data with only a small loss in the accuracy of the information represented within it. This is achieved through various steps such as simplifying the structure of the input, reducing the size or dimension, removing redundant constraints and so on.The widespread recognition of the importance of preprocessing algorithms in practice has motivated the challenging task of developing mathematical frameworks within which it is possible to conduct rigorous analysis, provide performance guarantees and compare the quality of various preprocessing algorithms proposed for specific computational problems. A partial answer to this challenge was provided in the area of parameterized complexity (or multivariate complexity) through the framework of kernels. This framework has lead to a vibrant new subfield of algorithmics -- Kernelization. The field of kernelization has turned out to be a resounding success over the last two decades as far as the analysis and understanding of 'lossless' preprocessing for NP-hard (computational problems that are not expected to have theoretically efficient, i.e., so called polynomial-time algorithms) decision problems is concerned. However, in practice, preprocessing is heavily used for large data sets of problems that have theoretically efficient (polynomial-time) algorithms as well as for NP-hard problems where one wants to optimize some objective function over the input data. In these situations, the framework of kernelization falls woefully short and does not combine well with approximation algorithms or heuristics. This proposal aims to make major advances in the mathematical theory of preprocessing by delivering new formulations of efficient preprocessing that overcome the aforementioned fundamental limitations that plague the classic theory of polynomial-time preprocessing. This project will lead to novel preprocessing heuristics and analyses for basic computational problems and extend the scope of rigorous preprocessing analysis to high-impact big data paradigms such as streaming algorithms. This will be achieved by delivering new preprocessing design techniques as well as new mathematical machinery that allows one to formally characterize the limitations of preprocessing for various problems. This project will bring about a paradigm shift by laying the foundations for a new theory of preprocessing that will be able to abstract and unify all efficient preprocessing. This is but the beginning of a timely journey into a mostly unexplored universe teeming with possibilities and undiscovered connections between diverse subfields of computer science.