Meta-Algorithms versus Circuit Lower Bounds

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

Computers have dramatically changed our lives. We can now efficiently solve many computational problems that would be impossible to solve without computers. Yet, many important problems still seem beyond the reach of even our most powerful super-computers. Is the apparent difficulty of these problems real (intrinsic to the problem), or these problems do have efficient algorithmic solutions that we haven't been able to discover yet? The field of computational complexity studies precisely this question: what problems require excessive computational resources (computation time, memory, etc.)? In addition to clarifying the boundary of what can be solved efficiently, identifying computationally hard problems also has important practical consequences. For instance, the security of virtually all cryptographic systems in use today (including electronic banking) relies on the unproven assumptions that certain computational problems are very hard to solve. Thus, proving that such problems are actually hard would prove that these cryptographic protocols are truly secure. One of important discoveries of modern complexity theory is the deep connection between proving the hardness of computational problems and designing efficient algorithms for related computational problems. The two tasks are like Ying and Yang of Computer Science: progress in one is impossible without progress in the other. The main goal of the proposed research is to gain better insight into this connection, and exploit it to make further progress in both computational hardness and efficient algorithm design.