Equality alone does not simulate randomness

DOI10.4230/LIPIcs.CCC.2019.14OpenAlexW2912462513MaRDI QIDQ5091765

Shachar Lovett, Marc Vinyals, Arkadev Chattopadhyay

Publication date: 27 July 2022

Full work available at URL: https://doi.org/10.4230/lipics.ccc.2019.14

zbMATH Keywords

derandomizationcommunication lower bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Dimension-free bounds and structural results in communication complexity ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity

Cites Work

• The landscape of communication complexity classes
• Crossing patterns of semi-algebraic sets
• On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
• On the power of quantum fingerprinting
• CREW PRAM<scp>s</scp> and Decision Trees
• The Probabilistic Communication Complexity of Set Intersection
• Interpolation by a Game
• Separations in Query Complexity Based on Pointer Functions
• Communication Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Equality alone does not simulate randomness