Communication complexity towards lower bounds on circuit depth

DOI10.1007/s00037-001-8195-xzbMath1053.68048OpenAlexW2003104918MaRDI QIDQ1601024

Jiří Sgall, Steven Rudich, Russell Impagliazzo, Jeff Edmonds

Publication date: 17 June 2002

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

Full work available at URL: https://doi.org/10.1007/s00037-001-8195-x

zbMATH Keywords

circuit depth complexityuniversal composition relation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (14)

Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Deterministic Communication vs. Partition Number ⋮ Lower bound on SNARGs in the random oracle model ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ Unnamed Item ⋮ The direct sum of universal relations ⋮ Unnamed Item ⋮ On derandomized composition of Boolean functions ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Unnamed Item ⋮ Lifting Theorems for Equality ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Toward better depth lower bounds: two results on the multiplexor relation ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets

This page was built for publication: Communication complexity towards lower bounds on circuit depth