On derandomized composition of Boolean functions

DOI10.1007/s00037-019-00188-1zbMath1496.68142OpenAlexW2953625968MaRDI QIDQ2281253

Or Meir

Publication date: 19 December 2019

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-019-00188-1

zbMATH Keywords

circuit complexityderandomizationcommunication complexityformula complexitycircuit lower boundsKarchmer-Wigderson relationsKRW conjectureformula lower bounds

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Derandomized parallel repetition theorems for free games
• Communication complexity towards lower bounds on circuit depth
• Composition limits and separating examples for some Boolean function complexity measures
• Learning functions of \(k\) relevant variables
• Monotone separation of logarithmic space from logarithmic depth
• On rank vs. communication complexity
• Randomness is linear in space
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Separation of the monotone NC hierarchy
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
• Properties and applications of boolean function composition
• A New Kind of Tradeoffs in Propositional Proof Complexity
• The Pattern Matrix Method
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone circuits for matching require linear depth
• Deterministic Communication vs. Partition Number
• Lower Bounds for Elimination via Weak Regularity
• Fractional Covers and Communication Complexity
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Rectangles Are Nonnegative Juntas
• Extracting all the randomness and reducing the error in Trevisan's extractors
• The Erdős-Ko-Rado theorem for integer sequences

This page was built for publication: On derandomized composition of Boolean functions