Publication:343867: Difference between revisions
From MaRDI portal
Publication:343867
Created automatically from import240129110113 |
EloiFerrer (talk | contribs) m EloiFerrer moved page A discrepancy lower bound for information complexity to A discrepancy lower bound for information complexity: Duplicate |
(No difference)
|
Latest revision as of 12:38, 29 April 2024
DOI10.1007/s00453-015-0093-8zbMath1353.68088arXiv1112.2000OpenAlexW2113315930MaRDI QIDQ343867
Omri Weinstein, Mark Braverman
Publication date: 29 November 2016
Published in: Algorithmica, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1112.2000
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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications, Interactive Information Complexity, Interactive Information Complexity, Superlinear lower bounds for multipass graph processing, Unnamed Item, Information complexity and applications., Compressing Interactive Communication Under Product Distributions, Information lower bounds via self-reducibility, The communication complexity of addition, Unnamed Item, The Communication Complexity of Set Intersection and Multiple Equality Testing, Exponential Separation of Communication and External Information, Communication Complexity of Statistical Distance, Upper bounds on communication in terms of approximate rank
Cites Work
- Unnamed Item
- Unnamed Item
- A full proof of the BGW protocol for perfectly secure multiparty computation
- An information statistics approach to data stream and communication complexity
- Quantum and approximate privacy
- On the distributional complexity of disjointness
- Towards proving strong direct product theorems
- How to compress interactive communication
- A strong direct product theorem for disjointness
- Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
- Privacy, additional information and communication
- Communication Complexity
- The Communication Complexity of Correlation
- Interactive information complexity
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Information Equals Amortized Communication
- The communication complexity of addition
- A Zero-One Law for Boolean Privacy
- Exponential Separation of Information and Communication for Boolean Functions