Symmetry in Computational Complexity (CoCoSym) Project funded by the European Research Council (ERC) as an ERC Consolidator Grant (ERC CoG), No. 771005
Principal investigator: Libor Barto
Host institution: Charles University, Prague, Czech Republic. Department: Department of Algebra, Faculty of Mathematics and Physics Dates: 1 Feb 2018 - 31 Jan 2023 Openings: I have a Phd and a postdoc position available - see ads below
Page under reconstruction!
Work in progress
Papers
Conferences
Visitors
Visits
Abstract The last 20 years of rapid development in the computational-theoretic aspects of the fixed-language Constraint Satisfaction Problems (CSPs) has been fueled by a connection between the complexity and a certain concept capturing symmetry of computational problems in this class. My vision is that this connection will eventually evolve into the organizing principle of computational complexity and will lead to solutions of fundamental problems such as the Unique Games Conjecture or even the P-versus-NP problem. In order to break through the current limits of this algebraic approach, I will concentrate on specific goals designed to
The approach is based on joining the forces of the universal algebraic methods in finite domains, model-theoretical and topological methods in the ∞CSP, and analytical and probabilistic methods in the vCSP. The starting point is to generalize and improve the Absorption Theory from finite domains. Call for applications: PhD students We are looking for highly motivated and creative PhD students to work on the ERC funded project Symmetry in Computational Complexity (CoCoSym) under the supervision of Libor Barto at the Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague. The project concerns the complexity and approximability of constraint satisfaction problems and is at the intersection of several areas of mathematics and theoretical computer science (general algebra, logic, computational complexity, combinatorics, analysis). The starting date of the PhD study is October 2019. The applicant is expected to have the master degree completed by this date. The duration is four years. The position is fully funded from the ERC grant, funding for conference travel is also available. Applicants should send a CV, a statement of research experience and interests, and an (unofficial) academic transcript in a single PDF file to Libor Barto (libor.barto@mff.cuni.cz) by April 14, 2019. Applicants should also arrange for at least two recommendation letters to be sent directly to the same email address by the same date. Informal inquiries are welcome. Call for applications: postdocs We are looking for a highly motivated and creative post-doctoral researcher to work on the ERC funded project Symmetry in Computational Complexity (CoCoSym) under the supervision of Libor Barto at the Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague. The project concerns the complexity and approximability of fixed-template constraint satisfaction problems over finite domains and their generalization to infinite domains and weighted relations. The duration of the position will be between one and three years. The starting day is flexible, applications will be considered until the position is filled. The position carries no teaching load. The position is fully funded from the ERC grant, funding for conference travel is also available. Applicants should send a CV, a statement of research experience and interests, and a list of publications (that may include a short annotation of at most three of their best papers) in a single PDF file to Libor Barto (libor.barto@mff.cuni.cz). Applicants should also arrange for at least two recommendation letters to be sent directly to the same email address. Informal inquiries are welcome. |