We consider the problem of optimal transport between two high-dimensional distributions μ,ν in ℝⁿ from a new algorithmic perspective, in which we are given a sample x ∼ μ and we have to find a close y ∼ ν while running in poly(n) time, where n is the size/dimension of x,y. In other words, we are interested in making the running time bounded in dimension of the spaces rather than bounded in the total size of the representations of the two distributions. Our main result is a general algorithmic transport result between any product distribution μ and an arbitrary distribution ν of total cost Δ + δ under 𝓁_p^p cost; here Δ is the cost of the so-called Knothe–Rosenblatt transport from μ to ν, while δ is a computational error that goes to zero for larger running time in the transport algorithm. For this result, we need ν to be "sequentially samplable" with a "bounded average sampling cost" which is a novel but natural notion of independent interest. In addition, we prove the following. - We prove an algorithmic version of the celebrated Talagrand’s inequality for transporting the standard Gaussian distribution Φⁿ to an arbitrary ν under the Euclidean-squared cost. When ν is Φⁿ conditioned on a set S of measure ε, we show how to implement the needed sequential sampler for ν in expected time poly(n/ε), using membership oracle access to S. Hence, we obtain an algorithmic transport that maps Φⁿ to Φⁿ|S in time poly(n/ε) and expected Euclidean-squared distance O(log 1/ε), which is optimal for a general set S of measure ε. - As corollary, we find the first computational concentration (Etesami et al. SODA 2020) result for the Gaussian measure under the Euclidean distance with a dimension-independent transportation cost, resolving a question of Etesami et al. More precisely, for any set S of Gaussian measure ε, we map most of Φⁿ samples to S with Euclidean distance O(√{log 1/ε}) in time poly(n/ε).

Product measures of dimension n are known to be “concentrated” under Hamming distance. More precisely, for any set S in the product space of probability Pr[S] ≥ ε, a random point in the space, with probability 1 – δ, has a neighbor in S that is different from the original point in only coordinates (and this is optimal). In this work, we obtain the tight computational (algorithmic) version of this result, showing how given a random point and access to an S-membership query oracle, we can find such a close point of Hamming distance in time poly(n, 1/ε, 1/δ). This resolves an open question of [MM19] who proved a weaker result (that works only for ). As corollaries, we obtain polynomial-time poisoning and (in certain settings) evasion attacks against learning algorithms when the original vulnerabilities have any cryptographically non-negligible probability. We call our algorithm MUCIO (short for “MUltiplicative Conditional Influence Optimizer”) since proceeding through the coordinates of the product space, it decides to change each coordinate of the given point based on a multiplicative version of the influence of a variable, where the influence is computed conditioned on the value of all previously updated coordinates. MUCIO is an online algorithm in that it decides on the i'th coordinate of the output given only the first i coordinates of the input. It also does not make any convexity assumption about the set S. Motivated by obtaining algorithmic variants of measure concentration in other metric probability spaces, we define a new notion of algorithmic reduction between computational concentration of measure in different probability metric spaces. This notion, whose definition has some subtlety, requires two (inverse) algorithmic mappings one of which is an algorithmic Lipschitz mapping and the other one is an algorithmic coupling connecting the two distributions. As an application, we apply this notion of reduction to obtain computational concentration of measure for high-dimensional Gaussian distributions under the ℓ1 distance. We further prove several extensions to the results above as follows. (1) Generalizing in another dimension, our computational concentration result is also true when the Hamming distance is weighted. (2) As measure concentration is usually proved for concentration around mean, we show how to use our results above to obtain algorithmic concentration for that setting as well. In particular, we prove a computational variant of McDiarmid's inequality, when properly defined. (3) Our result generalizes to discrete random processes (instead of just product distributions), and this generalization leads to new tampering algorithms for collective coin tossing protocols. (4) Finally, we prove exponential lower bounds on the average running time of non-adaptive query algorithms for proving computational concentration for the case of product spaces. Perhaps surprisingly, such lower bound shows any efficient algorithm must query about S-membership of points that are not close to the original point even though we are only interested in finding a close point in S.

Properties of graphs that can be characterized by the spectrum of the adjacency matrix of the graph have been studied systematically recently. Motivated by the complexity of these properties, we show that there are such properties for which testing whether a graph has that property can be NP-hard (or belong to other computational complexity classes consisting of even harder problems). In addition, we discuss a possible spectral characterization of some well-known NP-hard properties. In particular, for every integer k≥6 we construct a pair of k-regular cospectral graphs, where one graph is Hamiltonian and the other one not.

