A topological approach to non-uniform complexity

DOI10.1016/J.IC.2019.104443MaRDI QIDQ2280323zbMATH OpenOpenAlexFDO

Authors Silke Czarnetzki, A. Krebs

Publication date 18 December 2019

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2019.104443

zbMATH Keywords

algebracircuit classesdualitylanguage theorytopology

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algebraic theory of languages and automata (68Q70)

Recommendations

• Using duality in circuit complexity
• Expressibility and Nonuniform Complexity Classes
• Nonuniform complexity classes, decision graphs and homological properties of posets
• Instruction sequence based non-uniform complexity classes
• On uniformity within \(NC^ 1\)

Cites work

• \(NC^ 1\): The automata-theoretic viewpoint
• A topological approach to recognition
• An effective characterization of the alternation hierarchy in two-variable logic
• Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
• CONSTANT-DEPTH PERIODIC CIRCUITS
• Equational descriptions of languages
• Expressibility and Parallel Complexity
• scientific article; zbMATH DE number 4033093 (Why is no real title available?)
• scientific article; zbMATH DE number 53371 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• Inequalities for one-step products
• Linear circuits, two-variable logic and weakly blocked monoids
• Logic Meets Algebra: the Case of Regular Languages
• Lower bounds for modular counting by circuits with modular gates
• Non-uniform automata over groups
• On finite monoids having only trivial subgroups
• Profinite categories and semidirect products
• Profinite Methods in Automata Theory
• Regular languages and Stone duality
• STACS 2005
• Superlinear lower bounds for bounded-width branching programs
• The Birkhoff theorem for finite algebras
• The kernel of monoid morphisms
• The Theory of Representation for Boolean Algebras
• Ultrafilters on words for a fragment of logic

Cited in

(8)

• Special issue: selected papers of the 10th international conference on language and automata theory and applications, LATA 2016
• Using duality in circuit complexity
• Nonuniform complexity classes, decision graphs and homological properties of posets
• scientific article; zbMATH DE number 4002078 (Why is no real title available?)
• scientific article; zbMATH DE number 2152018 (Why is no real title available?)
• Topological Framework for Non‐Priority
• Topological complexity of the work map
• STACS 2004

This page was built for publication: A topological approach to non-uniform complexity

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