Pointer chasing via triangular discrimination
From MaRDI portal
Publication:4993101
DOI10.1017/S0963548320000085zbMath1504.68078OpenAlexW3024696485MaRDI QIDQ4993101
Publication date: 15 June 2021
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548320000085
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) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Superlinear lower bounds for multipass graph processing
- Homomorphisms to \(\mathbb R\) constructed from random walks
- Disorder, entropy and harmonic functions
- Lower bounds on communication complexity
- On the distributional complexity of disjointness
- Some bounds on multiparty communication complexity of pointer jumping
- Lower bounds for predecessor searching in the cell probe model
- How to Compress Interactive Communication
- A tight unconditional lower bound on distributed randomwalk computation
- A Counterexample to Strong Parallel Repetition
- On quantum and probabilistic communication
- Interaction in Quantum Communication
- On the power of unique 2-prover 1-round games
- Rounds in Communication Complexity Revisited
- Some inequalities for information divergence and related measures of discrimination
- A functional analysis proof of Gromov's polynomial growth theorem
- Elements of Information Theory
- Information Theory and Statistics: A Tutorial
- The communication complexity of pointer chasing
This page was built for publication: Pointer chasing via triangular discrimination
