3 citations · 9 across the 11 of their papers we have counts for
11 papers
Cost-aware Stopping for Bayesian Optimization
Qian Xie, Linda Cai, Alexander Terenin +2
In automated machine learning, scientific discovery, and other applications of Bayesian optimization, deciding when to stop evaluating expensive black-box functions in a cost-aware…
Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel
Shivam Gupta, Linda Cai, Sitan Chen
Sampling algorithms play an important role in controlling the quality and runtime of diffusion model inference. In recent years, a number of works~\cite{chen2023sampling,chen2023od…
Recent Developments in Pandora's Box Problem: Variants and Applications
Hedyeh Beyhaghi, Linda Cai
In 1979, Weitzman introduced Pandora's box problem as a framework for sequential search with costly inspections. Recently, there has been a surge of interest in Pandora's box probl…
Selling to Multiple No-Regret Buyers
Linda Cai, S. Matthew Weinberg, Evan Wildenhain +1
We consider the problem of repeatedly auctioning a single item to multiple i.i.d buyers who each use a no-regret learning algorithm to bid over time. In particular, we study the se…
Baechi: Fast Device Placement of Machine Learning Graphs
Beomyeol Jeon, Linda Cai, Chirag Shetty +6
Machine Learning graphs (or models) can be challenging or impossible to train when either devices have limited memory, or models are large. To split the model across devices, learn…
Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS
Hedyeh Beyhaghi, Linda Cai
Weitzman introduced Pandora's box problem as a mathematical model of sequential search with inspection costs, in which a searcher is allowed to select a prize from one of alter…
99% Revenue with Constant Enhanced Competition
Linda Cai, Raghuvansh R. Saxena
The enhanced competition paradigm is an attempt at bridging the gap between simple and optimal auctions. In this line of work, given an auction setting with items and bidde…
Representing All Stable Matchings by Walking a Maximal Chain
Linda Cai, Clayton Thomas
The seminal book of Gusfield and Irving [GI89] provides a compact and algorithmically useful way to represent the collection of stable matches corresponding to a given set of prefe…
The Short-Side Advantage in Random Matching Markets
Linda Cai, Clayton Thomas
A breakthrough of Ashlagi, Kanoria, and Leshno [AKL17] found that imbalance in the number of agents on either side of a random matching market has a profound effect on the market's…
Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms when Demand Queries are NP-hard
Linda Cai, Clayton Thomas, S. Matthew Weinberg
State-of-the-art posted-price mechanisms for submodular bidders with items achieve approximation guarantees of [Assadi and Singla, 2019]. Their truthfulnes…
Separators for Planar Graphs that are Almost Trees
Linda Cai, Sariel Har-Peled, Simiao Ye
We prove that a connected planar graph with vertices and edges has a vertex separator of size , and this separator can be computed in linear time.