research
∙
02/16/2023
Welfare Distribution in Two-sided Random Matching Markets
We study the welfare structure in two-sided large random matching market...
share
research
∙
11/24/2022
Parallel Repetition for the GHZ Game: Exponential Decay
We show that the value of the n-fold repeated GHZ game is at most 2^-Ω(n...
research
∙
11/17/2022
Rounding via Low Dimensional Embeddings
A regular graph G = (V,E) is an (ε,γ) small-set expander if for any set ...
research
∙
11/16/2022
Improved Monotonicity Testers via Hypercube Embeddings
We show improved monotonicity testers for the Boolean hypercube under th...
research
∙
10/03/2022
Understanding Influence Functions and Datamodels via Harmonic Analysis
Influence functions estimate effect of individual data points on predict...
research
∙
08/03/2022
Empirical Characteristics of Affordable Care Act Risk Transfer Payments
Under the Affordable Care Act (ACA), insurers cannot engage in medical u...
research
∙
06/02/2022
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark
In this paper, we study max-weight stochastic matchings on online bipart...
research
∙
10/20/2021
An Invariance Principle for the Multi-slice, with Applications
Given an alphabet size m∈ℕ thought of as a constant, and k⃗ = (k_1,…,k_m...
research
∙
08/17/2021
Statistically Near-Optimal Hypothesis Selection
Hypothesis Selection is a fundamental distribution learning problem wher...
research
∙
06/14/2021
Optimization-friendly generic mechanisms without money
The goal of this paper is to develop a generic framework for converting ...
research
∙
03/06/2021
New Separations Results for External Information
We obtain new separation results for the two-party external information ...
research
∙
03/02/2021
Prior-free Dynamic Mechanism Design With Limited Liability
We study the problem of repeatedly auctioning off an item to one of k bi...
research
∙
11/08/2020
Optimal tiling of the Euclidean space using symmetric bodies
What is the least surface area of a symmetric body B whose ℤ^n translati...
research
∙
09/10/2020
Tiered Random Matching Markets: Rank is Proportional to Popularity
We study the stable marriage problem in two-sided markets with randomly ...
research
∙
05/17/2020
The Role of Randomness and Noise in Strategic Classification
We investigate the problem of designing optimal classifiers in the strat...
research
∙
11/06/2019
The gradient complexity of linear regression
We investigate the computational complexity of several basic linear alge...
research
∙
09/08/2019
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility
We study the Convex Set Disjointness (CSD) problem, where two players ha...
research
∙
06/12/2019
Sorted Top-k in Rounds
We consider the sorted top-k problem whose goal is to recover the top-k ...
research
∙
06/11/2019
Calibration, Entropy Rates, and Memory in Language Models
Building accurate language models that capture meaningful long-term depe...
research
∙
05/02/2019
Space-bounded Church-Turing thesis and computational tractability of closed systems
We report a new limitation on the ability of physical systems to perform...
research
∙
11/22/2018
The Price of Uncertain Priors in Source Coding
We consider the problem of one-way communication when the recipient does...
research
∙
07/13/2018
Optimal Short-Circuit Resilient Formulas
We consider fault-tolerant boolean formulas in which the output of a fau...
research
∙
11/25/2017
Selling to a No-Regret Buyer
We consider the problem of a single seller repeatedly selling a single i...
research
∙
06/27/2017
Multi-armed Bandit Problems with Strategic Arms
We study a strategic version of the multi-armed bandit problem, where ea...
research
∙
06/24/2015