On the power of symmetric linear programs
| Autor: | Anuj Dawar, Joanna Ochremiak, Albert Atserias |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorísmia, Bioinformàtica, Complexitat i Mètodes Formals, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals, Universitat Politècnica de Catalunya [Barcelona] (UPC), Computer Laboratory [Cambridge], University of Cambridge [UK] (CAM), Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Dawar, Anuj [0000-0003-4014-8248], Apollo - University of Cambridge Repository |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science Linear programming Computer science Boolean circuit Polytope 02 engineering and technology Computational Complexity (cs.CC) Upper and lower bounds Vocabulary 01 natural sciences cs.LO Extended formulations Lift (mathematics) Symmetric group ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION 0202 electrical engineering electronic engineering information engineering Mathematics - Optimization and Control Complexitat computacional ComputingMilieux_MISCELLANEOUS Mathematics cs.CC Complexity theory [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Sense (electronics) Programació lineal Graph Exponential function Power (physics) Computational complexity Informàtica::Informàtica teòrica [Àrees temàtiques de la UPC] Planted clique 010201 computation theory & mathematics Hardware and Architecture Logic gate 020201 artificial intelligence & image processing Information Systems [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] Optimization Property (philosophy) 0102 computer and information sciences Combinatorics Artificial Intelligence FOS: Mathematics Perfect matching 0101 mathematics Hamiltonian graphs Q measurement Discrete mathematics math.OC Grafs Teoria de 010102 general mathematics Logic gates Logic in Computer Science (cs.LO) Graph theory Computer Science - Computational Complexity Optimization and Control (math.OC) Integrated circuit modeling Control and Systems Engineering Software MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Recercat. Dipósit de la Recerca de Catalunya instname 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jun 2019, Vancouver, Canada. pp.1-13, ⟨10.1109/LICS.2019.8785792⟩ LICS UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| DOI: | 10.1109/LICS.2019.8785792⟩ |
| Popis: | We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem. First author partially funded by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR) and MICCIN grant TIN2016-76573-C2-1P (TASSAT3). The second author was partially supported by a Fellowship of the Alan Turing Institute under the EPSRC grant EP/N510129/1. The third author funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 795936. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|