scientific article; zbMATH DE number 7471669

MaRDI QIDQ5028429FDOQ5028429

Authors: Nils Vortmeier, Thomas Zeume 

Publication date: 9 February 2022

Full work available at URL: https://arxiv.org/abs/1910.06004

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 7650850
• scientific article; zbMATH DE number 7650849
• Parallel complexity of logical query programs
• On the power of parity queries in Boolean decision trees
• Automata, Languages and Programming
• On dynamic bit-probe complexity
• scientific article; zbMATH DE number 6292744
• On the parity complexity measures of Boolean functions
• The complexity of DNF of parities
• On the power of parity polynomial time

zbMATH Keywords

dynamic complexityarity hierarchyparity quantifier

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Title not available (Why is that?)
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• On ACC
• Title not available (Why is that?)
• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• Dyn-FO: A parallel, dynamic complexity class
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• On the quantifier-free dynamic complexity of reachability
• Dynamic complexity under definable changes
• The dynamic descriptive complexity of \(k\)-clique
• The dynamic complexity of formal languages
• SEPARATING AUXILIARY ARITY HIERARCHY OF FIRST-ORDER INCREMENTAL EVALUATION SYSTEMS USING (3K+1)-ary INPUT RELATIONS

Cited In (2)

• Title not available (Why is that?)
• The dynamic complexity of acyclic hypergraph homomorphisms

This page was built for publication:

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