Certifying equality with limited interaction
From MaRDI portal
Publication:343864
DOI10.1007/s00453-016-0163-6zbMath1353.68089OpenAlexW2396549623MaRDI QIDQ343864
Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev, Joshua Brody, Amit Chakrabarti
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/
lower boundsinformation theoryprivacydistributed computingcommunication complexitybig dataround 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)
Related Items
Communication complexity with small advantage ⋮ The communication complexity of functions with large outputs ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A direct product theorem for two-party bounded-round public-coin communication complexity
- An information statistics approach to data stream and communication complexity
- Quantum and approximate privacy
- Private vs. common random bits in communication complexity
- On the distributional complexity of disjointness
- On data structures and asymmetric communication complexity
- The space complexity of approximating the frequency moments
- Lower bounds for one-way probabilistic communication complexity and their application to space 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.
- Everywhere-Tight Information Cost Tradeoffs for Augmented Index
- Unifying the Landscape of Cell-Probe Lower Bounds
- Sparse and Lopsided Set Disjointness via Information Theory
- Nearly Private Information Retrieval
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- The Probabilistic Communication Complexity of Set Intersection
- Amortized Communication Complexity
- Communication Complexity
- The Communication Complexity of Correlation
- The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
- Advances in Cryptology - EUROCRYPT 2004
- Direct Product via Round-Preserving Compression
- Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
- Interactive information complexity
- Oblivious Polynomial Evaluation
- Elements of Information Theory
- Information Equals Amortized Communication
- From information to exact communication
- An information complexity approach to extended formulations
- 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
