Improved Lower Bounds on the Randomized Complexity of Graph Properties.

Amit Chakrabarti Subhash Khot

Published in: ICALP (2001)

Keyphrases

lower bound
graph properties
worst case
upper bound
graph theoretic
data structure
np hard
graph theory
optimal solution
multi dimensional
optimization problems
network analysis
vc dimension