Pointer chasing via triangular discrimination

DOI10.1017/S0963548320000085MaRDI QIDQ4993101zbMATH OpenOpenAlexFDO

Authors Amir Yehudayoff

Publication date 15 June 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1017/s0963548320000085

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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) Distributed algorithms (68W15)

Recommendations

• The communication complexity of pointer chasing: applications of entropy and sampling
• The communication complexity of pointer chasing
• scientific article; zbMATH DE number 1954386
• Communication complexity of statistical distance

Cites work

• scientific article; zbMATH DE number 1263186 (Why is no real title available?)
• A counterexample to strong parallel repetition
• A functional analysis proof of Gromov's polynomial growth theorem
• A tight unconditional lower bound on distributed randomwalk computation
• Disorder, entropy and harmonic functions
• Elements of Information Theory
• Homomorphisms to \(\mathbb R\) constructed from random walks
• How to compress interactive communication
• Information Theory and Statistics: A Tutorial
• Interaction in Quantum Communication
• Lower bounds for predecessor searching in the cell probe model
• Lower bounds on communication complexity
• On quantum and probabilistic communication: Las Vegas and one-way protocols
• On the distributional complexity of disjointness
• On the power of unique 2-prover 1-round games
• Rounds in Communication Complexity Revisited
• Some bounds on multiparty communication complexity of pointer jumping
• Some inequalities for information divergence and related measures of discrimination
• Superlinear lower bounds for multipass graph processing
• The communication complexity of pointer chasing

Cited in

(4)

• How the classical pointer moves
• Quantum state testing beyond the polarizing regime and quantum triangular discrimination
• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• The communication complexity of pointer chasing

This page was built for publication: Pointer chasing via triangular discrimination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993101)