An Interactive Information Odometer and Applications

DOI10.1145/2746539.2746548zbMath1321.68260OpenAlexW2058766981MaRDI QIDQ2941524

Omri Weinstein, Mark Braverman

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2746539.2746548

zbMATH Keywords

information complexitysecure computationdirect product theoremsinteractive compression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Cryptography (94A60) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Information theory (general) (94A15) Network protocols (68M12)

Related Items (6)

Interactive Information Complexity ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ The work of Mark Braverman ⋮ Information complexity and applications. ⋮ New Strong Direct Product Results in Communication Complexity ⋮ Communication Complexity of Statistical Distance

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: An Interactive Information Odometer and Applications