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

INT 9600919总线 这个美国-捷克的研究工作由塞缪尔R。加州大学圣地亚哥分校的Buss和捷克科学院数学研究所的Pavel Pudlak将研究数学逻辑和计算复杂性理论的几个密切相关的领域。 这些领域包括：有界算术;命题证明系统的复杂性;电路复杂性和通信复杂性;以及密码学。 美国团队由Buss，加州大学圣地亚哥分校的Russell Impagliazzo，匹兹堡大学的Toniann Titassi和卡内基梅隆大学的Steven Rudich组成，将与数学研究所的三位捷克合作伙伴共同研究深度连接的基本开放数学问题。 捷克队由普德拉克、斯加尔和克拉伊切克组成。 这个国际团队将研究三个具体问题：1）有界算术的有限公理化，2）Frege和扩展Frege证明长度的界限，以及3）布尔电路深度和大小的下界。 预计结果将产生基础研究，将作为设计实际协议的基础，在未来，与潜在的应用密码学。 这个数学基础项目实现了促进科学知识的计划目标，使美国和东欧的领先专家能够在共同感兴趣和能力的领域联合收割机互补人才和研究资源。 ??

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. ??