Improved composition theorems for functions and relations

DOI10.4230/LIPICS.APPROX-RANDOM.2018.48MaRDI QIDQ5009544zbMATH OpenFDO

Authors Sajin Koroth, Or Meir

Publication date 4 August 2021

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2018.48

zbMATH Keywords

circuit complexitycommunication complexitycompositionKRW conjecture

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• 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
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Toward better depth lower bounds: two results on the multiplexor relation

Cites work

• Applications of matrix methods to the theory of lower bounds in computational complexity
• Communication complexity towards lower bounds on circuit depth
• Fractional Covers and Communication Complexity
• scientific article; zbMATH DE number 549856 (Why is no real title available?)
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture

Cited in

(11)

• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• On derandomized composition of Boolean functions
• Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
• 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
• A nearly-4 n depth lower bound for formulas with restriction on top
• Toward better depth lower bounds: a KRW-like theorem for strong composition
• On the complexity of hazard-free formulas
• On the complexity of hazard-free formulas
• Toward better depth lower bounds: two results on the multiplexor relation

This page was built for publication: Improved composition theorems for functions and relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009544)