文章基本信息

标题：Symmetric Computation (Invited Talk)
本地全文：下载
作者：Anuj Dawar
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：152
页码：1-12
DOI：10.4230/LIPIcs.CSL.2020.2
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We discuss a recent convergence of notions of symmetric computation arising in the theory of linear programming, in logic and in circuit complexity. This leads us to a coherent and robust definition of problems that are efficiently and symmetrically solvable. This is at once a rich class of problems and one for which we have methods for proving lower bounds. In this paper, we take a tour through results which show applications of these methods in a number of areas.
关键词：Descriptive Complexity; Fixed-point Logic with Counting; Circuit Complexity; Linear Programming; Hardness of Approximation; Arithmetic Circuits