Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
From MaRDI portal
Publication:1616616
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
Cites work
- scientific article; zbMATH DE number 3162894 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 549856 (Why is no real title available?)
- Amortized Communication Complexity
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Average-case lower bounds for formula size
- Boolean function complexity. Advances and frontiers.
- Choosing, agreeing, and eliminating in communication complexity
- Communication Complexity
- Communication complexity towards lower bounds on circuit depth
- Fractional Covers and Communication Complexity
- How to compress interactive communication
- Information Equals Amortized Communication
- Interactive PCP
- Interactive information complexity
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Mining circuit lower bound proofs for meta-algorithms
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Monotone circuits for matching require linear depth
- Monotone separation of logarithmic space from logarithmic depth
- Shrinkage of de Morgan formulae under restriction
- Size-depth tradeoffs for Boolean formulae
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- The Parallel Evaluation of General Arithmetic Expressions
- The Shrinkage Exponent of de Morgan Formulas is 2
- The effect of random restrictions on formula size
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
Cited in
(12)- Quantified Derandomization: How to Find Water in the Ocean
- Toward better depth lower bounds: two results on the multiplexor relation
- Lifting Theorems for Equality
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
- Capturing one-way functions via NP-hardness of meta-complexity
- Circuit lower bounds for MCSP from local pseudorandom generators
- Hardness magnification near state-of-the-art lower bounds
- Improved composition theorems for functions and relations
- Dag-like communication and its applications
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Security in Communication Networks
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
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)
