Mark Braverman | DeepAI

DeepAI AI Chat

Featured Co-authors

Yi Zhang
258 publications
David P. Woodruff
116 publications
Tengyu Ma
97 publications
Sham M. Kakade
65 publications
Elad Hazan
65 publications
Sanjeev Arora
58 publications
Karthik Narasimhan
57 publications
Shay Moran
56 publications
Max Simchowitz
48 publications
S. Matthew Weinberg
44 publications
Xinyi Chen
29 publications

∙ 02/16/2023

Welfare Distribution in Two-sided Random Matching Markets

We study the welfare structure in two-sided large random matching market...

0 Itai Ashlagi, et al. ∙

∙ 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...

0 Mark Braverman, et al. ∙

∙ 11/17/2022

Rounding via Low Dimensional Embeddings

A regular graph G = (V,E) is an (ε,γ) small-set expander if for any set ...

0 Mark Braverman, et al. ∙

∙ 11/16/2022

Improved Monotonicity Testers via Hypercube Embeddings

We show improved monotonicity testers for the Boolean hypercube under th...

0 Mark Braverman, et al. ∙

∙ 10/03/2022

Understanding Influence Functions and Datamodels via Harmonic Analysis

Influence functions estimate effect of individual data points on predict...

8 Nikunj Saunshi, et al. ∙

∙ 08/03/2022

Empirical Characteristics of Affordable Care Act Risk Transfer Payments

Under the Affordable Care Act (ACA), insurers cannot engage in medical u...

0 Grace Guan, et al. ∙

∙ 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...

0 Mark Braverman, et al. ∙

∙ 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...

0 Mark Braverman, et al. ∙

∙ 08/17/2021

Statistically Near-Optimal Hypothesis Selection

Hypothesis Selection is a fundamental distribution learning problem wher...

4 Olivier Bousquet, et al. ∙

∙ 06/14/2021

Optimization-friendly generic mechanisms without money

The goal of this paper is to develop a generic framework for converting ...

0 Mark Braverman, et al. ∙

∙ 03/06/2021

New Separations Results for External Information

We obtain new separation results for the two-party external information ...

0 Mark Braverman, et al. ∙

∙ 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...

0 Mark Braverman, et al. ∙

∙ 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...

0 Mark Braverman, et al. ∙

∙ 09/10/2020

Tiered Random Matching Markets: Rank is Proportional to Popularity

We study the stable marriage problem in two-sided markets with randomly ...

0 Itai Ashlagi, et al. ∙

∙ 05/17/2020

The Role of Randomness and Noise in Strategic Classification

We investigate the problem of designing optimal classifiers in the strat...

6 Mark Braverman, et al. ∙

∙ 11/06/2019

The gradient complexity of linear regression

We investigate the computational complexity of several basic linear alge...

14 Mark Braverman, et al. ∙

∙ 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...

0 Mark Braverman, et al. ∙

∙ 06/12/2019

Sorted Top-k in Rounds

We consider the sorted top-k problem whose goal is to recover the top-k ...

0 Mark Braverman, et al. ∙

∙ 06/11/2019

Calibration, Entropy Rates, and Memory in Language Models

Building accurate language models that capture meaningful long-term depe...

1 Mark Braverman, et al. ∙

∙ 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...

0 Mark Braverman, et al. ∙

∙ 11/22/2018

The Price of Uncertain Priors in Source Coding

We consider the problem of one-way communication when the recipient does...

0 Mark Braverman, et al. ∙

∙ 07/13/2018

Optimal Short-Circuit Resilient Formulas

We consider fault-tolerant boolean formulas in which the output of a fau...

0 Mark Braverman, et al. ∙

∙ 11/25/2017

Selling to a No-Regret Buyer

We consider the problem of a single seller repeatedly selling a single i...

0 Mark Braverman, et al. ∙

∙ 06/27/2017

Multi-armed Bandit Problems with Strategic Arms

We study a strategic version of the multi-armed bandit problem, where ea...

0 Mark Braverman, et al. ∙

∙ 06/24/2015

Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality

We study the tradeoff between the statistical error and communication co...

0 Mark Braverman, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world