ITR: Scalable Algorithms Enabled by Problem Structure and Applications to Computer Hardware

这项研究涉及发现和发展可扩展的算法来解决工程中经常出现的困难计算问题。特别是，研究者观察到人造工件具有固有的结构，使这些工件易于设计、合成和验证，而不受其绝对尺寸的影响。Internet、集成电路芯片和大型分布式软件系统等人工制品的规模继续以惊人的速度增长。处理这些伪产物（例如，搜索互联网，合成集成电路，或验证软件系统的正确性）但忽略其固有结构和规则的算法无法处理其日益增加的复杂性。另一方面，可扩展算法识别并利用它们所操作对象的结构和规律性，以降低计算复杂度。因此，研究和开发可扩展算法对于在快速变化的技术世界中保持进步至关重要。尽管在设计、合成和验证人类工程对象时使用的许多计算任务都是最坏情况下的np困难，但此类对象的复杂性仍在不断增加，并且经常被制造和部署。众所周知的例子包括从飞机机组调度到微处理器验证和现场可编程门阵列的路由，但问题实例的绝对复杂性往往与现代解决方法相矛盾。知识产权的重用并不总是意味着将计算问题实例减少到更小的实例，即使应用了这种减少，它们也可能导致次最优性。解决大型难题的能力对于前沿计算机硬件的设计至关重要，并且随着硅光刻（EUV， x射线，电子束等），纳米制造（分子电子学）和集成复杂性（片上系统）的进步，实例大小将迅速增加。因此，解决主流np完全问题的经验改进对于信息技术复杂性的持续增长至关重要。本项目旨在通过对问题结构的智能利用，显著扩展实际算法的性能包络，以处理非常大的难题实例。研究人员正在通过通用和基本的结果来追求这一目标，这些结果的适用性超出了目前流行的最坏情况界限，这些界限与经验观察到的性能不同。

This research involves the discovery and development of scalable algorithms for solving hard computational problems that routinely arise in engineering. In particular, the investigators observe that man-made artifacts have innate structures that make those artifacts tractable for design, synthesis, and verification independent of their absolute size. Artifacts such as the Internet, integrated circuit chips, and large distributed software systems, continue to increase in size at a breath-taking pace. Algorithms that deal with such artifacts (e.g., searching the Internet, synthesizing integrated circuits, or verifying the correctness of software systems) but which are oblivious to their inherent structure and regularity are unable to cope with their ever-increasing complexity. Scalable algorithms, on the other hand, recognize, and take advantage of, the structure and regularity of the objects they manipulate in order to bring computational complexity down. The study and development of scalable algorithms, thus, is essential for maintaining progress in our fast-changing technological world.Despite the fact that many of the computational tasks employed in designing, synthesizing, and verifying human-engineered objects are worst-case NP-hard, such objects continue to increase in complexity and are routinely made and deployed. Well-known examples range from aircraft crew scheduling to microprocessor verification and the routing of field-programmable gate arrays, yet the sheer complexity of problem instances often defies modern solution methods. Reuse of intellectual property does not always imply reductions of computational problem instances to smaller ones, and even when such reductions are applied they may lead to sub-optimality's. The ability to solve large instances of hard problems is critical to the design of leading-edge computer hardware, and instance size will increase rapidly with advances in silicon lithography (EUV, X-ray, electron beam, etc.), nano-manufacturing (molecular electronics) and integration complexity (system-on-a-chip). Therefore, empirical improvements in solving mainstream NP-complete problems are critical to sustained increase in sophistication of Information Technologies. This project aims at significantly extending the performance envelope of practical algorithms in order to handle very large hard problem instances through intelligent utilization of problem structure. The investigators are pursuing this goal through generic and fundamental results with applicability beyond currently popular worst-case bounds that are at variance with empirically observed performance.