Showing 1–50 of 62 results for author: Braverman, M

A New Information Complexity Measure for Multi-pass Streaming with Applications

Authors: Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang

Abstract: We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams. In the coin problem, one sees a stream of $n$ i.i.d. uniform bits and one would like to compute the majority with constant advantage. We show that any constant pass algorithm must use $Ω(\log n)$ bits of memory, significantly extending an earlie… ▽ More We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams. In the coin problem, one sees a stream of $n$ i.i.d. uniform bits and one would like to compute the majority with constant advantage. We show that any constant pass algorithm must use $Ω(\log n)$ bits of memory, significantly extending an earlier $Ω(\log n)$ bit lower bound for single-pass algorithms of Braverman-Garg-Woodruff (FOCS, 2020). This also gives the first $Ω(\log n)$ bit lower bound for the problem of approximating a counter up to a constant factor in worst-case turnstile streams for more than one pass. In the needle problem, one either sees a stream of $n$ i.i.d. uniform samples from a domain $[t]$, or there is a randomly chosen needle $α\in[t]$ for which each item independently is chosen to equal $α$ with probability $p$, and is otherwise uniformly random in $[t]$. The problem of distinguishing these two cases is central to understanding the space complexity of the frequency moment estimation problem in random order streams. We show tight multi-pass space bounds for this problem for every $p < 1/\sqrt{n \log^3 n}$, resolving an open question of Lovett and Zhang (FOCS, 2023); even for $1$-pass our bounds are new. To show optimality, we improve both lower and upper bounds from existing results. Our information complexity framework significantly extends the toolkit for proving multi-pass streaming lower bounds, and we give a wide number of additional streaming applications of our lower bound techniques, including multi-pass lower bounds for $\ell_p$-norm estimation, $\ell_p$-point query and heavy hitters, and compressed sensing problems. △ Less

Submitted 29 March, 2024; originally announced March 2024.

Comments: To appear in STOC 2024

Parallel Repetition of k-Player Projection Games

Authors: Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer

Abstract: We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection games with value less than 1. We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection games with value less than 1. △ Less

Submitted 7 December, 2023; originally announced December 2023.

Comments: 17 pages

Welfare Distribution in Two-sided Random Matching Markets

Authors: Itai Ashlagi, Mark Braverman, Geng Zhao

Abstract: We study the welfare structure in two-sided large random matching markets. In the model, each agent has a latent personal score for every agent on the other side of the market and her preferences follow a logit model based on these scores. Under a contiguity condition, we provide a tight description of stable outcomes. First, we identify an intrinsic fitness for each agent that represents her rela… ▽ More We study the welfare structure in two-sided large random matching markets. In the model, each agent has a latent personal score for every agent on the other side of the market and her preferences follow a logit model based on these scores. Under a contiguity condition, we provide a tight description of stable outcomes. First, we identify an intrinsic fitness for each agent that represents her relative competitiveness in the market, independent of the realized stable outcome. The intrinsic fitness values correspond to scaling coefficients needed to make a latent mutual matrix bi-stochastic, where the latent scores can be interpreted as a-priori probabilities of a pair being matched. Second, in every stable (or even approximately stable) matching, the welfare or the ranks of the agents on each side of the market, when scaled by their intrinsic fitness, have an approximately exponential empirical distribution. Moreover, the average welfare of agents on one side of the market is sufficient to determine the average on the other side. Overall, each agent's welfare is determined by a global parameter, her intrinsic fitness, and an extrinsic factor with exponential distribution across the population. △ Less

Submitted 16 February, 2023; originally announced February 2023.

Parallel Repetition for the GHZ Game: Exponential Decay

Authors: Mark Braverman, Subhash Khot, Dor Minzer

