Improved depth lower bounds for small distance connectivity

DOI10.1007/s000370050014zbMath0946.68060OpenAlexW2045001685MaRDI QIDQ1293359

Russell Impagliazzo, Toniann Pitassi, P. W. 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

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)

Related Items (4)

Formulas versus Circuits for Small Distance Connectivity ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ On the complexity of some problems on groups input as multiplication tables ⋮ Unnamed Item

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