2 citations · 4 across the 7 of their papers we have counts for
7 papers
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 :…
Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values
Yurong Liu, R. Teal Witter, Flip Korn +4
Banzhaf values provide a popular, interpretable alternative to the widely-used Shapley values for quantifying the importance of features in machine learning models. Like Shapley va…
Searching, Sorting, and Cake Cutting in Rounds
Simina Brânzei, Dimitris Paparas, Nicholas Recker
We study searching and sorting in rounds motivated by a fair division question: given a cake cutting problem with players, compute a fair allocation in at most rounds of in…
Pricing for Online Resource Allocation: Intervals and Paths
Shuchi Chawla, J. Benjamin Miller, Yifeng Teng
We present pricing mechanisms for several online resource allocation problems which obtain tight or nearly tight approximations to social welfare. In our settings, buyers arrive on…
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer
Xi Chen, George Matikas, Dimitris Paparas +1
We show that the Revenue-Optimal Deterministic Mechanism Design problem for a single additive buyer is #P-hard, even when the distributions have support size 2 for each item and, m…
The Complexity of Optimal Multidimensional Pricing
Xi Chen, Ilias Diakonikolas, Dimitris Paparas +2
We resolve the complexity of revenue-optimal deterministic auctions in the unit-demand single-buyer Bayesian setting, i.e., the optimal item pricing problem, when the buyer's value…
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…