An Interactive Information Odometer and Applications
From MaRDI portal
Publication:2941524
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
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
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
Cites Work
- 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
- Unnamed Item
