Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity

DOI10.4230/LIPIcs.CCC.2016.3zbMath1380.68193OpenAlexW2466575202MaRDI QIDQ5368737

Irit Dinur, Or Meir

Publication date: 10 October 2017

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.3

zbMATH Keywords

communication complexityKarchmer-Wigderson gamesKRW composition conjectureformula lower bounds

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

On the limits of gate elimination ⋮ Dag-like communication and its applications ⋮ Unnamed Item ⋮ The choice and agreement problems of a random function ⋮ On derandomized composition of Boolean functions ⋮ Unnamed Item ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Hardness magnification near state-of-the-art lower bounds

This page was built for publication: Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity