Near-Optimal Small-Depth Lower Bounds for Small

Abstract

We prove a lower bound for the s-t connectivity restricted to distance k for depth d circuits. Our lower bound is almost optimal.

Keywords

• Near-Optimal
• Small-Depth
• Lower
• Bounds
• for
• Small