Abstract
Choiceless Polynomial Time (CPT) is one of the few remaining candidate logics for capturing Ptime. In this paper, we make progress towards separating CPT from polynomial time by firstly establishing a connection between the expressive power of CPT and the existence of certain symmetric circuit families, and secondly, proving lower bounds against these circuits. We focus on the isomorphism problem of unordered CaiFürerImmermangraphs (the CFIquery) as a potential candidate for separating CPT from Ptime. Results by Dawar, Richerby and Rossman, and subsequently by Pakusa, Schalthöfer and Selman show that the CFIquery is CPTdefinable on linearly ordered and preordered base graphs with small colour classes. We define a class of CPTalgorithms, that we call "CFIsymmetric algorithms", which generalises all the known ones, and show that such algorithms can only define the CFIquery on a given class of base graphs if there exists a family of symmetric XORcircuits with certain properties. These properties include that the circuits have the same symmetries as the base graphs, are of polynomial size, and satisfy certain fanin restrictions. Then we prove that such circuits with slightly strengthened requirements (i.e. stronger symmetry and fanin and fanout restrictions) do not exist for the ndimensional hypercubes as base graphs. This almost separates the CFIsymmetric algorithms from Ptime  up to the gap that remains between the circuits whose existence we can currently disprove and the circuits whose existence is necessary for the definability of the CFIquery by a CFIsymmetric algorithm.
BibTeX  Entry
@InProceedings{pago:LIPIcs.MFCS.2023.73,
author = {Pago, Benedikt},
title = {{Lower Bounds for Choiceless Polynomial Time via Symmetric XORCircuits}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {73:173:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772921},
ISSN = {18688969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18607},
URN = {urn:nbn:de:0030drops186077},
doi = {10.4230/LIPIcs.MFCS.2023.73},
annote = {Keywords: logic in computer science, finite model theory, descriptive complexity, symmetric computation, symmetric circuits, graph isomorphism}
}
Keywords: 

logic in computer science, finite model theory, descriptive complexity, symmetric computation, symmetric circuits, graph isomorphism 
Collection: 

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) 
Issue Date: 

2023 
Date of publication: 

21.08.2023 