Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting.
Ofer GrossmanMeghal GuptaMark SellkePublished in: FOCS (2023)
Keyphrases
- lower bound
- upper bound
- exact and approximate
- exact solution
- randomized algorithms
- branch and bound algorithm
- branch and bound
- worst case
- optimal solution
- lower and upper bounds
- randomized algorithm
- objective function
- np hard
- upper and lower bounds
- lower bounding
- space time
- higher dimensional
- linear programming
- low dimensional
- sample complexity
- search space
- competitive ratio