Parameterized complexity classes defined by threshold circuits: using sorting networks to show collapses with W-hierarchy classes

DOI10.1007/978-3-030-92681-6_28OpenAlexW4205455071MaRDI QIDQ2150563

Raffael M. Paranhos, Luiz Satoru Ochi, Janio Carlos Nascimento Silva, Uéverton S. Souza

Publication date: 29 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92681-6_28

zbMATH Keywords

parameterized complexitythreshold circuitsW-hierarchyAKS sorting network

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Improved sorting networks with O(log N) depth
• W-hierarchies defined by symmetric gates
• Sorting in \(c \log n\) parallel steps
• Ramanujan graphs
• Eigenvalues and expanders
• Threshold circuits of bounded depth
• Explicit Concentrators from Generalized N-Gons

This page was built for publication: Parameterized complexity classes defined by threshold circuits: using sorting networks to show collapses with W-hierarchy classes