14 citations · 27 across the 20 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.CC2020
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an…
cs.GT2020
Multi-item Non-truthful Auctions Achieve Good Revenue
Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier +2
We present a general framework for designing approximately revenue-optimal mechanisms for multi-item additive auctions, which applies to both truthful and non-truthful auctions. Gi…