Lower bounds for semi-adaptive data structures via corruption

DOI10.4230/LIPICS.FSTTCS.2020.20MaRDI QIDQ6839888zbMATH OpenFDO

Authors Pavel Dvořák, Bruno Loff

Publication date 23 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2020.20

zbMATH Keywords

corruption boundinformation theorypolynomial lower boundsemi-adaptive dynamic data structure

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A little advice can be very helpful
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
• Elements of Information Theory
• Information complexity versus corruption and applications to orthogonality and gap-Hamming
• Logarithmic Lower Bounds in the Cell-Probe Model
• On the distributional complexity of disjointness
• Popular conjectures imply strong lower bounds for dynamic problems
• The cell probe complexity of dynamic range counting
• The communication complexity of gap Hamming distance
• The Probabilistic Communication Complexity of Set Intersection
• Tight bounds for the partial-sums problem
• Towards polynomial lower bounds for dynamic problems

This page was built for publication: Lower bounds for semi-adaptive data structures via corruption

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