On symmetric circuits and fixed-point logics

DOI10.1007/S00224-016-9692-2MaRDI QIDQ2363965zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yanyan Li

Publication date 17 July 2017

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

countingfixed-point logicmajoritysymmetric circuituniformity

Mathematics Subject Classification ID

Logic in computer science (03B70)

Recommendations

• scientific article; zbMATH DE number 6691390
• Symmetric Circuits for Rank Logic
• Symmetric circuits for rank logic
• Computer Science Logic
• The use of symmetric variables for reducing the complexity of logical circuits
• Symmetric Logic of Proofs
• On the symmetry of logic
• scientific article; zbMATH DE number 1086678
• Symmetries of quantified Boolean formulas
• Symmetric multi-valued logic functions: characterization and synthesis

Cites work

• A restricted second order logic for finite structures
• An optimal lower bound on the number of variables for graph identification
• Boolean Functions, Invariance Groups, and Parallel Complexity
• Choiceless polynomial time
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Definability by constant-depth polynomial-size circuits
• Fixed Point Logics
• Fixed-point definability and polynomial time on graphs with excluded minors
• scientific article; zbMATH DE number 6691390 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 979011 (Why is no real title available?)
• scientific article; zbMATH DE number 1086678 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• Maximum matching and linear programming in fixed-point logic with counting
• Relational queries computable in polynomial time

Cited in

(15)

• Calculi for symmetric queries
• scientific article; zbMATH DE number 6691390 (Why is no real title available?)
• Symmetric multi-valued logic functions: characterization and synthesis
• scientific article; zbMATH DE number 1086678 (Why is no real title available?)
• A finite-model-theoretic view on propositional proof complexity
• Symmetric Circuits for Rank Logic
• Symmetric circuits for rank logic
• Computer Science Logic
• scientific article; zbMATH DE number 3186297 (Why is no real title available?)
• Inapproximability of unique games in fixed-point logic with counting
• Choiceless computation and symmetry: limitations of definability
• Symmetric arithmetic circuits
• Symmetric arithmetic circuits
• Limits of symmetric computation (invited talk)
• Undefinability of approximation of 2-to-2 games

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2363965)