U.S.-Czech Research on Mathematical Logic, Complexity Theory, and Connections

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

INT 9600919 Buss This U.S.-Czech research effort headed by Samuel R. Buss of the University of California-San Diego, and Pavel Pudlak at the Mathematics Institute of the Czech Academy of Sciences, will examine several closely related areas of mathematical logic and computational complexity theory. These areas include: bounded arithmetic; complexity of propositional proof systems; circuit complexity and communication complexity; and cryptography. The U.S. team, consisting of Buss, Russell Impagliazzo of the University of California-San Diego, Toniann Titassi of the University of Pittsburgh, and Steven Rudich of Carnegie Mellon University, will work together with three Czech partners at the Mathematics Institute on deeply connected, fundamental open mathematical problems. The Czech team consists of Pudlak, Jiri Sgall and Jan Krajicek. There are three specific problems this international team will investigate: 1) finite axiomatizability of bounded arithmetic, 2) bounds on the length of Frege and extended Frege proofs, and 3) lower bounds for the depth and the size of Boolean circuits. Results are expected to yield foundational research that will serve as the basis for devising practical protocols in the future, with potential application to cryptography. This project in mathematical foundations fulfills the program objective of advancing scientific knowledge by enabling leading experts in the United States and Eastern Europe to combine complementary talents and pool research resources in areas of mutual interest and competence. ??