On symmetric circuits and fixed-point logics

DOI10.1007/s00224-016-9692-2zbMath1366.68047DBLPjournals/mst/AndersonD17OpenAlexW2282320536WikidataQ59614910 ScholiaQ59614910MaRDI QIDQ2363965

Yanyan Li

Publication date: 17 July 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-016-9692-2

zbMATH Keywords

uniformitycountingmajorityfixed-point logicsymmetric circuit

Mathematics Subject Classification ID

Related Items (2)

Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Choiceless polynomial time
• An optimal lower bound on the number of variables for graph identification
• A restricted second order logic for finite structures
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Boolean Functions, Invariance Groups, and Parallel Complexity
• Relational queries computable in polynomial time
• Definability by constant-depth polynomial-size circuits
• Fixed Point Logics
• Maximum Matching and Linear Programming in Fixed-Point Logic with Counting
• Fixed-point definability and polynomial time on graphs with excluded minors

This page was built for publication: On symmetric circuits and fixed-point logics