Toward better depth lower bounds: strong composition of XOR and a random function

DOI10.4230/LIPICS.STACS.2025.26MaRDI QIDQ7287760zbMATH OpenFDO

Authors Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin

Publication date 24 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2025.26

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Boolean function complexity. Advances and frontiers.
• Communication complexity towards lower bounds on circuit depth
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 549856 (Why is no real title available?)
• KRW composition theorems via lifting
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• On convex complexity measures
• Shrinkage of De Morgan formulae by spectral techniques
• 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 effect of random restrictions on formula size
• The Shrinkage Exponent of de Morgan Formulas is 2
• Toward better depth lower bounds: a KRW-like theorem for strong composition
• Toward better depth lower bounds: the XOR-KRW 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

This page was built for publication: Toward better depth lower bounds: strong composition of XOR and a random function

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