Upper and Lower Bounds on the Power of Advice
From MaRDI portal
Publication:2816830
DOI10.1137/15M1031862zbMath1344.68089MaRDI QIDQ2816830
Toniann Pitassi, Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen
Publication date: 26 August 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) 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) Data structures (68P05)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An information statistics approach to data stream and communication complexity
- Communication complexity under product and nonproduct distributions
- Private vs. common random bits in communication complexity
- On the distributional complexity of disjointness
- Lower bounds for fully dynamic connectivity problems in graphs
- On randomized one-round communication complexity
- Towards proving strong direct product theorems
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
- A strong direct product theorem for disjointness
- Towards polynomial lower bounds for dynamic problems
- On Yao’s XOR-Lemma
- Unifying the Landscape of Cell-Probe Lower Bounds
- Learning Complexity vs Communication Complexity
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Should Tables Be Sorted?
- The Probabilistic Communication Complexity of Set Intersection
- New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
- 10.1162/153244303321897681
- Communication Complexity
- The cell probe complexity of dynamic range counting
- Logarithmic Lower Bounds in the Cell-Probe Model
