On the Cut-Query Complexity of Approximating Max-Cut.

Orestis Plevrakis Seyoon Ragavan S. Matthew Weinberg

Published in: ICALP (2024)

Keyphrases

max cut
query complexity
planar graphs
data complexity
membership queries
np hard
graph model
np complete problems
spectral graph
exact learning
concept class
graph partitioning
special case
upper bound
expressive power
query answering