Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
DOI10.1007/S00037-017-0159-XzbMATH Open1402.68073OpenAlexW2741968539WikidataQ123160149 ScholiaQ123160149MaRDI QIDQ1616616FDOQ1616616
Authors: Irit Dinur, Or Meir 
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/
Recommendations
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- Improved composition theorems for functions and relations
- Communication complexity towards lower bounds on circuit depth
lower boundscommunication complexityKarchmer-Wigderson relationsKRW conjectureKarchmer-Wigderson gamesde Morgan formulas
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Cites Work
- Title not available (Why is that?)
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Size-depth tradeoffs for Boolean formulae
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Communication Complexity
- Boolean function complexity. Advances and frontiers.
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Fractional Covers and Communication Complexity
- Mining circuit lower bound proofs for meta-algorithms
- Title not available (Why is that?)
- The Shrinkage Exponent of de Morgan Formulas is 2
- The effect of random restrictions on formula size
- Shrinkage of de Morgan formulae under restriction
- Average-case lower bounds for formula size
- How to compress interactive communication
- The Parallel Evaluation of General Arithmetic Expressions
- Amortized Communication Complexity
- Interactive information complexity
- Information Equals Amortized Communication
- Monotone circuits for matching require linear depth
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- Interactive PCP
- Communication complexity towards lower bounds on circuit depth
- Choosing, agreeing, and eliminating in communication complexity
- Monotone separation of logarithmic space from logarithmic depth
- Title not available (Why is that?)
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
Cited In (12)
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Circuit lower bounds for MCSP from local pseudorandom generators
- Improved composition theorems for functions and relations
- Hardness magnification near state-of-the-art lower bounds
- Quantified Derandomization: How to Find Water in the Ocean
- Security in Communication Networks
- Toward better depth lower bounds: two results on the multiplexor relation
- Capturing one-way functions via NP-hardness of meta-complexity
- Dag-like communication and its applications
- Lifting Theorems for Equality
This page was built for publication: Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1616616)
