Certifying equality with limited interaction

DOI10.4230/LIPICS.APPROX-RANDOM.2014.545MaRDI QIDQ2969646zbMATH OpenOpenAlexFDO

Authors Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

Publication date 22 March 2017

Full work available at URL https://dblp.uni-trier.de/db/conf/approx/approx2014.html#BrodyCKWY14

zbMATH Keywords

communication complexityequalityinformation complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Certifying equality with limited interaction
• The communication complexity of set intersection and multiple equality testing
• scientific article; zbMATH DE number 1769898
• Equality, revisited
• Interactive Information Complexity

Cited in

(12)

• Equality alone does not simulate randomness
• Equality, revisited
• Amortized communication complexity of an equality predicate
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• `Non-interference' implies equality
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• Certifying equality with limited interaction
• Direct sum fails for zero-error average communication
• The communication complexity of set intersection and multiple equality testing
• The communication complexity of set intersection and multiple equality testing
• Worst Case Nonzero-Error Interactive Communication
• Lifting Theorems for Equality

This page was built for publication: Certifying equality with limited interaction

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