From the 1 of 7 linked papers with an AI index.
8 papers
Efficient Online Proportional Sampling with Applications to Smoothed Online Learning
Amirmahdi Mirfakhar, Maria-Florina Balcan, Hedyeh Beyhaghi
The paper proposes a data structure for efficiently performing online proportional sampling over high‑dimensional, piecewise‑structured domains under a σ‑smoothed adversary, and us…
CGES: Confidence-Guided Early Stopping for Efficient and Accurate Self-Consistency
Ehsan Aghazadeh, Ahmad Ghasemi, Hedyeh Beyhaghi +1
Large language models (LLMs) are often queried multiple times at test time, with predictions aggregated by majority vote. While effective, this self-consistency (Wang et al., 2023)…
Two-Sided Time-Independent Regret for Matching Markets with Limited Interviews
Amirmahdi Mirfakhar, Xuchuang Wang, Mengfan Xu +2
Two-sided matching platforms rely on preferences from both sides, yet participants can evaluate only a small fraction of potential partners. In practice, they use low-cost pre-matc…
The Secretary Problem with Predictions and a Chosen Order
Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi +2
We study a learning-augmented variant of the secretary problem, recently introduced by Fujii and Yoshida (2023), in which the decision-maker has access to machine-learned predictio…
The Active and Noise-Tolerant Strategic Perceptron
Maria-Florina Balcan, Hedyeh Beyhaghi
We initiate the study of active learning algorithms for classifying strategic agents. Active learning is a well-established framework in machine learning in which the learner selec…
Competitive Algorithms for Multi-Agent Ski-Rental Problems
Xuchuang Wang, Bo Sun, Hedyeh Beyhaghi +3
This paper introduces a novel multi-agent ski-rental problem that generalizes the classical ski-rental dilemma to a group setting where agents incur individual and shared costs. In…