Complexity of modular circuits

DOI10.1145/3531130.3533350MaRDI QIDQ6649462zbMATH OpenFDO

Authors Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski

Publication date 6 December 2024

Full work available at URL https://doi.org/10.1145/3531130.3533350

zbMATH Keywords

circuit complexitycircuit satisfiabilitymodular circuits

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A degree-decreasing lemma for \((\text{MOD}_q - \text{MOD}_p)\) circuits
• A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\)
• A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits
• A note on a theorem of Barrington, Straubing and Thérien
• Even Faster Algorithms for CSAT Over supernilpotent Algebras.
• Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
• Intermediate problems in modular circuits satisfiability
• Lower Bounds for (MOD_p - MOD_m) Circuits
• Non-uniform automata over groups
• On ACC
• Representing Boolean functions as polynomials modulo composite numbers
• Results on the equivalence problem for finite groups.
• Satisfiability in multi-valued circuits
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• The complexity of satisfiability of small depth circuits
• The complexity of solving equations over finite groups
• The complexity of the equation solvability and equivalence problems over finite groups
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• Which problems have strongly exponential complexity?

Cited in

(1)

• Violating constant degree hypothesis requires breaking symmetry

This page was built for publication: Complexity of modular circuits

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