Improved Monotone Circuit Depth Upper Bound for Directed Graph Reachability

Details Improved Monotone Circuit Depth Upper Bound for Directed Graph Reachability Improved Monotone Circuit Depth Upper Bound for Directed Graph Reachability

2008-09-22

arxiv.org/abs/0809.3614v1

Computer Science

Computational Complexity

preprint

Scientific paper

We 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.

Affiliated with

Also associated with

No associations

Rating

Improved Monotone Circuit Depth Upper Bound for Directed Graph Reachability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Monotone Circuit Depth Upper Bound for Directed Graph Reachability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Monotone Circuit Depth Upper Bound for Directed Graph Reachability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-299142