On the cut-query complexity of approximating max-cut.

Orestis Plevrakis Seyoon Ragavan S. Matthew Weinberg

Published in: CoRR (2022)

Keyphrases

query complexity
max cut
planar graphs
membership queries
data complexity
graph model
np hard
graph partitioning
np complete problems
concept class
exact learning
spectral graph
resource consumption
expressive power
graph coloring
machine learning
vc dimension
learning algorithm