Certifying equality with limited interaction
DOI10.1007/S00453-016-0163-6zbMATH Open1353.68089OpenAlexW2396549623MaRDI QIDQ343864FDOQ343864
Authors: Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev 
Publication date: 29 November 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4722/
Recommendations
big datadistributed computinglower boundsinformation theorycommunication complexityprivacyround complexity
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Cites Work
- Elements of Information Theory
- The space complexity of approximating the frequency moments
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Advances in Cryptology - EUROCRYPT 2004
- On the exact space complexity of sketching and streaming small norms
- The Probabilistic Communication Complexity of Set Intersection
- Communication Complexity
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- An information statistics approach to data stream and communication complexity
- An information complexity approach to extended formulations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Private vs. common random bits in communication complexity
- On the distributional complexity of disjointness
- On data structures and asymmetric communication complexity
- Lower bounds for number-in-hand multiparty communication complexity, made easy
- Information cost tradeoffs for augmented index and streaming language recognition
- How to compress interactive communication
- Recognizing well-parenthesized expressions in the streaming model
- The hardness of being private
- Certifying equality with limited interaction
- The randomized communication complexity of set disjointness
- Everywhere-Tight Information Cost Tradeoffs for Augmented Index
- Unifying the landscape of cell-probe lower bounds
- Sparse and Lopsided Set Disjointness via Information Theory
- A direct product theorem for two-party bounded-round public-coin communication complexity
- Nearly Private Information Retrieval
- Amortized Communication Complexity
- The Communication Complexity of Correlation
- The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
- Direct product via round-preserving compression
- Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
- Title not available (Why is that?)
- Interactive information complexity
- Oblivious Polynomial Evaluation
- Information Equals Amortized Communication
- From information to exact communication
- Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Quantum and approximate privacy
Cited In (6)
- The communication complexity of functions with large outputs
- `Non-interference' implies equality
- Certifying equality with limited interaction
- The communication complexity of set intersection and multiple equality testing
- The communication complexity of set intersection and multiple equality testing
- Communication complexity with small advantage
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 Q343864)
