
New Separations Results for External Information
We obtain new separation results for the twoparty external information ...
read it

Priorfree Dynamic Mechanism Design With Limited Liability
We study the problem of repeatedly auctioning off an item to one of k bi...
read it

Optimal tiling of the Euclidean space using symmetric bodies
What is the least surface area of a symmetric body B whose ℤ^n translati...
read it

Tiered Random Matching Markets: Rank is Proportional to Popularity
We study the stable marriage problem in twosided markets with randomly ...
read it

The Role of Randomness and Noise in Strategic Classification
We investigate the problem of designing optimal classifiers in the strat...
read it

The gradient complexity of linear regression
We investigate the computational complexity of several basic linear alge...
read it

Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility
We study the Convex Set Disjointness (CSD) problem, where two players ha...
read it

Sorted Topk in Rounds
We consider the sorted topk problem whose goal is to recover the topk ...
read it

Calibration, Entropy Rates, and Memory in Language Models
Building accurate language models that capture meaningful longterm depe...
read it

Spacebounded ChurchTuring thesis and computational tractability of closed systems
We report a new limitation on the ability of physical systems to perform...
read it

The Price of Uncertain Priors in Source Coding
We consider the problem of oneway communication when the recipient does...
read it

Optimal ShortCircuit Resilient Formulas
We consider faulttolerant boolean formulas in which the output of a fau...
read it

Selling to a NoRegret Buyer
We consider the problem of a single seller repeatedly selling a single i...
read it

Multiarmed Bandit Problems with Strategic Arms
We study a strategic version of the multiarmed bandit problem, where ea...
read it

Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality
We study the tradeoff between the statistical error and communication co...
read it
Mark Braverman
is this you? claim profile
Professor at Princeton University, Assistant Professor at Princeton University from 20112013, Assistant Professor at University of Toronto from 20102012, Cofounder & Director at Zetawire Inc. from 20072010, Postdoctoral Researcher at Microsoft from 20082010