Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
type: Item
instance of: scholarly article
title: Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
zbMATH Open document ID: 1402.68073
author: Irit Dinur
author: Or Meir
published in: Computational Complexity
publication date: 2018-11-07T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5841/
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 6974166
zbMATH Keywords: communication complexity
zbMATH Keywords: de Morgan formulas
zbMATH Keywords: lower bounds
zbMATH Keywords: Karchmer-Wigderson relations
zbMATH Keywords: Karchmer-Wigderson games
zbMATH Keywords: KRW conjecture
Wikidata QID: Q123160149
MaRDI profile type: Publication
OpenAlex ID: W2741968539
cites work: How to compress interactive communication
cites work: Choosing, agreeing, and eliminating in communication complexity
cites work: Size-depth tradeoffs for Boolean formulae
cites work: Interactive information complexity
cites work: Information Equals Amortized Communication
cites work: The Parallel Evaluation of General Arithmetic Expressions
cites work: Mining circuit lower bound proofs for meta-algorithms
cites work: Q4023085
cites work: Communication complexity towards lower bounds on circuit depth
cites work: Amortized Communication Complexity
cites work: Toward better formula lower bounds
cites work: Monotone separation of logarithmic space from logarithmic depth
cites work: The Shrinkage Exponent of de Morgan Formulas is 2
cites work: Q4287360
cites work: The effect of random restrictions on formula size
cites work: Boolean function complexity. Advances and frontiers.
cites work: Interactive PCP
cites work: Fractional Covers and Communication Complexity
cites work: Super-logarithmic depth lower bounds via the direct sum in communication complexity
cites work: Monotone Circuits for Connectivity Require Super-Logarithmic Depth
cites work: Method of determining lower bounds for the complexity of \(\Pi\)-circuits
cites work: Average-case lower bounds for formula size
cites work: Communication Complexity
cites work: Shrinkage of de Morgan formulae under restriction
cites work: Monotone circuits for matching require linear depth
cites work: Applications of matrix methods to the theory of lower bounds in computational complexity
cites work: Q3281059
DOI: 10.1007/S00037-017-0159-X
description: scientific article; zbMATH DE number 6974166