Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
From MaRDI portal
Publication:1616616
DOI10.1007/s00037-017-0159-xzbMath1402.68073OpenAlexW2741968539WikidataQ123160149 ScholiaQ123160149MaRDI QIDQ1616616
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/
lower boundscommunication complexityKarchmer-Wigderson relationsKRW conjectureKarchmer-Wigderson gamesde Morgan formulas
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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
