Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines.

Scott Diehl Dieter van Melkebeek

Published in: ICALP (2005)

Keyphrases

lower bound
upper bound
worst case
randomized algorithm
branch and bound
upper and lower bounds
randomized algorithms
branch and bound algorithm
linear programming relaxation
low dimensional
space time
hierarchical structure
approximation algorithms
vc dimension
constant factor
min sum