scientific article; zbMATH DE number 7053304
From MaRDI portal
Publication:5743425
zbMath1421.68019MaRDI QIDQ5743425
Jeff Edmonds, Arkadev Chattopadhyay, Toniann Pitassi, Faith Ellen
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095168
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Related Items (2)
Improved analysis of the online set cover problem with advice ⋮ Upper and Lower Bounds on the Power of Advice
Cites Work
- Unnamed Item
- Communication complexity under product and nonproduct distributions
- Private vs. common random bits in communication complexity
- 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
- Unifying the Landscape of Cell-Probe Lower Bounds
- Learning Complexity vs Communication Complexity
- New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
- 10.1162/153244303321897681
- Logarithmic Lower Bounds in the Cell-Probe Model
This page was built for publication: