Equality alone does not simulate randomness

DOI10.4230/LIPICS.CCC.2019.14MaRDI QIDQ5091765zbMATH OpenOpenAlexFDO

Authors Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

Publication date 27 July 2022

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

zbMATH Keywords

communication lower boundderandomization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1769898
• Equality, revisited
• Certifying equality with limited interaction
• Separating deterministic from randomized multiparty communication complexity
• Nondeterministic and randomized Boolean hierarchies in communication complexity

Cites work

• Communication Complexity
• CREW PRAM<scp>s</scp> and Decision Trees
• Crossing patterns of semi-algebraic sets
• scientific article; zbMATH DE number 524134 (Why is no real title available?)
• Interpolation by a Game
• On the power of quantum fingerprinting
• On the relative complexity of resolution refinements and cutting planes proof systems
• Stabbing planes
• The landscape of communication complexity classes
• The Probabilistic Communication Complexity of Set Intersection
• The randomized communication complexity of set disjointness

Cited in

(12)

• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Dimension-free bounds and structural results in communication complexity
• A Borsuk-Ulam lower bound for sign-rank and its applications
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Factorization norms and an inverse theorem for MaxCut
• Separation of the factorization norm and randomized communication complexity
• Randomized communication and implicit graph representations
• Unambiguous parity-query complexity
• Better boosting of communication oracles, or not
• A lower bound on the trace norm of Boolean matrices and its applications
• Secret sharing, slice formulas, and monotone real circuits
• Equality is far weaker than constant-cost communication

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

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