Skip to main content

New answers tagged

2 votes

Use of transitive closure in proof of NC hierarchy collapse

The answer by Mic is correct. If you're not comfortable thinking of this in terms of Transitive Closure, instead use the fact that NL is in NC^2. In NL, it is easy to determine the depth of each ...
Eric Allender's user avatar
2 votes

Use of transitive closure in proof of NC hierarchy collapse

The issue may be that the uniform circuit description is not leveled, you just see gates and wires. But using TC, you can compute a level number for every gate.
mic's user avatar
  • 356
9 votes
Accepted

Are there other proofs for Barrington's theorem?

After reading the comments to get clearer on the motivation, I think we can say two things (one from the comments, one perhaps not mentioned yet): Given the lack of responses, even with attention ...
Joshua Grochow's user avatar

Top 50 recent answers are included