scientific article; zbMATH DE number 6538681

DOI10.4086/TOC.2015.V011A019MaRDI QIDQ3467513zbMATH OpenOpenAlexFDO

Authors Joshua Brody, Kasper Green Larsen

Publication date 2 February 2016

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1208.2846

zbMATH Keywords

adaptivecircuit complexitycommunication complexitydata structuresdynamic data structuresencodinglower bounds

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Non-adaptive data structure bounds for dynamic predecessor
• Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds
• On adaptive DLOGTIME and POLYLOGTIME reductions
• scientific article; zbMATH DE number 3852432
• An optimal data structure to handle dynamic environments in non-deterministic computations
• Towards polynomial lower bounds for dynamic problems
• scientific article; zbMATH DE number 7250167
• A polynomial lower bound on adaptive complexity of submodular maximization
• Lower bounds for dynamic data structures on algebraic RAMs
• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

Cites work

• Should Tables Be Sorted?
• Simplex range reporting on a pointer machine

Cited in

(8)

• The function-inversion problem: barriers and opportunities
• Upper and lower bounds on the power of advice
• scientific article; zbMATH DE number 3852432 (Why is no real title available?)
• scientific article; zbMATH DE number 7250167 (Why is no real title available?)
• Non-adaptive data structure bounds for dynamic predecessor
• Lower bounds for data structures with space close to maximum imply circuit lower bounds
• Sampling lower bounds: Boolean average-case and permutations
• Optimal non-adaptive cell probe dictionaries and hashing

This page was built for publication:

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