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

DOI10.1007/s00037-017-0159-xzbMath1402.68073OpenAlexW2741968539WikidataQ123160149 ScholiaQ123160149MaRDI QIDQ1616616

Or Meir, Irit Dinur

Publication date: 7 November 2018

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5841/

zbMATH Keywords

lower boundscommunication complexityKarchmer-Wigderson relationsKRW conjectureKarchmer-Wigderson gamesde Morgan formulas

Mathematics Subject Classification ID

Related Items (6)

Quantified Derandomization: How to Find Water in the Ocean ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lifting Theorems for Equality ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Toward better depth lower bounds: two results on the multiplexor relation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• Choosing, agreeing, and eliminating in communication complexity
• Size-depth tradeoffs for Boolean formulae
• Communication complexity towards lower bounds on circuit depth
• Monotone separation of logarithmic space from logarithmic depth
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Mining circuit lower bound proofs for meta-algorithms
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Applications of matrix methods to the theory of lower bounds in computational complexity
• How to compress interactive communication
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Interactive PCP
• Monotone circuits for matching require linear depth
• The Shrinkage Exponent of de Morgan Formulas is 2
• The Parallel Evaluation of General Arithmetic Expressions
• The effect of random restrictions on formula size
• Shrinkage of de Morgan formulae under restriction
• Fractional Covers and Communication Complexity
• Amortized Communication Complexity
• Communication Complexity
• Toward better formula lower bounds
• Interactive information complexity
• Information Equals Amortized Communication
• Average-case lower bounds for formula size

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