Amplification of One-Way Information Complexity via Codes and Noise Sensitivity

DOI10.1007/978-3-662-47672-7_78zbMath1440.68093OpenAlexW2397532001MaRDI QIDQ3448852

Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_78

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Communication complexity, information complexity (68Q11)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An information statistics approach to data stream and communication complexity
• Communication complexity
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Central limit theorems for empirical measures
• On randomized one-round communication complexity
• On the degree of Boolean functions as real polynomials
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Sparse and Lopsided Set Disjointness via Information Theory
• The Pattern Matrix Method
• Lower Bounds in Communication Complexity
• Composition Theorems in Communication Complexity
• Analysis of Boolean Functions
• Quantum lower bounds by polynomials
• Elements of Information Theory
• Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching

This page was built for publication: Amplification of One-Way Information Complexity via Codes and Noise Sensitivity