The query complexity of graph isomorphism: bypassing distribution testing lower bounds.
Krzysztof OnakXiaorui SunPublished in: STOC (2018)
Keyphrases
- query complexity
- lower bound
- graph isomorphism
- concept class
- vc dimension
- upper bound
- learning theory
- concept classes
- np hard
- membership queries
- exact learning
- graph mining
- sample complexity
- data complexity
- branch and bound
- equivalence queries
- pac learning
- objective function
- knowledge representation
- graph search
- upper and lower bounds
- learning algorithm
- concept learning