Improved Monotone Circuit Depth Upper Bound for Directed Graph Reachability

Simple item page
dc.creatorVolkov, Sergey
dc.date2008-09-22
dc.date.accessioned2026-07-07T10:04:21Z
dc.date.available2026-07-07T10:04:21Z
dc.descriptionWe prove that the directed graph reachability problem (transitive closure) can be solved by monotone fan-in 2 boolean circuits of depth (1/2+o(1))(log n)^2, where n is the number of nodes. This improves the previous known upper bound (1+o(1))(log n)^2. The proof is non-constructive, but we give a constructive proof of the upper bound (7/8+o(1))(log n)^2.
dc.descriptionpreprint
dc.identifierhttps://arxiv.org/abs/0809.3614
dc.identifierhttp://arxiv.org/abs/0809.3614
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/169642
dc.subjectComputational Complexity
dc.titleImproved Monotone Circuit Depth Upper Bound for Directed Graph Reachability
dc.typetext

Files

Collections

arXiv