publications

2026

1. ALT

   Reward Selection with Noisy Observations

   Kamyar Azizzadenesheli, Trung Dang, Aranyak Mehta, Alexandros Psomas, and Qian Zhang

   In International Conference on Algorithmic Learning Theory, 2026

   Abs arXiv

   We study the problem of maximization under noisy values. In particular, there are n boxes with hidden i.i.d. reward x_i from an unknown distribution; these values are pertubed with independent heterogeneous Gaussian noises, producing y_i’s. We must choose one box from only knowing y_i and the variances of the Gaussian noises, obtaining reward x_i from such box. We show that the policy of "selecting \max y_i" and its variants of "selecting \max y_i - c \sigma_i" can be far from the hindsight optimal; however, a small pertubation to this policy, namely "selecting \max y_i$ among the low variance boxes" may achieve a constant approximation to the hindsight optimal within some regime, and no algorithms can obtain a constant approximation outside of this regime.

2. Manuscript

   Fair Division Under Inaccurate Preferences

   Trung Dang, Daniel Halpern, Anuran Makur, Alexandros Psomas, Japneet Singh, and Paritosh Verma

   arXiv preprint arXiv:2602.24169, 2026

   Abs arXiv

   We explore the broad landscape of fair division of indivisible items given inaccurate cardinal preferences, with a focus on minimizing envy. We consider various settings based on whether the true preferences of the agents are stochastic or worst-case, and whether the inaccuracies, modeled as additive noise, are stochastic or worst-case. When the true preferences are stochastic, we show that envy-free allocations can be computed with high probability; this is achieved both in the setting with stochastic and worst-case noise. When the true preferences are worst-case, and the noise is bounded, we analyze the maximum envy achieved by the well-known Round-Robin algorithm. Lastly, we consider a setting with worst-case preferences and noise, where the true preferences for each item are revealed upon its allocation. Here, we give an efficient online algorithm that guarantees logarithmic maximum envy with high probability, for bounded noise. This result builds upon and generalizes a known result from algorithmic discrepancy to a setting with noisy input data.

2025

1. SODA

   A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization

   Shuchi Chawla, Dimitris Christou, Trung Dang, Zhiyi Huang, Gregory Kehne, and Rojin Rezvan

   In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

   Abs arXiv

   We derive a novel multi-dimensional online contention resolution scheme with the objective of maximizing revenue. In particular, we obtain polylog upper and lower bounds to the ex-ante buy-many objective, achieved via an sequential dynamic item pricing mechanism.

2. ISIT

   Robust Max Selection

   Trung Dang and Zhiyi Huang

   In 2025 IEEE International Symposium on Information Theory (ISIT), 2025

   Abs arXiv

   We introduce a new model to study algorithm design under unreliable information. Under our model, algorithms can perform black-box comparison queries between any pair of elements; however, queries regarding corrupted elements may have arbitrary output. In particular, corrupted elements do not need to behave as any consistent values, and may introduce cycles in the elements’ ordering. As a first result, we obtain tight (up to polylog) upper and lower bound for the query complexity for deterministic and randomized algorithms to determine a minimum-sized set that contains the maximum value.

3. WINE

   Multi-Unit Combinatorial Prophet Inequalities

   Shuchi Chawla, Trung Dang, Zhiyi Huang, and Yifan Wang

   In International Conference on Web and Internet Economics, 2025

   Abs arXiv

   We consider the combinatorial prophet inequality setting where buyers have XOS valuations over the items, with the extension that each item have k copies. We study the dependence of the competitive ratio on k. We show that 1. multi-unit static item pricing is strictly harder than single-unit static item pricing, 2. multi-unit dynamic item pricing is asymptotically similar to single-unit static item pricing, and 3. it is possible to obtain strictly better than 1/2 (in fact, close to 1-1/e) ratio if we emply static per-copy pricing in the multi-unit case.

4. WINE

   Commitment Gap via Correlation Gap

   Shuchi Chawla, Dimitris Christou, and Trung Dang

   In International Conference on Web and Internet Economics, 2025

   Abs arXiv

   We study the general model of Costly Information Combinatorial Selection (CICS). In this problem, a decision maker needs to select a feasible subset of stochastic variables, and can only learn information about their values through a series of costly steps, modeled by a Markov decision process. The algorithmic objective is to maximize the total value of the selection *minus* the cost of information acquisition. In this work, we obtain improved bounds on the commitment gap of CICS through a reduction to a simpler problem of Bayesian Combinatorial Selection where information is free. By establishing a close relationship between these problems, we are able to relate the commitment gap of CICS to ex ante free-order prophet inequalities. As a consequence, we obtain improved approximation results for CICS, including the well-studied variant of Pandora’s Box with Optional Inspection under matroid feasibility constraints.

2023

1. NeurIPS

   Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1 + α Moments

   Trung Dang, Jasper Lee, Maoyuan Song, and Paul Valiant

   In Advances in Neural Information Processing Systems, 2023

   Abs arXiv

   We show that the classic median-of-means estimator for mean estimation is beyond-worst-case optimal, for a specific notion of beyond-worst-case that interpolates between instance-optimality and Pareto optimality. Notably, we show this by constructing a distribution q for every distribution p that is indistinguishable from p using as many samples as MoM, while having separated mean from p.

2. Manuscript

   Improving Pearson’s chi-squared test: hypothesis testing of distributions–optimally

   Trung Dang, Walter McKelvie, Paul Valiant, and Hongao Wang

   arXiv preprint arXiv:2310.09408, 2023

   Abs arXiv

   We consider the problem of "hypothesis testing": given samples from an unknown distribution p and a hypothesis distribution p, we need to determine if p = q or |p - q| > \eps with probability > 1 - δusing as few samples as possible. We introduce a new tester, efficiently computable and easy to use, which is found via a new non-convex optimization framework that essentially seeks to "find the tester whose Chernoff bounds on its performance are as good as possible". This tester is 1+o(1) optimal, in that the number of samples n needed by the tester is within 1+o(1) factor of the samples needed by *any* tester, even non-linear testers. We complement this algorithmic framework with matching lower bounds saying, essentially, that "our tester is instance-optimal, even to 1+o(1) factors, to the degree that Chernoff bounds are tight". Our overall non-convex optimization framework extends well beyond the current problem and is of independent interest.

2021

1. NSysS

   MGD: A Utility Metric for Private Data Publication

   Zitao Li, Trung Dang, Tianhao Wang, and Ninghui Li

   In Proceedings of the 8th International Conference on Networking, Systems and Security, Cox’s Bazar, Bangladesh, 2021

   DOI