摘要：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