Let F be a finite alphabet and D be a finite set of distributions over F. A Generalized Santha-Vazirani (GSV) source of type (F, D), introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence (F_1, ..., F_n) in F^n, where F_i is a sample from some distribution d in D whose choice may depend on F_1, ..., F_{i-1}. We show that all GSV source types (F, D) fall into one of three categories: (1) non-extractable; (2) extractable with error n^{-Theta(1)}; (3) extractable with error 2^{-Omega(n)}. We provide essentially randomness-optimal extraction algorithms for extractable sources. Our algorithm for category (2) sources extracts one bit with error epsilon from n = poly(1/epsilon) samples in time linear in n. Our algorithm for category (3) sources extracts m bits with error epsilon from n = O(m + log 1/epsilon) samples in time min{O(m2^m * n),n^{O(|F|)}}. We also give algorithms for classifying a GSV source type (F, D): Membership in category (1) can be decided in NP, while membership in category (3) is polynomial-time decidable.

A Santha--Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible. In this paper, we study the generalization of SV sources for nonbinary sequences. We show that unlike the binary setup of Santha and Vazirani, deterministic randomness extraction in the generalized case is sometimes possible. In particular, if the adversary has access to $s$ “nondegenerate” dice that are $c$-sided and can choose one die to throw based on the previous realizations of the dice, then deterministic randomness extraction is possible if $s

We introduce irregular product codes, a class of codes where each codeword is represented by a matrix and the entries in each row (column) of the matrix come from a component row (column) code. As opposed to standard product codes, we do not require that all component row codes nor all component column codes be the same. Relaxing this requirement can provide some additional attractive features such as allowing some regions of the codeword to be more error-resilient, providing a more refined spectrum of rates for finite lengths, and improved performance for some of these rates. We study these codes over erasure channels and prove that for any 0 <; ε <; 1, for many rate distributions on component row codes, there is a matching rate distribution on component column codes such that an irregular product code based on MDS codes with those rate distributions on the component codes has asymptotic rate 1 - ε and can decode on erasure channels having erasure probability <; ε (and having alphabet size equal to the alphabet size of the component MDS codes).

We consider the problem of online keyword advertising auctions among multiple bidders with limited budgets, and study a natural bidding heuristic in which advertisers attempt to optimize their utility by equalizing their return-on-investment across all keywords. We show that existing auction mechanisms combined with this heuristic can experience cycling (as has been observed in many current systems), and therefore propose a modified class of mechanisms with small random perturbations. This perturbation is reminiscent of the small time-dependent perturbations employed in the dynamical systems literature to convert many types of chaos into attracting motions. We show that the perturbed mechanism provably converges in the case of first-price auctions and experimentally converges in the case of second-price auctions. Moreover, the point of convergence has a natural economic interpretation as the unique market equilibrium in the case of first-price mechanisms. In the case of second-price auctions, we conjecture that it converges to the "supply-aware" market equilibrium. Thus, our results can be alternatively described as a tâtonnement process for convergence to market equilibriumin which prices are adjusted on the side of the buyers rather than the sellers. We also observe that perturbation in mechanism design is useful in a broader context: In general, it can allow bidders to "share" a particular item, leading to stable allocations and pricing for the bidders, and improved revenue for the auctioneer.

In this paper, we will investigate the performance of Raptor codes on arbitrary binary input memoryless symmetric channels (BIMSCs). In doing so, we generalize some of the results that were proved before for the erasure channel. We will generalize the stability condition to the class of Raptor codes. This generalization gives a lower bound on the fraction of output nodes of degree 2 of a Raptor code if the error probability of the belief-propagation decoder converges to zero. Using information-theoretic arguments, we will show that if a sequence of output degree distributions is to achieve the capacity of the underlying channel, then the fraction of nodes of degree 2 in these degree distributions has to converge to a certain quantity depending on the channel. For the class of erasure channels this quantity is independent of the erasure probability of the channel, but for many other classes of BIMSCs, this fraction depends on the particular channel chosen. This result has implications on the "universality" of Raptor codes for classes other than the class of erasure channels, in a sense that will be made more precise in the paper. We will also investigate the performance of specific Raptor codes which are optimized using a more exact version of the Gaussian approximation technique.

An upper bound on the performance of the belief propagation algorithm in decoding a code over a binary-input output-symmetric channel in terms of the decoding threshold of the code over the erasure channel is presented in this paper. Using this upper bound, we obtain the overhead of fountain codes on the erasure channel, provided that they are capacity-achieving on a symmetric channel. The upper bound is similar to a lower bound proved by Khandekar. The lower bound will be used to bound from above the reception overhead of fountain codes on symmetric channels.

This paper extends the construction and analysis of Raptor codes originally designed in A. Shokrollahi (2004) for the erasure channel to general symmetric channels. We explicitly calculate the asymptotic fraction of output nodes of degree one and two for capacity-achieving Raptor codes, and discuss techniques to optimize the output degree distribution.