18 citations · 109 across the 28 of their papers we have counts for
5 papers · 1 filter
On the cut-query complexity of approximating max-cut
Orestis Plevrakis, Seyoon Ragavan, S. Matthew Weinberg
We consider the problem of query-efficient global max-cut on a weighted undirected graph in the value oracle model examined by [RSW18]. Graph algorithms in this cut query model and…
An Improved Lower Bound for Matroid Intersection Prophet Inequalities
Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg
We consider prophet inequalities subject to feasibility constraints that are the intersection of matroids. The best-known algorithms achieve a -approximation, even when r…
Optimal Strategic Mining Against Cryptographic Self-Selection in Proof-of-Stake
Matheus V. X. Ferreira, Ye Lin Sally Hahn, S. Matthew Weinberg +1
Cryptographic Self-Selection is a subroutine used to select a leader for modern proof-of-stake consensus protocols, such as Algorand. In cryptographic self-selection, each round $r…
Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for all Distributions
Meryem Essaidi, Matheus V. X. Ferreira, S. Matthew Weinberg
We consider a revenue-maximizing seller with a single item for sale to multiple buyers with i.i.d. valuations. Akbarpour and Li (2020) show that the only optimal, credible, strateg…
On Infinite Separations Between Simple and Optimal Mechanisms
C. Alexandros Psomas, Ariel Schvartzman, S. Matthew Weinberg
We consider a revenue-maximizing seller with heterogeneous items for sale to a single additive buyer, whose values are drawn from a known, possibly correlated prior $\mathcal{D…