2 citations · 4 across the 7 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
The Query Complexity of Local Search in Rounds on General Graphs
Simina Brânzei, Ioannis Panageas, Dimitris Paparas
We analyze the query complexity of finding a local minimum in rounds on general graphs. More precisely, given a graph and oracle access to an unknown function $f :…
cs.CC2012★ 1 cited
The Complexity of Non-Monotone Markets
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We then prove that it is PPAD-hard to compute an approximate…