Podcast Beta
Questions and Answers
What type of problems do the reductions from communication complexity of lopsided set disjointness help establish lower bounds for?
high-dimensional, constant-dimensional geometric, dynamic problems
What is the new bound established for 4-dimensional range reporting given space O(n poly lg n)?
$\Omega(lg n / lg lg n)$
What recent result raised the prospect that higher dimensions could be easy in terms of reporting time?
[Nekrich, SoCG'07] solved 3D reporting in near-constant time
What problem has a tight space lower bound for the partial match problem with constant query time?
Signup and view all the answers
What type of lower bound was established for reachability oracles?
Signup and view all the answers