Abstract: We show that the value of the $n$-fold repeated GHZ game is at most $2^{-Ω(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics. We show that the value of the $n$-fold repeated GHZ game is at most $2^{-Ω(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics. △ Less

Submitted 24 November, 2022; originally announced November 2022.

Rounding via Low Dimensional Embeddings

Authors: Mark Braverman, Dor Minzer

Abstract: A regular graph $G = (V,E)$ is an $(\varepsilon,γ)$ small-set expander if for any set of vertices of fractional size at most $\varepsilon$, at least $γ$ of the edges that are adjacent to it go outside. In this paper, we give a unified approach to several known complexity-theoretic results on small-set expanders. In particular, we show: 1. Max-Cut: we show that if a regular graph $G = (V,E)$ is a… ▽ More A regular graph $G = (V,E)$ is an $(\varepsilon,γ)$ small-set expander if for any set of vertices of fractional size at most $\varepsilon$, at least $γ$ of the edges that are adjacent to it go outside. In this paper, we give a unified approach to several known complexity-theoretic results on small-set expanders. In particular, we show: 1. Max-Cut: we show that if a regular graph $G = (V,E)$ is an $(\varepsilon,γ)$ small-set expander that contains a cut of fractional size at least $1-δ$, then one can find in $G$ a cut of fractional size at least $1-O\left(\fracδ{\varepsilonγ^6}\right)$ in polynomial time. 2. Improved spectral partitioning, Cheeger's inequality and the parallel repetition theorem over small-set expanders. The general form of each one of these results involves square-root loss that comes from certain rounding procedure, and we show how this can be avoided over small set expanders. Our main idea is to project a high dimensional vector solution into a low-dimensional space while roughly maintaining $\ell_2^2$ distances, and then perform a pre-processing step using low-dimensional geometry and the properties of $\ell_2^2$ distances over it. This pre-processing leverages the small-set expansion property of the graph to transform a vector valued solution to a different vector valued solution with additional structural properties, which give rise to more efficient integral-solution rounding schemes. △ Less

Submitted 17 November, 2022; originally announced November 2022.

Improved Monotonicity Testers via Hypercube Embeddings

Authors: Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer

Abstract: We show improved monotonicity testers for the Boolean hypercube under the $p$-biased measure, as well as over the hypergrid $[m]^n$. Our results are: 1. For any $p\in (0,1)$, for the $p$-biased hypercube we show a non-adaptive tester that makes $\tilde{O}(\sqrt{n}/\varepsilon^2)$ queries, accepts monotone functions with probability $1$ and rejects functions that are $\varepsilon$-far from monoto… ▽ More We show improved monotonicity testers for the Boolean hypercube under the $p$-biased measure, as well as over the hypergrid $[m]^n$. Our results are: 1. For any $p\in (0,1)$, for the $p$-biased hypercube we show a non-adaptive tester that makes $\tilde{O}(\sqrt{n}/\varepsilon^2)$ queries, accepts monotone functions with probability $1$ and rejects functions that are $\varepsilon$-far from monotone with probability at least $2/3$. 2. For all $m\in\mathbb{N}$, we show an $\tilde{O}(\sqrt{n}m^3/\varepsilon^2)$ query monotonicity tester over $[m]^n$. We also establish corresponding directed isoperimetric inequalities in these domains. Previously, the best known tester due to Black, Chakrabarty and Seshadhri had $Ω(n^{5/6})$ query complexity. Our results are optimal up to poly-logarithmic factors and the dependency on $m$. Our proof uses a notion of monotone embeddings of measures into the Boolean hypercube that can be used to reduce the problem of monotonicity testing over an arbitrary product domains to the Boolean cube. The embedding maps a function over a product domain of dimension $n$ into a function over a Boolean cube of a larger dimension $n'$, while preserving its distance from being monotone; an embedding is considered efficient if $n'$ is not much larger than $n$, and we show how to construct efficient embeddings in the above mentioned settings. △ Less

Submitted 16 November, 2022; originally announced November 2022.

Understanding Influence Functions and Datamodels via Harmonic Analysis

Authors: Nikunj Saunshi, Arushi Gupta, Mark Braverman, Sanjeev Arora

Abstract: Influence functions estimate effect of individual data points on predictions of the model on test data and were adapted to deep learning in Koh and Liang [2017]. They have been used for detecting data poisoning, detecting helpful and harmful examples, influence of groups of datapoints, etc. Recently, Ilyas et al. [2022] introduced a linear regression method they termed datamodels to predict the ef… ▽ More Influence functions estimate effect of individual data points on predictions of the model on test data and were adapted to deep learning in Koh and Liang [2017]. They have been used for detecting data poisoning, detecting helpful and harmful examples, influence of groups of datapoints, etc. Recently, Ilyas et al. [2022] introduced a linear regression method they termed datamodels to predict the effect of training points on outputs on test data. The current paper seeks to provide a better theoretical understanding of such interesting empirical phenomena. The primary tool is harmonic analysis and the idea of noise stability. Contributions include: (a) Exact characterization of the learnt datamodel in terms of Fourier coefficients. (b) An efficient method to estimate the residual error and quality of the optimum linear datamodel without having to train the datamodel. (c) New insights into when influences of groups of datapoints may or may not add up linearly. △ Less

Submitted 3 October, 2022; originally announced October 2022.

Empirical Characteristics of Affordable Care Act Risk Transfer Payments

Authors: Grace Guan, Mark Braverman

Abstract: Under the Affordable Care Act (ACA), insurers cannot engage in medical underwriting and thus face perverse incentives to engage in risk selection and discourage low-value patients from enrolling in their plans. One ACA program intended to reduce the effects of risk selection is risk adjustment. Under a risk adjustment program, insurers with less healthy enrollees receive risk transfer payments fro… ▽ More Under the Affordable Care Act (ACA), insurers cannot engage in medical underwriting and thus face perverse incentives to engage in risk selection and discourage low-value patients from enrolling in their plans. One ACA program intended to reduce the effects of risk selection is risk adjustment. Under a risk adjustment program, insurers with less healthy enrollees receive risk transfer payments from insurers with healthier enrollees. Our goal is to understand the elements driving risk transfers. First, the distribution of risk transfers should be based on random health shocks, which are unpredictable events that negatively affect health status. Second, risk transfers could be influenced by factors unique to each insurer, such as certain plans attracting certain patients, the extent to which carriers engage in risk selection, and the degree of upcoding. We create a publicly available dataset using Centers for Medicare and Medicaid Services data that includes insurer risk transfer payments, costs, and premiums for the 2014-2017 benefit years. Using this dataset, we find that the empirical distribution of risk transfer payments is not consistent with the lack of risk selection as measured by the ACA risk transfer formula. Over all states included in our dataset, at least 60% of the volume of transfers cannot be accounted for by a purely normal model. Because we find that it is very unlikely that risk transfer payments are caused solely by random shocks that reflect health events of the population, our work raises important questions about the causes of heterogeneity in risk transfers. △ Less

Submitted 3 August, 2022; originally announced August 2022.

Comments: 33 pages, 2 figures

Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark

Authors: Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett

Abstract: In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by Papadimitriou, Pollner, Saberi, and Wajc [EC'21]. In the vertex arrival version of the problem, the goal is to find an approximate max-weight match… ▽ More In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by Papadimitriou, Pollner, Saberi, and Wajc [EC'21]. In the vertex arrival version of the problem, the goal is to find an approximate max-weight matching of a given bipartite graph when the vertices in one part of the graph arrive online in a fixed order with independent chances of failure. Whenever a vertex arrives we should decide, irrevocably, whether to match it with one of its unmatched neighbors or leave it unmatched forever. There has been a long line of work designing approximation algorithms for different variants of this problem with respect to the offline benchmark (prophet). Papadimitriou et al., however, propose the alternative online benchmark and show that considering this new benchmark allows them to improve the 0.5 approximation ratio, which is the best ratio achievable with respect to the offline benchmark. They provide a 0.51-approximation algorithm which was later improved to 0.526 by Saberi and Wajc [ICALP'21]. The main contribution of this paper is designing a simple algorithm with a significantly improved approximation ratio of (1-1/e) for this problem. We also consider the edge arrival version in which, instead of vertices, edges of the graph arrive in an online fashion with independent chances of failure. Designing approximation algorithms for this problem has also been studied extensively with the best approximation ratio being 0.337 with respect to the offline benchmark. This paper, however, is the first to consider the online benchmark for the edge arrival version of the problem. For this problem, we provide a simple algorithm with an approximation ratio of 0.5 with respect to the online benchmark. △ Less

Submitted 2 June, 2022; originally announced June 2022.

An Invariance Principle for the Multi-slice, with Applications

Authors: Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer

Abstract: Given an alphabet size $m\in\mathbb{N}$ thought of as a constant, and $\vec{k} = (k_1,\ldots,k_m)$ whose entries sum of up $n$, the $\vec{k}$-multi-slice is the set of vectors $x\in [m]^n$ in which each symbol $i\in [m]$ appears precisely $k_i$ times. We show an invariance principle for low-degree functions over the multi-slice, to functions over the product space $([m]^n,μ^n)$ in which… ▽ More Given an alphabet size $m\in\mathbb{N}$ thought of as a constant, and $\vec{k} = (k_1,\ldots,k_m)$ whose entries sum of up $n$, the $\vec{k}$-multi-slice is the set of vectors $x\in [m]^n$ in which each symbol $i\in [m]$ appears precisely $k_i$ times. We show an invariance principle for low-degree functions over the multi-slice, to functions over the product space $([m]^n,μ^n)$ in which $μ(i) = k_i/n$. This answers a question raised by Filmus et al. As applications of the invariance principle, we show: 1. An analogue of the "dictatorship test implies computational hardness" paradigm for problems with perfect completeness, for a certain class of dictatorship tests. Our computational hardness is proved assuming a recent strengthening of the Unique-Games Conjecture, called the Rich $2$-to-$1$ Games Conjecture. Using this analogue, we show that assuming the Rich $2$-to-$1$ Games Conjecture, (a) there is an $r$-ary CSP $\mathcal{P}_r$ for which it is NP-hard to distinguish satisfiable instances of the CSP and instances that are at most $\frac{2r+1}{2^r} + o(1)$ satisfiable, and (b) hardness of distinguishing $3$-colorable graphs, and graphs that do not contain an independent set of size $o(1)$. 2. A reduction of the problem of studying expectations of products of functions on the multi-slice to studying expectations of products of functions on correlated, product spaces. In particular, we are able to deduce analogues of the Gaussian bounds from \cite{MosselGaussian} for the multi-slice. 3. In a companion paper, we show further applications of our invariance principle in extremal combinatorics, and more specifically to proving removal lemmas of a wide family of hypergraphs $H$ called $ζ$-forests, which is a natural extension of the well-studied case of matchings. △ Less

Submitted 20 October, 2021; originally announced October 2021.

Statistically Near-Optimal Hypothesis Selection

Authors: Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol, Shay Moran

Abstract: Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class $Q=\{q_1,\ldots, q_n\}$ of distributions, and a sampling access to an unknown target distribution $p$, the goal is to output a distribution $q$ such that $\mathsf{TV}(p,q)$ is close to $opt$, where $opt = \min_i\{\mathsf{TV}(p,q_i)\}$ and $\mathsf{TV}(\cdot, \cdot)$ denotes the total-variation distan… ▽ More Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class $Q=\{q_1,\ldots, q_n\}$ of distributions, and a sampling access to an unknown target distribution $p$, the goal is to output a distribution $q$ such that $\mathsf{TV}(p,q)$ is close to $opt$, where $opt = \min_i\{\mathsf{TV}(p,q_i)\}$ and $\mathsf{TV}(\cdot, \cdot)$ denotes the total-variation distance. Despite the fact that this problem has been studied since the 19th century, its complexity in terms of basic resources, such as number of samples and approximation guarantees, remains unsettled (this is discussed, e.g., in the charming book by Devroye and Lugosi `00). This is in stark contrast with other (younger) learning settings, such as PAC learning, for which these complexities are well understood. We derive an optimal $2$-approximation learning strategy for the Hypothesis Selection problem, outputting $q$ such that $\mathsf{TV}(p,q) \leq2 \cdot opt + \eps$, with a (nearly) optimal sample complexity of~$\tilde O(\log n/ε^2)$. This is the first algorithm that simultaneously achieves the best approximation factor and sample complexity: previously, Bousquet, Kane, and Moran (COLT `19) gave a learner achieving the optimal $2$-approximation, but with an exponentially worse sample complexity of $\tilde O(\sqrt{n}/ε^{2.5})$, and Yatracos~(Annals of Statistics `85) gave a learner with optimal sample complexity of $O(\log n /ε^2)$ but with a sub-optimal approximation factor of $3$. △ Less

Submitted 17 August, 2021; originally announced August 2021.

Comments: Accepted to FOCS 2021

Optimization-friendly generic mechanisms without money

Authors: Mark Braverman

Abstract: The goal of this paper is to develop a generic framework for converting modern optimization algorithms into mechanisms where inputs come from self-interested agents. We focus on aggregating preferences from $n$ players in a context without money. Special cases of this setting include voting, allocation of items by lottery, and matching. Our key technical contribution is a new meta-algorithm we cal… ▽ More The goal of this paper is to develop a generic framework for converting modern optimization algorithms into mechanisms where inputs come from self-interested agents. We focus on aggregating preferences from $n$ players in a context without money. Special cases of this setting include voting, allocation of items by lottery, and matching. Our key technical contribution is a new meta-algorithm we call \apex (Adaptive Pricing Equalizing Externalities). The framework is sufficiently general to be combined with any optimization algorithm that is based on local search. We outline an agenda for studying the algorithm's properties and its applications. As a special case of applying the framework to the problem of one-sided assignment with lotteries, we obtain a strengthening of the 1979 result by Hylland and Zeckhauser on allocation via a competitive equilibrium from equal incomes (CEEI). The [HZ79] result posits that there is a (fractional) allocation and a set of item prices such that the allocation is a competitive equilibrium given prices. We further show that there is always a reweighing of the players' utility values such that running unit-demand VCG with reweighed utilities leads to a HZ-equilibrium prices. Interestingly, not all HZ competitive equilibria come from VCG prices. As part of our proof, we re-prove the [HZ79] result using only Brouwer's fixed point theorem (and not the more general Kakutani's theorem). This may be of independent interest. △ Less

Submitted 14 June, 2021; originally announced June 2021.

MSC Class: 91A68 ACM Class: J.4

New Separations Results for External Information

Authors: Mark Braverman, Dor Minzer

Abstract: We obtain new separation results for the two-party external information complexity of boolean functions. The external information complexity of a function $f(x,y)$ is the minimum amount of information a two-party protocol computing $f$ must reveal to an outside observer about the input. We obtain the following results: 1. We prove an exponential separation between external and internal informati… ▽ More We obtain new separation results for the two-party external information complexity of boolean functions. The external information complexity of a function $f(x,y)$ is the minimum amount of information a two-party protocol computing $f$ must reveal to an outside observer about the input. We obtain the following results: 1. We prove an exponential separation between external and internal information complexity, which is the best possible; previously no separation was known. 2. We prove a near-quadratic separation between amortized zero-error communication complexity and external information complexity for total functions, disproving a conjecture of \cite{Bravermansurvey}. 3. We prove a matching upper showing that our separation result is tight. △ Less

Submitted 6 March, 2021; originally announced March 2021.

Prior-free Dynamic Mechanism Design With Limited Liability

Authors: Mark Braverman, Jon Schneider, S. Matthew Weinberg

Abstract: We study the problem of repeatedly auctioning off an item to one of $k$ bidders where: a) bidders have a per-round individual rationality constraint, b) bidders may leave the mechanism at any point, and c) the bidders' valuations are adversarially chosen (the prior-free setting). Without these constraints, the auctioneer can run a second-price auction to "sell the business" and receive the second… ▽ More We study the problem of repeatedly auctioning off an item to one of $k$ bidders where: a) bidders have a per-round individual rationality constraint, b) bidders may leave the mechanism at any point, and c) the bidders' valuations are adversarially chosen (the prior-free setting). Without these constraints, the auctioneer can run a second-price auction to "sell the business" and receive the second highest total value for the entire stream of items. We show that under these constraints, the auctioneer can attain a constant fraction of the "sell the business" benchmark, but no more than $2/e$ of this benchmark. In the course of doing so, we design mechanisms for a single bidder problem of independent interest: how should you repeatedly sell an item to a (per-round IR) buyer with adversarial valuations if you know their total value over all rounds is $V$ but not how their value changes over time? We demonstrate a mechanism that achieves revenue $V/e$ and show that this is tight. △ Less

Submitted 2 March, 2021; originally announced March 2021.

Optimal tiling of the Euclidean space using symmetric bodies

Authors: Mark Braverman, Dor Minzer

Abstract: What is the least surface area of a symmetric body $B$ whose $\mathbb{Z}^n$ translations tile $\mathbb{R}^n$? Since any such body must have volume $1$, the isoperimetric inequality implies that its surface area must be at least $Ω(\sqrt{n})$. Remarkably, Kindler et al.\ showed that for general bodies $B$ this is tight, i.e.\ that there is a tiling body of $\mathbb{R}^n$ whose surface area is… ▽ More What is the least surface area of a symmetric body $B$ whose $\mathbb{Z}^n$ translations tile $\mathbb{R}^n$? Since any such body must have volume $1$, the isoperimetric inequality implies that its surface area must be at least $Ω(\sqrt{n})$. Remarkably, Kindler et al.\ showed that for general bodies $B$ this is tight, i.e.\ that there is a tiling body of $\mathbb{R}^n$ whose surface area is $O(\sqrt{n})$. In theoretical computer science, the tiling problem is intimately to the study of parallel repetition theorems (which are an important component in PCPs), and more specifically in the question of whether a "strong version" of the parallel repetition theorem holds. Raz showed, using the odd cycle game, that strong parallel repetition fails in general, and subsequently these ideas were used in order to construct non-trivial tilings of $\mathbb{R}^n$. In this paper, motivated by the study of a symmetric parallel repetition, we consider the symmetric variant of the tiling problem in $\mathbb{R}^n$. We show that any symmetric body that tiles $\mathbb{R}^n$ must have surface area at least $Ω(n/\sqrt{\log n})$, and that this bound is tight, i.e.\ that there is a symmetric tiling body of $\mathbb{R}^n$ with surface area $O(n/\sqrt{\log n})$. We also give matching bounds for the value of the symmetric parallel repetition of Raz's odd cycle game. Our result suggests that while strong parallel repetition fails in general, there may be important special cases where it still applies. △ Less

Submitted 8 November, 2020; originally announced November 2020.

Tiered Random Matching Markets: Rank is Proportional to Popularity

Authors: Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, Geng Zhao

Abstract: We study the stable marriage problem in two-sided markets with randomly generated preferences. We consider agents on each side divided into a constant number of "soft tiers", which intuitively indicate the quality of the agent. Specifically, every agent within a tier has the same public score, and agents on each side have preferences independently generated proportionally to the public scores of t… ▽ More We study the stable marriage problem in two-sided markets with randomly generated preferences. We consider agents on each side divided into a constant number of "soft tiers", which intuitively indicate the quality of the agent. Specifically, every agent within a tier has the same public score, and agents on each side have preferences independently generated proportionally to the public scores of the other side. We compute the expected average rank which agents in each tier have for their partners in the men-optimal stable matching, and prove concentration results for the average rank in asymptotically large markets. Furthermore, we show that despite having a significant effect on ranks, public scores do not strongly influence the probability of an agent matching to a given tier of the other side. This generalizes results of [Pittel 1989] which correspond to uniform preferences. The results quantitatively demonstrate the effect of competition due to the heterogeneous attractiveness of agents in the market, and we give the first explicit calculations of rank beyond uniform markets. △ Less

Submitted 12 January, 2021; v1 submitted 10 September, 2020; originally announced September 2020.

The Role of Randomness and Noise in Strategic Classification

Authors: Mark Braverman, Sumegha Garg

Abstract: We investigate the problem of designing optimal classifiers in the strategic classification setting, where the classification is part of a game in which players can modify their features to attain a favorable classification outcome (while incurring some cost). Previously, the problem has been considered from a learning-theoretic perspective and from the algorithmic fairness perspective. Our main c… ▽ More We investigate the problem of designing optimal classifiers in the strategic classification setting, where the classification is part of a game in which players can modify their features to attain a favorable classification outcome (while incurring some cost). Previously, the problem has been considered from a learning-theoretic perspective and from the algorithmic fairness perspective. Our main contributions include 1. Showing that if the objective is to maximize the efficiency of the classification process (defined as the accuracy of the outcome minus the sunk cost of the qualified players manipulating their features to gain a better outcome), then using randomized classifiers (that is, ones where the probability of a given feature vector to be accepted by the classifier is strictly between 0 and 1) is necessary. 2. Showing that in many natural cases, the imposed optimal solution (in terms of efficiency) has the structure where players never change their feature vectors (the randomized classifier is structured in a way, such that the gain in the probability of being classified as a 1 does not justify the expense of changing one's features). 3. Observing that the randomized classification is not a stable best-response from the classifier's viewpoint, and that the classifier doesn't benefit from randomized classifiers without creating instability in the system. 4. Showing that in some cases, a noisier signal leads to better equilibria outcomes -- improving both accuracy and fairness when more than one subpopulation with different feature adjustment costs are involved. This is interesting from a policy perspective, since it is hard to force institutions to stick to a particular randomized classification strategy (especially in a context of a market with multiple classifiers), but it is possible to alter the information environment to make the feature signals inherently noisier. △ Less

Submitted 17 May, 2020; originally announced May 2020.

Comments: 22 pages. Appeared in FORC, 2020

The gradient complexity of linear regression

Authors: Mark Braverman, Elad Hazan, Max Simchowitz, Blake Woodworth

Abstract: We investigate the computational complexity of several basic linear algebra primitives, including largest eigenvector computation and linear regression, in the computational model that allows access to the data via a matrix-vector product oracle. We show that for polynomial accuracy, $Θ(d)$ calls to the oracle are necessary and sufficient even for a randomized algorithm. Our lower bound is based… ▽ More We investigate the computational complexity of several basic linear algebra primitives, including largest eigenvector computation and linear regression, in the computational model that allows access to the data via a matrix-vector product oracle. We show that for polynomial accuracy, $Θ(d)$ calls to the oracle are necessary and sufficient even for a randomized algorithm. Our lower bound is based on a reduction to estimating the least eigenvalue of a random Wishart matrix. This simple distribution enables a concise proof, leveraging a few key properties of the random Wishart ensemble. △ Less

Submitted 23 May, 2021; v1 submitted 6 November, 2019; originally announced November 2019.

Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility

Authors: Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena

Abstract: We study the Convex Set Disjointness (CSD) problem, where two players have input sets taken from an arbitrary fixed domain~$U\subseteq \mathbb{R}^d$ of size $\lvert U\rvert = n$. Their mutual goal is to decide using minimum communication whether the convex hulls of their sets intersect (equivalently, whether their sets can be separated by a hyperplane). Different forms of this problem naturally… ▽ More We study the Convex Set Disjointness (CSD) problem, where two players have input sets taken from an arbitrary fixed domain~$U\subseteq \mathbb{R}^d$ of size $\lvert U\rvert = n$. Their mutual goal is to decide using minimum communication whether the convex hulls of their sets intersect (equivalently, whether their sets can be separated by a hyperplane). Different forms of this problem naturally arise in distributed learning and optimization: it is equivalent to {\em Distributed Linear Program (LP) Feasibility} -- a basic task in distributed optimization, and it is tightly linked to {\it Distributed Learning of Halfdpaces in $\mathbb{R}^d$}. In {communication complexity theory}, CSD can be viewed as a geometric interpolation between the classical problems of {Set Disjointness} (when~$d\geq n-1$) and {Greater-Than} (when $d=1$). We establish a nearly tight bound of $\tilde Θ(d\log n)$ on the communication complexity of learning halfspaces in $\mathbb{R}^d$. For Convex Set Disjointness (and the equivalent task of distributed LP feasibility) we derive upper and lower bounds of $\tilde O(d^2\log n)$ and~$Ω(d\log n)$. These results improve upon several previous works in distributed learning and optimization. Unlike typical works in communication complexity, the main technical contribution of this work lies in the upper bounds. In particular, our protocols are based on a {\it Container Lemma for Halfspaces} and on two variants of {\it Carathéodory's Theorem}, which may be of independent interest. These geometric statements are used by our protocols to provide a compressed summary of the players' input. △ Less

Submitted 8 September, 2019; originally announced September 2019.

Comments: 37 pages, 8 figures

Calibration, Entropy Rates, and Memory in Language Models

Authors: Mark Braverman, Xinyi Chen, Sham M. Kakade, Karthik Narasimhan, Cyril Zhang, Yi Zhang

Abstract: Building accurate language models that capture meaningful long-term dependencies is a core challenge in natural language processing. Towards this end, we present a calibration-based approach to measure long-term discrepancies between a generative sequence model and the true distribution, and use these discrepancies to improve the model. Empirically, we show that state-of-the-art language models, i… ▽ More Building accurate language models that capture meaningful long-term dependencies is a core challenge in natural language processing. Towards this end, we present a calibration-based approach to measure long-term discrepancies between a generative sequence model and the true distribution, and use these discrepancies to improve the model. Empirically, we show that state-of-the-art language models, including LSTMs and Transformers, are \emph{miscalibrated}: the entropy rates of their generations drift dramatically upward over time. We then provide provable methods to mitigate this phenomenon. Furthermore, we show how this calibration-based approach can also be used to measure the amount of memory that language models use for prediction. △ Less

Submitted 11 June, 2019; originally announced June 2019.

Sorted Top-k in Rounds

Authors: Mark Braverman, Jieming Mao, Yuval Peres

Abstract: We consider the sorted top-$k$ problem whose goal is to recover the top-$k$ items with the correct order out of $n$ items using pairwise comparisons. In many applications, multiple rounds of interaction can be costly. We restrict our attention to algorithms with a constant number of rounds $r$ and try to minimize the sample complexity, i.e. the number of comparisons. When the comparisons are noi… ▽ More We consider the sorted top-$k$ problem whose goal is to recover the top-$k$ items with the correct order out of $n$ items using pairwise comparisons. In many applications, multiple rounds of interaction can be costly. We restrict our attention to algorithms with a constant number of rounds $r$ and try to minimize the sample complexity, i.e. the number of comparisons. When the comparisons are noiseless, we characterize how the optimal sample complexity depends on the number of rounds (up to a polylogarithmic factor for general $r$ and up to a constant factor for $r=1$ or 2). In particular, the sample complexity is $Θ(n^2)$ for $r=1$, $Θ(n\sqrt{k} + n^{4/3})$ for $r=2$ and $\tildeΘ\left(n^{2/r} k^{(r-1)/r} + n\right)$ for $r \geq 3$. We extend our results of sorted top-$k$ to the noisy case where each comparison is correct with probability $2/3$. When $r=1$ or 2, we show that the sample complexity gets an extra $Θ(\log(k))$ factor when we transition from the noiseless case to the noisy case. We also prove new results for top-$k$ and sorting in the noisy case. We believe our techniques can be generally useful for understanding the trade-off between round complexities and sample complexities of rank aggregation problems. △ Less

Submitted 12 June, 2019; originally announced June 2019.

Space-bounded Church-Turing thesis and computational tractability of closed systems

Authors: Mark Braverman, Cristobal Rojas, Jonathan Schneider

Abstract: We report a new limitation on the ability of physical systems to perform computation -- one that is based on generalizing the notion of memory, or storage space, available to the system to perform the computation. Roughly, we define memory as the maximal amount of information that the evolving system can carry from one instant to the next. We show that memory is a limiting factor in computation ev… ▽ More We report a new limitation on the ability of physical systems to perform computation -- one that is based on generalizing the notion of memory, or storage space, available to the system to perform the computation. Roughly, we define memory as the maximal amount of information that the evolving system can carry from one instant to the next. We show that memory is a limiting factor in computation even in lieu of any time limitations on the evolving system - such as when considering its equilibrium regime. We call this limitation the Space-Bounded Church Turing Thesis (SBCT). The SBCT is supported by a Simulation Assertion (SA), which states that predicting the long-term behavior of bounded-memory systems is computationally tractable. In particular, one corollary of SA is an explicit bound on the computational hardness of the long-term behavior of a discrete-time finite-dimensional dynamical system that is affected by noise. We prove such a bound explicitly. △ Less

Submitted 2 May, 2019; originally announced May 2019.

Comments: 6 pages

MSC Class: 68Q05; 37C40

Journal ref: Physical Review Letters. 115, 098701. August 2015

The Price of Uncertain Priors in Source Coding

Authors: Mark Braverman, Brendan Juba

Abstract: We consider the problem of one-way communication when the recipient does not know exactly the distribution that the messages are drawn from, but has a "prior" distribution that is known to be close to the source distribution, a problem first considered by Juba et al. We consider the question of how much longer the messages need to be in order to cope with the uncertainty about the receiver's prior… ▽ More We consider the problem of one-way communication when the recipient does not know exactly the distribution that the messages are drawn from, but has a "prior" distribution that is known to be close to the source distribution, a problem first considered by Juba et al. We consider the question of how much longer the messages need to be in order to cope with the uncertainty about the receiver's prior and the source distribution, respectively, as compared to the standard source coding problem. We consider two variants of this uncertain priors problem: the original setting of Juba et al. in which the receiver is required to correctly recover the message with probability 1, and a setting introduced by Haramaty and Sudan, in which the receiver is permitted to fail with some probability $ε$. In both settings, we obtain lower bounds that are tight up to logarithmically smaller terms. In the latter setting, we furthermore present a variant of the coding scheme of Juba et al. with an overhead of $\logα+\log 1/ε+1$ bits, thus also establishing the nearly tight upper bound. △ Less

Submitted 21 November, 2018; originally announced November 2018.

Comments: To appear in IEEE Transactions on Information Theory

Optimal Short-Circuit Resilient Formulas

Authors: Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew

Abstract: We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate's inputs. A recent result by Kalai et al. (FOCS 2012) converts any boolean formula into a resilient formula of polynomial size that works correctly if less than a fraction $1/6$ of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and sho… ▽ More We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate's inputs. A recent result by Kalai et al. (FOCS 2012) converts any boolean formula into a resilient formula of polynomial size that works correctly if less than a fraction $1/6$ of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any boolean formula against a fraction $1/5$ of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in size. Towards our results, we consider interactive coding schemes when noiseless feedback is present; these produce resilient boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists up to a fraction $1/5$ of corrupted transmissions in each direction of the interactive channel. We further show that such a level of noise is maximal for coding schemes with sub-exponential blowup in communication. Our coding scheme takes a surprising inspiration from Blockchain technology. △ Less

Submitted 3 August, 2022; v1 submitted 13 July, 2018; originally announced July 2018.

Comments: The second version corrects an error in the theorems of Section 3. Accepted to JACM

Selling to a No-Regret Buyer

Authors: Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg

Abstract: We consider the problem of a single seller repeatedly selling a single item to a single buyer (specifically, the buyer has a value drawn fresh from known distribution $D$ in every round). Prior work assumes that the buyer is fully rational and will perfectly reason about how their bids today affect the seller's decisions tomorrow. In this work we initiate a different direction: the buyer simply ru… ▽ More We consider the problem of a single seller repeatedly selling a single item to a single buyer (specifically, the buyer has a value drawn fresh from known distribution $D$ in every round). Prior work assumes that the buyer is fully rational and will perfectly reason about how their bids today affect the seller's decisions tomorrow. In this work we initiate a different direction: the buyer simply runs a no-regret learning algorithm over possible bids. We provide a fairly complete characterization of optimal auctions for the seller in this domain. Specifically: - If the buyer bids according to EXP3 (or any "mean-based" learning algorithm), then the seller can extract expected revenue arbitrarily close to the expected welfare. This auction is independent of the buyer's valuation $D$, but somewhat unnatural as it is sometimes in the buyer's interest to overbid. - There exists a learning algorithm $\mathcal{A}$ such that if the buyer bids according to $\mathcal{A}$ then the optimal strategy for the seller is simply to post the Myerson reserve for $D$ every round. - If the buyer bids according to EXP3 (or any "mean-based" learning algorithm), but the seller is restricted to "natural" auction formats where overbidding is dominated (e.g. Generalized First-Price or Generalized Second-Price), then the optimal strategy for the seller is a pay-your-bid format with decreasing reserves over time. Moreover, the seller's optimal achievable revenue is characterized by a linear program, and can be unboundedly better than the best truthful auction yet simultaneously unboundedly worse than the expected welfare. △ Less

Submitted 24 November, 2017; originally announced November 2017.

Multi-armed Bandit Problems with Strategic Arms

Authors: Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg

Abstract: We study a strategic version of the multi-armed bandit problem, where each arm is an individual strategic agent and we, the principal, pull one arm each round. When pulled, the arm receives some private reward $v_a$ and can choose an amount $x_a$ to pass on to the principal (keeping $v_a-x_a$ for itself). All non-pulled arms get reward $0$. Each strategic arm tries to maximize its own utility over… ▽ More We study a strategic version of the multi-armed bandit problem, where each arm is an individual strategic agent and we, the principal, pull one arm each round. When pulled, the arm receives some private reward $v_a$ and can choose an amount $x_a$ to pass on to the principal (keeping $v_a-x_a$ for itself). All non-pulled arms get reward $0$. Each strategic arm tries to maximize its own utility over the course of $T$ rounds. Our goal is to design an algorithm for the principal incentivizing these arms to pass on as much of their private rewards as possible. When private rewards are stochastically drawn each round ($v_a^t \leftarrow D_a$), we show that: - Algorithms that perform well in the classic adversarial multi-armed bandit setting necessarily perform poorly: For all algorithms that guarantee low regret in an adversarial setting, there exist distributions $D_1,\ldots,D_k$ and an approximate Nash equilibrium for the arms where the principal receives reward $o(T)$. - Still, there exists an algorithm for the principal that induces a game among the arms where each arm has a dominant strategy. When each arm plays its dominant strategy, the principal sees expected reward $μ'T - o(T)$, where $μ'$ is the second-largest of the means $\mathbb{E}[D_{a}]$. This algorithm maintains its guarantee if the arms are non-strategic ($x_a = v_a$), and also if there is a mix of strategic and non-strategic arms. △ Less

Submitted 27 June, 2017; originally announced June 2017.

On Simultaneous Two-player Combinatorial Auctions

Authors: Mark Braverman, Jieming Mao, S. Matthew Weinberg

Abstract: We consider the following communication problem: Alice and Bob each have some valuation functions $v_1(\cdot)$ and $v_2(\cdot)$ over subsets of $m$ items, and their goal is to partition the items into $S, \bar{S}$ in a way that maximizes the welfare, $v_1(S) + v_2(\bar{S})$. We study both the allocation problem, which asks for a welfare-maximizing partition and the decision problem, which asks whe… ▽ More We consider the following communication problem: Alice and Bob each have some valuation functions $v_1(\cdot)$ and $v_2(\cdot)$ over subsets of $m$ items, and their goal is to partition the items into $S, \bar{S}$ in a way that maximizes the welfare, $v_1(S) + v_2(\bar{S})$. We study both the allocation problem, which asks for a welfare-maximizing partition and the decision problem, which asks whether or not there exists a partition guaranteeing certain welfare, for binary XOS valuations. For interactive protocols with $poly(m)$ communication, a tight 3/4-approximation is known for both [Fei06,DS06]. For interactive protocols, the allocation problem is provably harder than the decision problem: any solution to the allocation problem implies a solution to the decision problem with one additional round and $\log m$ additional bits of communication via a trivial reduction. Surprisingly, the allocation problem is provably easier for simultaneous protocols. Specifically, we show: 1) There exists a simultaneous, randomized protocol with polynomial communication that selects a partition whose expected welfare is at least $3/4$ of the optimum. This matches the guarantee of the best interactive, randomized protocol with polynomial communication. 2) For all $\varepsilon > 0$, any simultaneous, randomized protocol that decides whether the welfare of the optimal partition is $\geq 1$ or $\leq 3/4 - 1/108+\varepsilon$ correctly with probability $> 1/2 + 1/ poly(m)$ requires exponential communication. This provides a separation between the attainable approximation guarantees via interactive ($3/4$) versus simultaneous ($\leq 3/4-1/108$) protocols with polynomial communication. In other words, this trivial reduction from decision to allocation problems provably requires the extra round of communication. △ Less

Submitted 11 April, 2017; originally announced April 2017.

Network coding in undirected graphs is either very helpful or not helpful at all

Authors: Mark Braverman, Sumegha Garg, Ariel Schvartzman

Abstract: While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured by Li and Li (2004) that the answer is "no". In this paper we show that even a small advantage over MCF can be amplified to yield a near-maximu… ▽ More While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured by Li and Li (2004) that the answer is "no". In this paper we show that even a small advantage over MCF can be amplified to yield a near-maximum possible gap. We prove that any undirected network with $k$ source-sink pairs that exhibits a $(1+\varepsilon)$ gap between its MCF rate and its network coding rate can be used to construct a family of graphs $G'$ whose gap is $\log(|G'|)^c$ for some constant $c < 1$. The resulting gap is close to the best currently known upper bound, $\log(|G'|)$, which follows from the connection between MCF and sparsest cuts. Our construction relies on a gap-amplifying graph tensor product that, given two graphs $G_1,G_2$ with small gaps, creates another graph $G$ with a gap that is equal to the product of the previous two, at the cost of increasing the size of the graph. We iterate this process to obtain a gap of $\log(|G'|)^c$ from any initial gap. △ Less

Submitted 23 August, 2016; originally announced August 2016.

Comments: 20 pages

Parallel Algorithms for Select and Partition with Noisy Comparisons

Authors: Mark Braverman, Jieming Mao, S. Matthew Weinberg

Abstract: We consider the problem of finding the $k^{th}$ highest element in a totally ordered set of $n$ elements (select), and partitioning a totally ordered set into the top $k$ and bottom $n-k$ elements (partition) using pairwise comparisons. Motivated by settings like peer grading or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons may be inconsistent with the grou… ▽ More We consider the problem of finding the $k^{th}$ highest element in a totally ordered set of $n$ elements (select), and partitioning a totally ordered set into the top $k$ and bottom $n-k$ elements (partition) using pairwise comparisons. Motivated by settings like peer grading or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons may be inconsistent with the ground truth, we evaluate algorithms based both on their total runtime and the number of interactive rounds in three comparison models: noiseless (where the comparisons are correct), erasure (where comparisons are erased with probability $1-γ$), and noisy (where comparisons are correct with probability $1/2+γ/2$ and incorrect otherwise). We provide numerous matching upper and lower bounds in all three models. Even our results in the noiseless model, which is quite well-studied in the TCS literature on parallel algorithms, are novel. △ Less

Submitted 15 March, 2016; originally announced March 2016.

Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions

Authors: Mark Braverman, Jieming Mao, S. Matthew Weinberg

Abstract: We study the communication complexity of combinatorial auctions via interpolation mechanisms that interpolate between non-truthful and truthful protocols. Specifically, an interpolation mechanism has two phases. In the first phase, the bidders participate in some non-truthful protocol whose output is itself a truthful protocol. In the second phase, the bidders participate in the truthful protocol… ▽ More We study the communication complexity of combinatorial auctions via interpolation mechanisms that interpolate between non-truthful and truthful protocols. Specifically, an interpolation mechanism has two phases. In the first phase, the bidders participate in some non-truthful protocol whose output is itself a truthful protocol. In the second phase, the bidders participate in the truthful protocol selected during phase one. Note that virtually all existing auctions have either a non-existent first phase (and are therefore truthful mechanisms), or a non-existent second phase (and are therefore just traditional protocols, analyzed via the Price of Anarchy/Stability). The goal of this paper is to understand the benefits of interpolation mechanisms versus truthful mechanisms or traditional protocols, and develop the necessary tools to formally study them. Interestingly, we exhibit settings where interpolation mechanisms greatly outperform the optimal traditional and truthful protocols. Yet, we also exhibit settings where interpolation mechanisms are provably no better than truthful ones. Finally, we apply our new machinery to prove that the recent single-bid mechanism of Devanur et. al.~\cite{DevanurMSW15} (the only pre-existing interpolation mechanism in the literature) achieves the optimal price of anarchy among a wide class of protocols, a claim that simply can't be addressed by appealing just to machinery from communication complexity or the study of truthful mechanisms. △ Less

Submitted 9 November, 2015; originally announced November 2015.

Tight space-noise tradeoffs in computing the ergodic measure

Authors: Mark Braverman, Cristobal Rojas, Jon Schneider

Abstract: In this note we obtain tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system affected by Gaussian noise. If the scale of the noise is $\varepsilon$, and the function describing the evolution of the system is not by itself a source of computational complexity, then the density function of the ergodic measure can be approximated wit… ▽ More In this note we obtain tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system affected by Gaussian noise. If the scale of the noise is $\varepsilon$, and the function describing the evolution of the system is not by itself a source of computational complexity, then the density function of the ergodic measure can be approximated within precision $δ$ in space polynomial in $\log 1/\varepsilon+\log\log 1/δ$. We also show that this bound is tight up to polynomial factors. In the course of showing the above, we prove a result of independent interest in space-bounded computation: that it is possible to exponentiate an $n$ by $n$ matrix to an exponentially large power in space polylogarithmic in $n$. △ Less

Submitted 21 August, 2015; originally announced August 2015.

Comments: 25 pages

MSC Class: 68Q05; 37C40 ACM Class: F.1.1

Coding for interactive communication correcting insertions and deletions

Authors: Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky

Abstract: We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here the discussion into a more general and stronger class of noise, namely, we allow the channel to perform insertions and deletions of symbols. These types of errors may bring the parties "out of sync", so that there is no… ▽ More We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here the discussion into a more general and stronger class of noise, namely, we allow the channel to perform insertions and deletions of symbols. These types of errors may bring the parties "out of sync", so that there is no consensus regarding the current round of the protocol. In this more general noise model, we obtain the first interactive coding scheme that has a constant rate and resists noise rates of up to $1/18-\varepsilon$. To this end we develop a novel primitive we name edit distance tree code. The edit distance tree code is designed to replace the Hamming distance constraints in Schulman's tree codes (STOC 93), with a stronger edit distance requirement. However, the straightforward generalization of tree codes to edit distance does not seem to yield a primitive that suffices for communication in the presence of synchronization problems. Giving the "right" definition of edit distance tree codes is a main conceptual contribution of this work. △ Less

Submitted 24 May, 2016; v1 submitted 3 August, 2015; originally announced August 2015.

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

Authors: Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff

Abstract: We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the $m$ machines receives $n$ data points from a $d$-dimensional Gaussian distribution with unknown mean $θ$ which is promised to be $k$-sparse. The machines communicate by message passing a… ▽ More We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the $m$ machines receives $n$ data points from a $d$-dimensional Gaussian distribution with unknown mean $θ$ which is promised to be $k$-sparse. The machines communicate by message passing and aim to estimate the mean $θ$. We provide a tight (up to logarithmic factors) tradeoff between the estimation error and the number of bits communicated between the machines. This directly leads to a lower bound for the distributed \textit{sparse linear regression} problem: to achieve the statistical minimax error, the total communication is at least $Ω(\min\{n,d\}m)$, where $n$ is the number of observations that each machine receives and $d$ is the ambient dimension. These lower results improve upon [Sha14,SD'14] by allowing multi-round iterative communication model. We also give the first optimal simultaneous protocol in the dense case for mean estimation. As our main technique, we prove a \textit{distributed data processing inequality}, as a generalization of usual data processing inequalities, which might be of independent interest and useful for other problems. △ Less

Submitted 9 May, 2016; v1 submitted 23 June, 2015; originally announced June 2015.

Comments: To appear at STOC 2016. Fixed typos in theorem 4.5 and incorporated reviewers' suggestions

Near-optimal bounds on bounded-round quantum communication complexity of disjointness

Authors: Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette

Abstract: We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tildeΩ(n/r + r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound was $Ω(n/r^2 + r)$ due to Jain, Radhakrishnan and Sen… ▽ More We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tildeΩ(n/r + r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound was $Ω(n/r^2 + r)$ due to Jain, Radhakrishnan and Sen [JRS03]. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function $f$ is at most $2^{O(QIC(f))}$, where $QIC(f)$ is the prior-free quantum information complexity of $f$ (with error $1/3$). △ Less

Submitted 12 May, 2015; originally announced May 2015.

Comments: 41 pages

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness

Authors: Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein

Abstract: We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all k-subgraphs have density at most $1-ε$, requires $n^{\tilde Ω(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for this problem, and is the first one to rule out an addi… ▽ More We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all k-subgraphs have density at most $1-ε$, requires $n^{\tilde Ω(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for this problem, and is the first one to rule out an additive PTAS for Densest $k$-Subgraph. We further strengthen this result by showing that our lower bound continues to hold when, in the soundness case, even subgraphs smaller by a near-polynomial factor ($k' = k 2^{-\tilde Ω(log n)}$) are assumed to be at most ($1-ε$)-dense. Our reduction is inspired by recent applications of the "birthday repetition" technique [AIM14,BKW15]. Our analysis relies on information theoretical machinery and is similar in spirit to analyzing a parallel repetition of two-prover games in which the provers may choose to answer some challenges multiple times, while completely ignoring other challenges. △ Less

Submitted 30 April, 2015; originally announced April 2015.

Information complexity is computable

Authors: Mark Braverman, Jon Schneider

Abstract: The information complexity of a function $f$ is the minimum amount of information Alice and Bob need to exchange to compute the function $f$. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function $f$ to within any additive error $α> 0$, thus resolving an open question as to whether information complexity is computable. In the process, we give… ▽ More The information complexity of a function $f$ is the minimum amount of information Alice and Bob need to exchange to compute the function $f$. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function $f$ to within any additive error $α> 0$, thus resolving an open question as to whether information complexity is computable. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of $f$ when restricted to $b$-bit protocols to the (unrestricted) information complexity of $f$. △ Less

Submitted 10 February, 2015; originally announced February 2015.

Comments: 30 pages

MSC Class: 94A17; 68Q05 ACM Class: E.4

Simulating Noisy Channel Interaction

Authors: Mark Braverman, Jieming Mao

Abstract: We show that $T$ rounds of interaction over the binary symmetric channel $BSC_{1/2-ε}$ with feedback can be simulated with $O(ε^2 T)$ rounds of interaction over a noiseless channel. We also introduce a more general "energy cost" model of interaction over a noisy channel. We show energy cost to be equivalent to external information complexity, which implies that our simulation results are unlikely… ▽ More We show that $T$ rounds of interaction over the binary symmetric channel $BSC_{1/2-ε}$ with feedback can be simulated with $O(ε^2 T)$ rounds of interaction over a noiseless channel. We also introduce a more general "energy cost" model of interaction over a noisy channel. We show energy cost to be equivalent to external information complexity, which implies that our simulation results are unlikely to carry over to energy complexity. Our main technical innovation is a self-reduction from simulating a noisy channel to simulating a slightly-less-noisy channel, which may have other applications in the area of interactive compression. △ Less

Submitted 15 September, 2014; originally announced September 2014.

Contracting Experts With Unknown Cost Structures

Authors: Mark Braverman, Gal Oshri

Abstract: We investigate the problem of a principal looking to contract an expert to provide a probability forecast for a categorical event. We assume all experts have a common public prior on the event's probability, but can form more accurate opinions by engaging in research. Various experts' research costs are unknown to the principal. We present a truthful and efficient mechanism for the principal's pro… ▽ More We investigate the problem of a principal looking to contract an expert to provide a probability forecast for a categorical event. We assume all experts have a common public prior on the event's probability, but can form more accurate opinions by engaging in research. Various experts' research costs are unknown to the principal. We present a truthful and efficient mechanism for the principal's problem of contracting an expert. This results in the principal contracting the best expert to do the work, and the principal's expected utility is equivalent to having the second best expert in-house. Our mechanism connects scoring rules with auctions, a connection that is useful when obtaining new information requires costly research. △ Less

Submitted 29 April, 2014; originally announced April 2014.

Optimal Provision-After-Wait in Healthcare

Authors: Mark Braverman, Jing Chen, Sampath Kannan

Abstract: We investigate computational and mechanism design aspects of scarce resource allocation, where the primary rationing mechanism is through waiting times. Specifically we consider allocating medical treatments to a population of patients. Each patient needs exactly one treatment, and can choose from $k$ hospitals. Hospitals have different costs, which are fully paid by a third party ---the "payer".… ▽ More We investigate computational and mechanism design aspects of scarce resource allocation, where the primary rationing mechanism is through waiting times. Specifically we consider allocating medical treatments to a population of patients. Each patient needs exactly one treatment, and can choose from $k$ hospitals. Hospitals have different costs, which are fully paid by a third party ---the "payer". The payer has a fixed budget $B$, and each hospital will have its own waiting time. At equilibrium, each patient will choose his most preferred hospital given his intrinsic preferences and the waiting times. The payer thus computes the waiting times so that at equilibrium the budget constraint is satisfied and the social welfare is maximized. We first show that the optimization problem is NP-hard, yet if the budget can be relaxed to $(1+ε)B$ for an arbitrarily small $ε$, then the optimum under budget $B$ can be approximated efficiently. Next, we study the endogenous emergence of waiting time from the dynamics between hospitals and patients, and show that there is no need for the payer to explicitly enforce the optimal waiting times. Under certain conditions, all he need is to enforce the amount of money he wants to pay to each hospital. The dynamics will always converge to the desired waiting times in finite time. We then go beyond equilibrium solutions and investigate the optimization problem over a much larger class of mechanisms containing the equilibrium ones as special cases. With two hospitals, we show that under a natural assumption on the patients' preference profiles, optimal welfare is in fact attained by the randomized assignment mechanism, which allocates patients to hospitals at random subject to the budget constraint, but avoids waiting times. Finally, we discuss potential policy implications of our results, as well as follow-up directions and open problems. △ Less

Submitted 6 December, 2013; originally announced December 2013.

Comments: One-page abstract appears at Innovations in Theoretical Computer Science (ITCS), 2014

Tight Bounds for Set Disjointness in the Message Passing Model

Authors: Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan

Abstract: In a multiparty message-passing model of communication, there are $k$ players. Each player has a private input, and they communicate by sending messages to one another over private channels. While this model has been used extensively in distributed computing and in multiparty computation, lower bounds on communication complexity in this model and related models have been somewhat scarce. In recent… ▽ More In a multiparty message-passing model of communication, there are $k$ players. Each player has a private input, and they communicate by sending messages to one another over private channels. While this model has been used extensively in distributed computing and in multiparty computation, lower bounds on communication complexity in this model and related models have been somewhat scarce. In recent work \cite{phillips12,woodruff12,woodruff13}, strong lower bounds of the form $Ω(n \cdot k)$ were obtained for several functions in the message-passing model; however, a lower bound on the classical Set Disjointness problem remained elusive. In this paper, we prove tight lower bounds of the form $Ω(n \cdot k)$ for the Set Disjointness problem in the message passing model. Our bounds are obtained by developing information complexity tools in the message-passing model, and then proving an information complexity lower bound for Set Disjointness. As a corollary, we show a tight lower bound for the task allocation problem \cite{DruckerKuhnOshman} via a reduction from Set Disjointness. △ Less

Submitted 20 May, 2013; originally announced May 2013.

Search using queries on indistinguishable items

Authors: Mark Braverman, Gal Oshri

Abstract: We investigate the problem of determining a set S of k indistinguishable integers in the range [1,n]. The algorithm is allowed to query an integer $q\in [1,n]$, and receive a response comparing this integer to an integer randomly chosen from S. The algorithm has no control over which element of S the query q is compared to. We show tight bounds for this problem. In particular, we show that in the… ▽ More We investigate the problem of determining a set S of k indistinguishable integers in the range [1,n]. The algorithm is allowed to query an integer $q\in [1,n]$, and receive a response comparing this integer to an integer randomly chosen from S. The algorithm has no control over which element of S the query q is compared to. We show tight bounds for this problem. In particular, we show that in the natural regime where $k\le n$, the optimal number of queries to attain $n^{-Ω(1)}$ error probability is $Θ(k^3 \log n)$. In the regime where $k>n$, the optimal number of queries is $Θ(n^2 k \log n)$. Our main technical tools include the use of information theory to derive the lower bounds, and the application of noisy binary search in the spirit of Feige, Raghavan, Peleg, and Upfal (1994). In particular, our lower bound technique is likely to be applicable in other situations that involve search under uncertainty. △ Less

Submitted 4 February, 2013; originally announced February 2013.

Comments: A version of this paper was presented in STACS'13

On the Convergence of the Hegselmann-Krause System

Authors: Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle, Huy L. Nguyen

Abstract: We study convergence of the following discrete-time non-linear dynamical system: n agents are located in R^d and at every time step, each moves synchronously to the average location of all agents within a unit distance of it. This popularly studied system was introduced by Krause to model the dynamics of opinion formation and is often referred to as the Hegselmann-Krause model. We prove the first… ▽ More We study convergence of the following discrete-time non-linear dynamical system: n agents are located in R^d and at every time step, each moves synchronously to the average location of all agents within a unit distance of it. This popularly studied system was introduced by Krause to model the dynamics of opinion formation and is often referred to as the Hegselmann-Krause model. We prove the first polynomial time bound for the convergence of this system in arbitrary dimensions. This improves on the bound of n^{O(n)} resulting from a more general theorem of Chazelle. Also, we show a quadratic lower bound and improve the upper bound for one-dimensional systems to O(n^3). △ Less

Submitted 8 November, 2012; originally announced November 2012.

Comments: 9 pages, 1 figure, to appear in ITCS '13

Truthful Mechanisms for Competing Submodular Processes

Authors: Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren

Abstract: Motivated by applications to word-of-mouth advertising, we consider a game-theoretic scenario in which competing advertisers want to target initial adopters in a social network. Each advertiser wishes to maximize the resulting cascade of influence, modeled by a general network diffusion process. However, competition between products may adversely impact the rate of adoption for any given firm. The… ▽ More Motivated by applications to word-of-mouth advertising, we consider a game-theoretic scenario in which competing advertisers want to target initial adopters in a social network. Each advertiser wishes to maximize the resulting cascade of influence, modeled by a general network diffusion process. However, competition between products may adversely impact the rate of adoption for any given firm. The resulting framework gives rise to complex preferences that depend on the specifics of the stochastic diffusion model and the network topology. We study this model from the perspective of a central mechanism, such as a social networking platform, that can optimize seed placement as a service for the advertisers. We ask: given the reported demands of the competing firms, how should a mechanism choose seeds to maximize overall efficiency? Beyond the algorithmic problem, competition raises issues of strategic behaviour: rational agents should not be incentivized to underreport their budget demands. We show that when there are two players, the social welfare can be $2$-approximated by a polynomial-time strategyproof mechanism. Our mechanism is defined recursively, randomizing the order in which advertisers are allocated seeds according to a particular greedy method. For three or more players, we demonstrate that under additional assumptions (satisfied by many existing models of influence spread) there exists a simpler strategyproof $\frac{e}{e-1}$-approximation mechanism; notably, this second mechanism is not necessarily strategyproof when there are only two players. △ Less

Submitted 25 March, 2014; v1 submitted 9 February, 2012; originally announced February 2012.

Comments: The latest version contains a revised Section 4 and Appendix D

Finding Endogenously Formed Communities

Authors: Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer Chayes, Shang-Hua Teng

Abstract: A central problem in e-commerce is determining overlapping communities among individuals or objects in the absence of external identification or tagging. We address this problem by introducing a framework that captures the notion of communities or clusters determined by the relative affinities among their members. To this end we define what we call an affinity system, which is a set of elements, e… ▽ More A central problem in e-commerce is determining overlapping communities among individuals or objects in the absence of external identification or tagging. We address this problem by introducing a framework that captures the notion of communities or clusters determined by the relative affinities among their members. To this end we define what we call an affinity system, which is a set of elements, each with a vector characterizing its preference for all other elements in the set. We define a natural notion of (potentially overlapping) communities in an affinity system, in which the members of a given community collectively prefer each other to anyone else outside the community. Thus these communities are endogenously formed in the affinity system and are "self-determined" or "self-certified" by its members. We provide a tight polynomial bound on the number of self-determined communities as a function of the robustness of the community. We present a polynomial-time algorithm for enumerating these communities. Moreover, we obtain a local algorithm with a strong stochastic performance guarantee that can find a community in time nearly linear in the of size the community. Social networks fit particularly naturally within the affinity system framework -- if we can appropriately extract the affinities from the relatively sparse yet rich information from social networks, our analysis then yields a set of efficient algorithms for enumerating self-determined communities in social networks. In the context of social networks we also connect our analysis with results about $(α,β)$-clusters introduced by Mishra, Schreiber, Stanton, and Tarjan \cite{msst}. In contrast with the polynomial bound we prove on the number of communities in the affinity system model, we show that there exists a family of networks with superpolynomial number of $(α,β)$-clusters. △ Less

Submitted 29 February, 2012; v1 submitted 23 January, 2012; originally announced January 2012.

Comments: 22 pages

ACM Class: F.2.0; J.4

Noise vs computational intractability in dynamics

Authors: Mark Braverman, Alexander Grigo, Cristobal Rojas

Abstract: Computation plays a key role in predicting and analyzing natural phenomena. There are two fundamental barriers to our ability to computationally understand the long-term behavior of a dynamical system that describes a natural process. The first one is unaccounted-for errors, which may make the system unpredictable beyond a very limited time horizon. This is especially true for chaotic systems, whe… ▽ More Computation plays a key role in predicting and analyzing natural phenomena. There are two fundamental barriers to our ability to computationally understand the long-term behavior of a dynamical system that describes a natural process. The first one is unaccounted-for errors, which may make the system unpredictable beyond a very limited time horizon. This is especially true for chaotic systems, where a small change in the initial conditions may cause a dramatic shift in the trajectories. The second one is Turing-completeness. By the undecidability of the Halting Problem, the long-term prospects of a system that can simulate a Turing Machine cannot be determined computationally. We investigate the interplay between these two forces -- unaccounted-for errors and Turing-completeness. We show that the introduction of even a small amount of noise into a dynamical system is sufficient to "destroy" Turing-completeness, and to make the system's long-term behavior computationally predictable. On a more technical level, we deal with long-term statistical properties of dynamical systems, as described by invariant measures. We show that while there are simple dynamical systems for which the invariant measures are non-computable, perturbing such systems makes the invariant measures efficiently computable. Thus, noise that makes the short term behavior of the system harder to predict, may make its long term statistical behavior computationally tractable. We also obtain some insight into the computational complexity of predicting systems affected by random noise. △ Less

Submitted 2 January, 2012; originally announced January 2012.

Comments: ITCS 2012. 37 pages, 1 figure

MSC Class: 37C20; 37C40 ACM Class: H.1.1; F.1.1; F.1.3

A discrepancy lower bound for information complexity

Authors: Mark Braverman, Omri Weinstein

Abstract: This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized communication complexity, also applies to information complexity. More precisely, if the discrepancy of a two-party function $f$ with respect to a distribution $μ$ is $Disc_μf$, then any two… ▽ More This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized communication complexity, also applies to information complexity. More precisely, if the discrepancy of a two-party function $f$ with respect to a distribution $μ$ is $Disc_μf$, then any two party randomized protocol computing $f$ must reveal at least $Ω(\log (1/Disc_μf))$ bits of information to the participants. As a corollary, we obtain that any two-party protocol for computing a random function on $\{0,1\}^n\times\{0,1\}^n$ must reveal $Ω(n)$ bits of information to the participants. In addition, we prove that the discrepancy of the Greater-Than function is $Ω(1/\sqrt{n})$, which provides an alternative proof to the recent proof of Viola \cite{Viola11} of the $Ω(\log n)$ lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight $Ω(\log n)$ lower bound on its information complexity. The proof of our main result develops a new simulation procedure that may be of an independent interest. In a very recent breakthrough work of Kerenidis et al. \cite{kerenidis2012lower}, this simulation procedure was the main building block for proving that almost all known lower bound techniques for communication complexity (and not just discrepancy) apply to information complexity. △ Less

Submitted 12 June, 2012; v1 submitted 8 December, 2011; originally announced December 2011.

Information Equals Amortized Communication

Authors: Mark Braverman, Anup Rao

Abstract: We show how to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver. This is a generalization and strengthening of the Slepian-Wolf theorem, which shows how to carry out such a simulation… ▽ More We show how to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver. This is a generalization and strengthening of the Slepian-Wolf theorem, which shows how to carry out such a simulation with low amortized communication in the case that M is a deterministic function of X. A caveat is that our simulation is interactive. As a consequence, we prove that the internal information cost (namely the information revealed to the parties) involved in computing any relation or function using a two party interactive protocol is exactly equal to the amortized communication complexity of computing independent copies of the same relation or function. We also show that the only way to prove a strong direct sum theorem for randomized communication complexity is by solving a particular variant of the pointer jumping problem that we define. Our work implies that a strong direct sum theorem for communication complexity holds if and only if efficient compression of communication protocols is possible. △ Less

Submitted 17 June, 2011; originally announced June 2011.

Inapproximability of NP-Complete Variants of Nash Equilibrium

Authors: Per Austrin, Mark Braverman, Eden Chlamtac

Abstract: In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an $\eps$-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as finding a hidden clique of size $O(\log n)$ in the random graph $G(n,1/2)$. This raises the question of whether a similar intractability holds for approximate Nash equilibrium without such constraints. We give evidence th… ▽ More In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an $\eps$-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as finding a hidden clique of size $O(\log n)$ in the random graph $G(n,1/2)$. This raises the question of whether a similar intractability holds for approximate Nash equilibrium without such constraints. We give evidence that the constraint of near-optimal value makes the problem distinctly harder: a simple algorithm finds an optimal 1/2-approximate equilibrium, while finding strictly better than 1/2-approximate equilibria is as hard as the Hidden Clique problem. This is in contrast to the unconstrained problem where more sophisticated algorithms, achieving better approximations, are known. Unlike general Nash equilibrium, which is in PPAD, optimal (maximum value) Nash equilibrium is NP-hard. We proceed to show that optimal Nash equilibrium is just one of several known NP-hard problems related to Nash equilibrium, all of which have approximate variants which are as hard as finding a planted clique. In particular, we show this for approximate variants of the following problems: finding a Nash equilibrium with value greater than $η$ (for any $η>0$, even when the best Nash equilibrium has value $1-η$), finding a second Nash equilibrium, and finding a Nash equilibrium with small support. Finally, we consider the complexity of approximate pure Bayes Nash equilibria in two-player games. Here we show that for general Bayesian games the problem is NP-hard. For the special case where the distribution over types is uniform, we give a quasi-polynomial time algorithm matched by a hardness result based on the Hidden Clique problem. △ Less

Submitted 19 April, 2011; originally announced April 2011.

The Grothendieck constant is strictly smaller than Krivine's bound

Authors: Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor

Abstract: We prove that $K_G<\fracπ{2\log(1+\sqrt{2})}$, where $K_G$ is the Grothendieck constant. We prove that $K_G<\fracπ{2\log(1+\sqrt{2})}$, where $K_G$ is the Grothendieck constant. △ Less

Submitted 17 August, 2011; v1 submitted 31 March, 2011; originally announced March 2011.

Comments: An extended abstract describing the contents of this work will appear in FOCS 2011. Suggestions of the FOCS reviewers have been addressed

Matching with Couples Revisited

Authors: Itai Ashlagi, Mark Braverman, Avinatan Hassidim

Abstract: It is well known that a stable matching in a many-to-one matching market with couples need not exist. We introduce a new matching algorithm for such markets and show that for a general class of large random markets the algorithm will find a stable matching with high probability. In particular we allow the number of couples to grow at a near-linear rate. Furthermore, truth-telling is an approximate… ▽ More It is well known that a stable matching in a many-to-one matching market with couples need not exist. We introduce a new matching algorithm for such markets and show that for a general class of large random markets the algorithm will find a stable matching with high probability. In particular we allow the number of couples to grow at a near-linear rate. Furthermore, truth-telling is an approximated equilibrium in the game induced by the new matching algorithm. Our results are tight: for markets in which the number of couples grows at a linear rate, we show that with constant probability no stable matching exists. △ Less

Submitted 17 November, 2010; v1 submitted 9 November, 2010; originally announced November 2010.