4 papers
Robust Max Selection
Trung Dang, Zhiyi Huang
We introduce a new model to study algorithm design under unreliable information, and apply this model for the problem of finding the uncorrupted maximum element of a list containin…
A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
Shuchi Chawla, Dimitris Christou, Trung Dang +3
We study multi-buyer multi-item sequential item pricing mechanisms for revenue maximization with the goal of approximating a natural fractional relaxation -- the ex ante optimal re…
Improving Pearson's chi-squared test: hypothesis testing of distributions -- optimally
Trung Dang, Walter McKelvie, Paul Valiant +1
Pearson's chi-squared test, from 1900, is the standard statistical tool for "hypothesis testing on distributions": namely, given samples from an unknown distribution that may o…
Reward Selection with Noisy Observations
Kamyar Azizzadenesheli, Trung Dang, Aranyak Mehta +2
We study a fundamental problem in optimization under uncertainty. There are boxes; each box contains a hidden reward . Rewards are drawn i.i.d. from an unknown distrib…