AF: Medium: Collaborative Research: Circuit Lower Bounds via Projections

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

Computers play a central role in how we work, play, and communicate with each other in today's world. It is a truism that computers have grown steadily more powerful over the years, but equally important (if not more so) than the amount of sheer computing power available is how efficiently we are able to harness that power. Finding an efficient strategy to solve a given problem (in the language of computer science, an efficient algorithm) can often spell the difference between success and failure. (As an illustrative analogy, consider the task of assembling a large jigsaw puzzle. A poor choice of strategy such as a brute-force approach of trying each pair of pieces against each other may be infeasibly slow, while a cleverer approach such as grouping pieces by their color can be radically more efficient and lead to a feasible solution.) But in order to fully understand the abilities of efficient algorithms, it is crucial to also understand their limits: what is it that efficient algorithms *cannot* do? The field of "computational complexity", which is the subject of the PIs' project, seeks to mathematically prove that certain computational problems do not admit *any* efficient algorithm no matter how long and hard we try to develop one. Such results can have both practical value (by guiding algorithm development away from "dead ends") and deep theoretical significance, as they play a profound role in shaping our fundamental understanding of the phenomenon of computation.The 1980s witnessed exciting progress on a range of Boolean circuit models (a mathematical abstraction of the digital circuits that modern computers are built from) in computational complexity; researchers succeeded in proving many lower bounds establishing that various computational problems have no efficient algorithms in these models. However, further progress slowed significantly after the 1980s. Many of the landmark results obtained in this era were based on the "method of random restrictions", which roughly speaking uses probabilistic arguments to show that Boolean circuits can be dramatically simplified by making certain random substitutions of constant values for input variables. In this project the PIs will intensively investigate an extension of the method of random restrictions which they call the "method of random projections." Rather than simply substituting constant values for input variables, the random projection method additionally identifies groups of variables, "projecting" them all to the same new variable so that they must all take the same value. While the underlying idea is simple, it turns out that this identification of variables helps "maintain useful structure" which is extremely useful for proving lower bounds. In recent work the PIs have successfully used this new "method of random projections" to solve several decades-old problems in Boolean circuit lower bounds and related areas (which in some cases had notoriously resisted progress since the 1980s or 1990s). As the main intellectual goals of the project, the PIs will continue to develop and apply the method of random projections to attack important open problems in Boolean circuit complexity.In addition to the technical goals described above, other central goals of the project are to educate, communicate, and inspire. The PIs will train graduate students through research collaboration, disseminate research results through seminar talks, survey articles and other publications, and continue ongoing outreach activities aimed at increasing interest in and awareness of theoretical computer science topics in a broader population, including presentations at elementary schools.