Improved depth lower bounds for small distance connectivity

DOI10.1007/S000370050014zbMATH Open0946.68060OpenAlexW2045001685MaRDI QIDQ1293359FDOQ1293359

Authors: Russell Impagliazzo, Toniann Pitassi, Paul Beame 

Publication date: 17 October 2000

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s000370050014

Recommendations

• Formulas vs. circuits for small distance connectivity
• Near-optimal small-depth lower bounds for small distance connectivity
• Formulas versus Circuits for Small Distance Connectivity
• Monotone Circuits for Connectivity Have Depth (log n)^2-o(1)

zbMATH Keywords

switching lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Interpolation, preservation, definability (03C40)

Cited In (7)

• One-way multiparty communication lower bound for pointer jumping with applications
• Formulas vs. circuits for small distance connectivity
• On some recent projection switching lemmas for small depth circuits
• Formulas versus Circuits for Small Distance Connectivity
• On the complexity of some problems on groups input as multiplication tables
• Title not available (Why is that?)
• Near-optimal small-depth lower bounds for small distance connectivity

This page was built for publication: Improved depth lower bounds for small distance connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1293359)