Bounds on Monotone Switching Networks for Directed Connectivity

DOI10.1145/3080520zbMath1426.68104arXiv0911.0664OpenAlexW2963815293MaRDI QIDQ4640280

Aaron Potechin

Publication date: 17 May 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

switching networkscircuit lower boundsNLLdirected connectivitymonotone computation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (4)

Static-memory-hard functions, and modeling the cost of space vs. time ⋮ Unnamed Item ⋮ Adventures in monotone complexity and TFNP ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width

This page was built for publication: Bounds on Monotone Switching Networks for Directed Connectivity