Since the introduction of tree codes by Schulman (STOC 1993), explicit construction of asymptotically good tree codes has remained a notorious challenge. A work by Cohen, Haeupler and Schulman (STOC 2018), as well as the state-of-the-art construction by Ben Yaacov, Cohen, and Yankovitz (STOC 2022) have achieved codes with rate $Ω(1/\log\log n)$, exponentially improving upon the original rate $Ω(1/\log n)$ construction of Evans, Klugerman and Schulman from 1994. All of these constructions rely, at least in part, on increasingly sophisticated methods of combining (block) error-correcting codes. In this work, we identify a fundamental barrier to constructing tree codes using known techniques. We introduce a key property which we call immediacy, that, while not required by the original definition of tree codes, is shared by all known constructions and inherently arises in recursive combinations of error-correcting codes. Our main technical contribution is the proof of a rate-immediacy trade-off, which, in particular, implies that any tree code with constant distance and non-trivial immediacy must necessarily have vanishing rate. By applying our rate-immediacy trade-off to existing constructions, we establish that their known rate analyses are essentially optimal given their actual error-correction properties. More broadly, our work highlights the need for fundamentally new ideas -- beyond the recursive use of error-correcting codes -- to achieve substantial progress in explicitly constructing asymptotically good tree codes.

A famous theorem of Kruskal gives the simplest and arguably most fundamental criterion under which a tensor is guaranteed a unique minimum-rank decomposition. Kruskal’s condition requires that the sum of the Kruskal ranks {k_i}_{i=1}^m of the components satisfies ∑_{i∈[m]} k_i ≥ 2r + m - 1, where r denotes the rank and m the order of the tensor. However, Kruskal’s original proof and subsequent simplifications/generalizations have remained non-constructive. With the sole exception of the case (k₁ = r, k₂ = r, k₃ = 2), attributed to Jennrich - no algorithm has been established for decomposing tensors under the Kruskal condition without additional assumptions. In fact, whether there exists an efficient algorithm for decomposing a tensor under the Kruskal condition was explicitly posed as an open problem in the work of Bhaskara et al. (COLT 2014). Even slight variations of the Jennrich special case, such as the (r, r-1, 3) case, have remained algorithmically open; specifically, no sub-exponential time bound was known. In this work, we make progress on this problem by giving an elementary, constructive proof of Kruskal’s Theorem for general m-way tensors. Concretely, we give a randomized algorithm that decomposes any tensor satisfying the Kruskal condition by utilizing random projections to map the problem into a geometry of intersecting hyperplanes via a MinRank instance. Specifically for 3-way tensors satisfying k₁+k₂+k₃ = 2r+2, the algorithm achieves a runtime of n^O(k) where k = min(k₁,k₂,k₃). Thus, we extend smoothly beyond the Jennrich special case, achieving polynomial-time complexity for any family of tensors that satisfies the Kruskal condition, provided the least Kruskal rank is bounded.

Since this paper is under journal submission, we publish only an extended abstract here. A full version can be found at https://arxiv.org/abs/2406.03938.

Causal discovery algorithms typically recover causal graphs only up to their Markov equivalence classes unless additional parametric assumptions are made. The sizes of these equivalence classes reflect the limits of what can be learned about the underlying causal graph from purely observational data. Under the assumptions of acyclicity, causal sufficiency, and a uniform model prior, Markov equivalence classes are known to be small on average. In this paper, we show that this is no longer the case when any of these assumptions is relaxed. Specifically, we prove exponentially large lower bounds for the expected size of Markov equivalence classes in three settings: sparse random directed acyclic graphs, uniformly random acyclic directed mixed graphs, and uniformly random directed cyclic graphs.

Product of experts (PoE) are layered networks in which the value at each node is an AND (or product) of the values (possibly negated) at its inputs. These were introduced as a neural network architecture that can efficiently learn to generate high-dimensional data which satisfy many low-dimensional constraints-thereby allowing each individual expert to perform a simple task. PoEs have found a variety of applications in learning. We study the problem of identifiability of a product of experts model having a layer of binary latent variables, and a layer of binary observables that are iid conditional on the latents. The previous best upper bound on the number of observables needed to identify the model was exponential in the number of parameters. We show: (a) When the latents are uniformly distributed, the model is identifiable with a number of observables equal to the number of parameters (and hence best possible). (b) In the more general case of arbitrarily distributed latents, the model is identifiable for a number of observables that is still linear in the number of parameters (and within a factor of two of best-possible). The proofs rely on root interlacing phenomena for some special three-term recurrences.

We consider the problem of \emph{identifying,} from statistics, a distribution of discrete random variables $X_1 \ldots,X_n$ that is a mixture of $k$ product distributions. The best previous sample complexity for $n \in O(k)$ was $(1/\zeta)^{O(k^2 \log k)}$ (under a mild separation assumption parameterized by $\zeta$). The best known lower bound was $\exp(\Omega(k))$. It is known that $n\geq 2k-1$ is necessary and sufficient for identification. We show, for any $n\geq 2k-1$, how to achieve sample complexity and run-time complexity $(1/\zeta)^{O(k)}$. We also extend the known lower bound of $e^{\Omega(k)}$ to match our upper bound across a broad range of $\zeta$. Our results are obtained by combining (a) a classic method for robust tensor decomposition, (b) a novel way of bounding the condition number of key matrices called Hadamard extensions, by studying their action only on flattened rank-1 tensors.

In the Euclidean k-Means problem we are given a collection of n points D in an Euclidean space and a positive integer k. Our goal is to identify a collection of k points in the same space (centers) so as to minimize the sum of the squared Euclidean distances between each point in D and the closest center. This problem is known to be APX-hard and the current best approximation ratio is a primal-dual 6.357 approximation based on a standard LP for the problem [Ahmadian et al. FOCS'17, SICOMP'20]. In this note we show how a minor modification of Ahmadian et al.'s analysis leads to a slightly improved 6.12903 approximation. As a related result, we also show that the mentioned LP has integrality gap at least 16+515>1.2157.

The Hadamard Extension$\mathbb H({\mathrm {m}})$of an$n \times k$matrix m is the collection of all Hadamard products of subsets of its rows. This construction is essential for source identification (parameter estimation) of a mixture of$k$product distributions over$n$binary random variables. A necessary requirement for such identification is that$\mathbb H({\mathrm {m}})$have full column rank; conversely, identification is possible if apart from each row there exist two disjoint sets of rows of m, each of whose extension has full column rank. It is necessary therefore to understand when$\mathbb H({\mathrm {m}})$has full column rank; we provide two results in this direction. The first is that if$\mathbb H({\mathrm {m}})$has full column rank then there exists a set of at most$k-1$rows of m, whose extension already has full column rank. The second is a Hall-type condition on the values in the rows of m, that suffices to ensure full column rank of$\mathbb H({\mathrm {m}})$.

We give an algorithm for source identification of a mixture of k product distributions on n bits. This is a fundamental problem in machine learning with many applications. Our algorithm identifies the source parameters of an identifiable mixture, given, as input, approximate values of multilinear moments (derived, for instance, from a sufficiently large sample), using $2^{O(k^2)}n^{O(k)}$ arithmetic operations. Our result is the first explicit bound on the computational complexity of source identification of such mixtures. The running time improves previous results by Feldman, O’Donnell, and Servedio (FOCS 2005) and Chen and Moitra (STOC 2019) that guaranteed only learning the mixture (without parametric identification of the source). Our analysis gives a quantitative version of a qualitative characterization of identifiable sources that is due to Tahmasebi, Motahari, and Maddah-Ali (ISIT 2018).

An important achievement in the field of causal inference was a complete characterization of when a causal effect, in a system modeled by a causal graph, can be determined uniquely from purely observational data. The identification algorithms resulting from this work produce exact symbolic expressions for causal effects, in terms of the observational probabilities. More recent work has looked at the numerical properties of these expressions, in particular using the classical notion of the condition number. In its classical interpretation, the condition number quantifies the sensitivity of the output values of the expressions to small numerical perturbations in the input observational probabilities. In the context of causal identification, the condition number has also been shown to be related to the effect of certain kinds of uncertainties in the structure of the causal graphical model. In this paper, we first give an upper bound on the condition number for the interesting case of causal graphical models with small “confounded components”. We then develop a tight characterization of the condition number of any given causal identification problem. Finally, we use our tight characterization to give a specific example where the condition number can be much lower than that obtained via generic bounds on the condition number, and to show that even “equivalent” expressions for causal identification can behave very differently with respect to their numerical stability properties.

The classic graphical Cheeger inequalities state that if M is an n × n symmetric doubly stochastic matrix, then where is the edge expansion of M, and λ2(M) is the second largest eigenvalue of M. We study the relationship between φ(A) and the spectral gap 1 – Re λ2(A) for any doubly stochastic matrix A (not necessarily symmetric), where λ2(A) is a nontrivial eigenvalue of A with maximum real part. Fiedler showed that the upper bound on φ(A) is unaffected, i.e., . With regards to the lower bound on φ(A), there are known constructions with indicating that at least a mild dependence on n is necessary to lower bound φ(A). In our first result, we provide an exponentially better construction of n × n doubly stochastic matrices An, for which In fact, all nontrivial eigenvalues of our matrices are 0, even though the matrices are highly nonexpanding. We further show that this bound is in the correct range (up to the exponent of n), by showing that for any doubly stochastic matrix A, As a consequence, unlike the symmetric case, there is a (necessary) loss of a factor of in lower bounding φ by the spectral gap in the nonsymmetric setting. Our second result extends these bounds to general matrices R with nonnegative entries, to obtain a two-sided gapped refinement of the Perron-Frobenius theorem. Recall from the Perron-Frobenius theorem that for such R, there is a nonnegative eigenvalue r such that all eigenvalues of R lie within the closed disk of radius r about 0. Further, if R is irreducible, which means φ(R) > 0 (for suitably defined φ), then r is positive and all other eigenvalues lie within the open disk, so (with eigenvalues sorted by real part), Re λ2(R) < r. An extension of Fiedler's result provides an upper bound and our result provides the corresponding lower bound on φ(R) in terms of r – Re λ2(R), obtaining a two-sided quantitative version of the Perron-Frobenius theorem.

This paper revisits a classical scenario in communication theory: a waveform sampled at regular intervals is to be encoded so as to minimize distortion in its reconstruction, despite the noise. This transformation must be online (causal), to enable real-time signaling, and should use no more power than the original signal. The noise model we consider is an atomic norm convex relaxation of the standard (discrete alphabet) Hammingweight-bounded model, namely adversarial ℓ1-bounded. In the block coding (noncausal) setting, such encoding is possible due to the existence of large almost-Euclidean sections in ℓ1spaces, a notion first studied in the work of Dvoretzky in 1961. Our main result is that an analogous result is achievable even casually. Equivalently, our work may be seen as a lower triangular version of ℓ1Dvoretzky theorems. In terms of communication, the guarantees are expressed in terms of certain time-weighted norms: the time-weighted ℓ2norm imposed on the decoder forces increasingly accurate reconstruction of the distant past signal, while the time-weighted ℓ1norm on the noise ensures vanishing interference from distant past noise. Encoding is linear (hence easy to implement in analog hardware). Decoding is performed by an LP analogous to those used in compressed sensing.

We analyze a stylized model of co-evolution between any two purely competing species (e.g., host and parasite), both sexually reproducing. Similarly to a recent model of Livnat \etal~\cite{evolfocs14} the fitness of an individual depends on whether the truth assignments on $n$ variables that reproduce through recombination satisfy a particular Boolean function. Whereas in the original model a satisfying assignment always confers a small evolutionary advantage, in our model the two species are in an evolutionary race with the parasite enjoying the advantage if the value of its Boolean function matches its host, and the host wishing to mismatch its parasite. Surprisingly, this model makes a simple and robust behavioral prediction. The typical system behavior is \textit{periodic}. These cycles stay bounded away from the boundary and thus, \textit{learning-dynamics competition between sexual species can provide an explanation for genetic diversity.} This explanation is due solely to the natural selection process. No mutations, environmental changes, etc., need be invoked. The game played at the gene level may have many Nash equilibria with widely diverse fitness levels. Nevertheless, sexual evolution leads to gene coordination that implements an optimal strategy, i.e., an optimal population mixture, at the species level. Namely, the play of the many "selfish genes" implements a time-averaged correlated equilibrium where the average fitness of each species is exactly equal to its value in the two species zero-sum competition. Our analysis combines tools from game theory, dynamical systems and Boolean functions to establish a novel class of conservative dynamical systems.

We study security games in which a defender commits to a mixed strategy for protecting a finite set of targets of different values. An attacker, knowing the defender's strategy, chooses which target to attack and for how long. If the attacker spends time t at a target i of value αi, and if he leaves before the defender visits the target, his utility is t · ai; if the defender visits before he leaves, his utility is 0. The defender's goal is to minimize the attacker's utility. The defender's strategy consists of a schedule for visiting the targets; it takes her unit time to switch between targets. Such games are a simplified model of a number of real-world scenarios such as protecting computer networks from intruders, crops from thieves, etc. We show that optimal defender play for such security games, although played in continuous time, reduces to the solution of a combinatorial question regarding the existence of infinite sequences over a finite alphabet, with the following properties for each symbol i: (1) i constitutes a prescribed limiting fraction pi of the sequence. (2) The occurrences of i are spread apart close to evenly, in that the ratio of the longest to shortest interval between consecutive occurrences is bounded by a parameter K. We call such sequences K-quasi-regular; a 1-quasi-regular sequence is one in which the occurrences of each symbol form an arithmetic sequence. As we show, a 1-quasi-regular sequence ensures an optimal defender strategy for these security games: the intuition for this fact lies in the famous “inspection paradox.” However, as we demonstrate, for K < 2 and general pi, K-quasi-regular sequences may not exist. Fortunately, this does not turn out to be an obstruction: we show that, surprisingly, 2-quasi-regular sequences also suffice for optimal defender play. What is more, even randomized 2-quasi-regular sequences suffice for optimality. We show that such sequences always exist, and can be calculated efficiently. Thus, we can ensure optimal defender play for these security games. The question of the least K for which deterministic K-quasi-regular sequences exist is fascinating. Using an ergodic theoretical approach, we proceed to show that deterministic 3-quasi-regular sequences always exist (and can be calculated efficiently). We also show that these deterministic 3-regular sequences give rise to a ≈ 1.006-approximation algorithm for the defender's optimal strategy. For 2 ≤ K < 3 we do not know whether deterministic K-quasi-regular sequences always exist; however, when the pi are all small, improved bounds are possible, and in fact, (1 + ∊)-quasi-regular deterministic sequences exist for any ∊ > 0 for sufficiently small pi.

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

We consider multiplayer games in which the players fall in two teams of size k, with payoffs equal within, and of opposite sign across, the two teams. In the classical case of k=1, such zero-sum games possess a unique value, independent of order of play, due to the von Neumann minimax theorem. However, this fails for all k>1; we can measure this failure by a duality gap, which quantifies the benefit of being the team to commit last to its strategy. In our main result we show that the gap equals 2(1-2^{1-k}) for m=2 and 2(1-\m^{-(1-o(1))k}) for m>2, with m being the size of the action space of each player. At a finer level, the cost to a team of individual players acting independently while the opposition employs joint randomness is 1-2^{1-k} for k=2, and 1-\m^{-(1-o(1))k} for m>2. This class of multiplayer games, apart from being a natural bridge between two-player zero-sum games and general multiplayer games, is motivated from Biology (the weak selection model of evolution) and Economics (players with shared utility but poor coordination).

In both general equilibrium theory and game theory, the dominant mathematical models rest on a fully rational solution concept in which every player's action is a best-response to the actions of the other players. In both theories there is less agreement on suitable out- of-equilibrium modeling, but one attractive approach is the level k model in which a level 0 player adopts a very simple response to current conditions, a level 1 player best-responds to a model in which others take level 0 actions, and so forth. (This is analogous to k-ply exploration of game trees in AI, and to receding-horizon control in control theory.) If players have deterministic mental models with this kind of finite-level response, there is obviously no way their mental models can all be consistent. Nevertheless, there is experimental evidence that people act this way in many situations, motivating the question of what the dynamics of such interactions lead to. We address the problem of out-of-equilibrium price dynamics in the setting of Fisher markets. We develop a general framework in which sellers have (a) a set of atomic price update rules which are simple responses to a price vector; (b) a belief-formation procedure that simulates actions of other sellers (themselves using the atomic price updates) to some finite horizon in the future. In this framework, sellers use an atomic price update rule to respond to a price vector they generate with the belief formation procedure. The framework is general and allows sellers to have inconsistent and time- varying beliefs about each other. Under certain assumptions on the atomic update rules, we show that despite the inconsistent and time-varying nature of beliefs, the market converges to a unique equilibrium. (If the price updates are driven by weak-gross substitutes demands, this is the same equilibrium point predicted by those demands.) This result holds for both synchronous and asynchronous discrete-time updates. Moreover, the result is computationally feasible in the sense that the convergence rate is linear, i.e., the distance to equilibrium decays exponentially fast. To the best of our knowledge, this is the first result that demonstrates, in Fisher markets, convergence at any rate for dynamics driven by a plausible model of seller incentives. We then specialize our results to Fisher markets with elastic demands (a further special case corresponds to demand generated by buyers with constant elasticity of substitution (CES) utilities, in the weak gross substitutes (WGS) regime) and show that the atomic update rule in which a seller uses the best-response (=profit- maximizing) update given the prices of all other sellers, satisfies the assumptions required on atomic price update rules in our framework. We can even characterize the convergence rate (as a function of elasticity parameters of the demand function). Our results apply also to settings where, to the best of our knowledge, there exists no previous demonstration of efficient convergence of any discrete dynamic of price updates. Even for the simple case of (level 0) best- response dynamics, our result is the first to demonstrate a linear rate of convergence.

We study a classical iterative algorithm for balancing matrices in the L ∞ norm via a scaling transformation. This algorithm, which goes back to Osborne and Parlett 8 Reinsch in the 1960s, is implemented as a standard preconditioner in many numerical linear algebra packages. Surprisingly, despite its widespread use over several decades, no bounds were known on its rate of convergence. In this article, we prove that, for any irreducible n × n (real or complex) input matrix A , a natural variant of the algorithm converges in O ( n 3 log ( n ρ/ε)) elementary balancing operations, where ρ measures the initial imbalance of A and ε is the target imbalance of the output matrix. (The imbalance of A is |log( a i out / a i in )|, where a i out , a i in are the maximum entries in magnitude in the i th row and column, respectively.) This bound is tight up to the log n factor. A balancing operation scales the i th row and column so that their maximum entries are equal, and requires O ( m / n ) arithmetic operations on average, where m is the number of nonzero elements in A . Thus, the running time of the iterative algorithm is Õ( n 2 m ). This is the first time bound of any kind on any variant of the Osborne-Parlett-Reinsch algorithm. We also prove a conjecture of Chen that characterizes those matrices for which the limit of the balancing process is independent of the order in which balancing operations are performed.

The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any δ > 0 we construct an extractor for O(1/δ) n-bit sources with min-entropy (logn)1+δ. This is most interesting when δ is set to a small constant, though the result also yields an extractor for O(log logn) sources with logarithmic min-entropy. Prior to this work, the best explicit extractor in terms of supporting least-possible min-entropy, due to Li (FOCS'15), requires min-entropy (logn)2+δfrom its O(1/δ) sources. Further, all current techniques for constructing multi-source extractors "break" below min-entropy (log n)2. In fact, existing techniques do not provide even a disperser for o(log n) sources each with min-entropy (log n)1.99. Apart from being a natural problem, supporting logarithmic min-entropy has applications to combinatorics. A two-source disperser, let alone an extractor, for min-entropy O(log n) induces a (log, nO(1))-Ramsey graph on n vertices. Thus, constructing such dispersers would be a significant step towards constructively matching Erdös' proof for the existence of (2log n)-Ramsey graphs on n vertices. Our construction does not rely on the sophisticated primitives that were key to the substantial recent progress on multi-source extractors, such as non-malleable extractors, correlation breakers, the lightest-bin condenser, or extractors for non-oblivious bit-fixing sources, although some of these primitives can be combined with our construction so to improve the output length and the error guarantee. Instead, at the heart of our construction is a new primitive called an independence-preserving merger. The construction of the latter builds on the alternating extraction technique.

We consider the problem of implementing distributed protocols, despite adversarial channel errors, on synchronous-messaging networks with arbitrary topology. In our first result we show that any n-party T-round protocol on an undirected communication network G can be compiled into a robust simulation protocol on a sparse (ℴ(n) edges) subnetwork so that the simulation tolerates an adversarial error rate of ; the simulation has a round complexity of , where m is the number of edges in G. (So the simulation is work-preserving up to a log factor.) The adversary's error rate is within a constant factor of optimal. Given the error rate, the round complexity blowup is within a factor of ℴ(k log n) of optimal, where k is the edge connectivity of G. We also determine that the maximum tolerable error rate on directed communication networks is ⊝(1/s) where s is the number of edges in a minimum equivalent digraph. Next we investigate adversarial per-edge error rates, where the adversary is given an error budget on each edge of the network. We determine the limit for tolerable per-edge error rates on an arbitrary directed graph to within a factor of 2. However, the construction that approaches this limit has exponential round complexity, so we give another compiler, which transforms T-round protocols into ℴ(mT)-round simulations, and prove that for polynomial-query black box compilers, the per-edge error rate tolerated by this last compiler is within a constant factor of optimal.

We study the computational complexity of several natural problems arising in statistical physics and combinatorics. In particular, we consider the following problems: the mean magnetization and mean energy of the Ising model (both the ferromagnetic and the anti-ferromagnetic settings), the average size of an independent set in the hard core model, and the average size of a matching in the monomer-dimer model. We prove that for all non-trivial values of the underlying model parameters, exactly computing these averages is #P-hard. In contrast to previous results of Sinclair and Srivastava (2013) for the mean magnetization of the ferromagnetic Ising model, our approach does not use any Lee-Yang type theorems about the complex zeros of partition functions. Indeed, it was due to the lack of suitable Lee-Yang theorems for models such as the anti-ferromagnetic Ising model that some of the problems we study here were left open by Sinclair and Srivastava. In this paper, we instead use some relatively simple and well-known ideas from the theory of automatic symbolic integration to complete our hardness reductions.

We present a simple and natural non-pricing mechanism for allocating divisible goods among strategic agents having lexicographic preferences. Our mechanism has favorable properties of incentive compatibility (strategy-proofness), Pareto efficiency, envy-freeness, and time efficiency.

We study the problem of learning from unlabeled samples very general statistical mixture models on large finite sets. Specifically, the model to be learned, mix, is a probability distribution over probability distributions p, where each such p is a probability distribution over [n] = {1,2,...,n}. When we sample from mix, we do not observe p directly, but only indirectly and in very noisy fashion, by sampling from [n] repeatedly, independently K times from the distribution p. The problem is to infer mix to high accuracy in transportation (earthmover) distance.

We study a classical iterative algorithm for the problem of balancing matrices in the L∞ norm via a scaling transformation. This algorithm, which goes back to Osborne and Parlett & Reinsch in the 1960s, is implemented as a standard preconditioner in many numerical linear algebra packages. Surprisingly, despite its widespread use over several decades, no bounds were known on its rate of convergence. In this paper we prove that, for a large class of irreducible n x n (real or complex) input matrices~$A$, a natural variant of the algorithm converges in O(n3 log(nρ/ε)) elementary balancing operations, where ρ measures the initial imbalance of A and ε is the target imbalance of the output matrix. (The imbalance of A is maxi |log(aiout/aiin)|, where aiout,aiin are the maximum entries in magnitude in the ith row and column respectively.) This bound is tight up to the log n factor. A balancing operation scales the ith row and column so that their maximum entries are equal, and requires O(m/n) arithmetic operations on average, where m is the number of non-zero elements in A. Thus the running time of the iterative algorithm is ~O(n2m). This is the first time bound of any kind on any variant of the Osborne-Parlett-Reinsch algorithm. The class of matrices for which the above analysis holds are those which satisfy a condition we call Unique Balance, meaning that the limit of the iterative balancing process does not depend on the order in which balancing operations are performed. We also prove a combinatorial characterization of the Unique Balance property, which had earlier been conjectured by Chen.

We consider the task of communicating a data stream-a long, possibly infinite message not known in advance to the sender-over a channel with adversarial noise. For any given noise rate c1/2.

The analysis of network routing games typically assumes, right at the onset, precise and detailed information about the latency functions. Such information may, however, be unavailable or difficult to obtain. Moreover, one is often primarily interested in enforcing a desirable target flow as the equilibrium by suitably influencing player behavior in the routing game. We ask whether one can achieve target flows as equilibria without knowing the underlying latency functions. Our main result gives a crisp positive answer to this question. We show that, under fairly general settings, one can efficiently compute edge tolls that induce a given target multicommodity flow in a nonatomic routing game using a polynomial number of queries to an oracle that takes candidate tolls as input and returns the resulting equilibrium flow. This result is obtained via a novel application of the ellipsoid method, and applies to arbitrary multicommodity settings and non-linear latency functions. Our algorithm extends easily to many other settings, such as (i) when certain edges cannot be tolled or there is an upper bound on the total toll paid by a user, and (ii) general nonatomic congestion games. We obtain tighter bounds on the query complexity for series-parallel networks, and single-commodity routing games with linear latency functions, and complement these with a query-complexity lower bound applicable even to single-commodity routing games on parallel-link graphs with linear latency functions. We also explore the use of Stackelberg routing to achieve target equilibria and obtain strong positive results for series-parallel graphs. Our results build upon various new techniques that we develop pertaining to the computation of, and connections between, different notions of approximate equilibrium, properties of multicommodity flows and tolls in series-parallel graphs, and sensitivity of equilibrium flow with respect to tolls. Our results demonstrate that one can indeed circumvent the potentially-onerous task of modeling latency functions, and yet obtain meaningful results for the underlying routing game.

We propose a new conjecture on some exponential sums. These particular sums have not apparently been considered in the literature. Subject to the conjecture we obtain the first effective construction of asymptotically good tree codes. The available numerical evidence is consistent with the conjecture and is sufficient to certify codes for significant-length communications.

We give an algorithm for learning a mixture of unstructured distributions. This problem arises in various unsupervised learning scenarios, for example in learning topic models from a corpus of documents spanning several topics. We show how to learn the constituents of a mixture of k arbitrary distributions over a large discrete domain [n]={1, 2, ...,n} and the mixture weights, using O(n polylog n) samples. (In the topic-model learning setting, the mixture constituents correspond to the topic distributions.)

We study a generalization of the famous k-center problem where each object is an affine subspace of dimension Δ, and give either the first or significantly improved algorithms and hardness results for many combinations of parameters. This generalization from points (Δ = 0) is motivated by the analysis of incomplete data, a pervasive challenge in statistics: incomplete data objects in ℝd can be modeled as affine subspaces. We give three algorithmic results for different values of k, under the assumption that all subspaces are axis-parallel, the main case of interest because of the correspondence to missing entries in data tables. 1) k = 1: Two polynomial time approximation schemes which runs in poly (Δ, 1/∊)nd. 2) k = 2: O(Δ1/4)-approximation algorithm which runs in poly(n, d, Δ) 3) General k: Polynomial time approximation scheme which runs in We also prove nearly matching hardness results; in both the general (not necessarily axis-parallel) case (for k ≥ 2) and in the axis-parallel case (for k ≥ 3), the running time of an approximation algorithm with any approximation ratio cannot be polynomial in even one of k and Δ, unless P = NP. Furthermore, assuming that the 3-SAT problem cannot be solved sub-exponentially, the dependence on both k and Δ must be exponential in the general case (in the axis-parallel case, only the dependence on k drops to . The simplicity of the first and the third algorithm suggests that they might be actually used in statistical applications. The second algorithm, which demonstrates a theoretical gap between the axis-parallel and general case for k = 2, displays a strong connection between geometric clustering and classical coloring problems on graphs and hypergraphs, via a new Helly-type theorem.

This issue of SICOMP contains eight selected papers from the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010), held June 6--8, 2010, in Cambridge, Massachusetts. The STOC proceedings contained 78 papers, which the program committee selected from 279 submissions. The program committee consisted of Timothy Chan, Ken Clarkson, Constantinos Daskalakis, Irit Dinur, Faith Ellen, Alan Frieze, Parikshit Gopalan, Piotr Indyk, Valentine Kabanets, Yael Tauman Kalai, Howard Karloff, Robert Kleinberg, Assaf Naor, Noam Nisan, Chris Peikert, Jaikumar Radhakrishnan, Oded Regev, Alexander Russell, Leonard Schulman (chair), Aravind Srinivasan, Santosh Vempala, and Andrew Yao. Eight of the STOC papers appear in this special section, each expanded and subjected to the standard thorough reviewing process of the journal. They cover a diverse collection of topics: In “Improving Exhaustive Search Implies Superpolynomial Lower Bounds," R. Ryan Williams shows that there are natural problems in NP and BPP for which algorithms that improve over the naïve deterministic simulation even quite slightly, imply lower bounds such as NEXP $\not\in$ P/poly and LOGSPACE $\neq$ NP. Williams also proves certain unconditional time-space lower bounds for improving on exhaustive search; the length of the witness-string in some standard verification protocol is a key parameter here. In “An Effective Dichotomy for the Counting Constraint Satisfaction Problem," Martin Dyer and David Richerby consider the counting constraint satisfaction problem (\#CSP). This problem asks how many ways there are to satisfy a system of constraints on a set of variables, where a constraint is a relation chosen from a fixed finite set. This class is shown to have a decidable dichotomy, depending on the form of the relations. The dichotomy is that each problem in the class either is in FP or is \#P-complete, with no intermediate cases. In “Pseudorandom Generators for Polynomial Threshold Functions," Raghu Meka and David Zuckerman develop improved (and in many cases the first nontrivial) pseudorandom generators for low-degree polynomial threshold functions; related explicit constructions are also developed. A key ingredient is the use of invariance principles to construct pseudorandom generators. In “Local List-Decoding and Testing of Random Linear Codes from High Error," Swastik Kopparty and Shubhangi Saraf give efficient local list-decoding and testing algorithms for “sparse" random linear codes, and subexponential time algorithms for list-decoding random linear codes, which tolerate error rates approaching $1/2$. In “How to Compress Interactive Communication," Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao attack the important direct sum problem in communication complexity: is the complexity of evaluating $n$ copies of a function ever significantly less than $n$ times the complexity of evaluating it once? By defining a new notion of information cost for protocols --- the so-called internal information cost --- and providing new protocol compression schemes, they prove that computing $n$ copies of any function requires communicating at least $\sqrt{n}$ times as many bits as computing one copy of the function. In “A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations," Daniele Micciancio and Panagiotis Voulgaris provide the first $\exp(O(n))$-time algorithms for the closest vector problem (CVP) and shortest independent vectors problem (SIVP); their algorithm is, moreover, deterministic. Likewise they provide a deterministic algorithm for the shortest vector problem (SVP), whose $\exp(O(n))$ runtime is an improvement over the best known bounds for randomized algorithms. In “Perfect Matchings in $O(n \log n)$ Time in Regular Bipartite Graphs," Ashish Goel, Michael Kapralov, and Sanjeev Khanna provide a randomized algorithm that finds a perfect matching in a $d$-regular $n$-node bipartite graph in time $O(n \log n)$, notably, within time that may be sublinear in the input size and is independent of the degree. In “Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions," Iftach Haitner, Omer Reingold, and Salil Vadhan give a new construction of pseudorandom generators from one-way functions that both simplifies and tightens the acclaimed original construction of Hastad, Impagliazzo, Levin, and Luby. We thank the authors, the STOC program committee, the STOC external reviewers, and the journal referees for all their work to make this special issue possible.

Statistical data frequently includes outliers; these can distort the results of estimation procedures and optimization problems. For this reason, loss functions which deemphasize the effect of outliers are widely used by statisticians. However, there are relatively few algorithmic results about clustering with outliers. For instance, the k-median with outliers problem uses a loss function fc1, …, ck(x) which is equal to the minimum of a penalty h, and the least distance between the data point x and a center ci. The loss-minimizing choice of {c1, …, ck} is an outlier-resistant clustering of the data. This problem is also a natural special case of the k-median with penalties problem considered by [Charikar, Khuller, Mount and Narasimhan SODA'01]. The essential challenge that arises in these optimization problems is data reduction for the weighted k-median problem. We solve this problem, which was previously solved only in one dimension ([Har-Peled FSTTCS'06], [Feldman, Fiat and Sharir FOCS'06]). As a corollary, we also achieve improved data reduction for the k-line-median problem.

We investigate variants of Lloyd's heuristic for clustering high-dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We propose and justify aclusterabilitycriterion for data sets. We present variants of Lloyd's heuristic that quickly lead to provably near-optimal clustering solutions when applied to well-clusterable instances. This is the first performance guarantee for a variant of Lloyd's heuristic. The provision of a guarantee on output quality does not come at the expense of speed: some of our algorithms are candidates for beingfaster in practicethan currently used variants of Lloyd's method. In addition, our other algorithms are faster on well-clusterable instances than recently proposed approximation algorithms, while maintaining similar guarantees on clustering quality. Our main algorithmic contribution is a novel probabilistic seeding process for the starting configuration of a Lloyd-type iteration.

Let X be a space and F a family of 0, 1-valued functions on X. Vapnik and Chervonenkis showed that if F is “simple” (finite VC dimension), then for every probability measure μ on X and ε > 0 there is a finite set S such that for all f ∊ F, σx∊S f(x)/|S| = [∫ f (x)dμ(x)] ± ε. Think of S as a “universal ε-approximator” for integration in F. S can actually be obtained w.h.p. just by sampling a few points from μ. This is a mainstay of computational learning theory. It was later extended by other authors to families of bounded (e.g., [0, 1]-valued) real functions. In this work we establish similar “universal ε-approximators” for families of unbounded nonnegative real functions — in particular, for the families over which one optimizes when performing data classification. (In this case the ε-approximation should be multiplicative.) Specifically, let F be the family of “k-median functions” (or k-means, etc.) on ℝd with an arbitrary norm ϱ. That is, any set u1, …, uk ∊ ℝd determines an f by f(x) = (mini ϱ(x – ui))α. (Here α ≥ 0.) Then for every measure μ on ℝd there exists a set S of cardinality poly(k, d, 1/ε) and a measure ν supported on S such that for every f ∊ F, σx∊S f(x)v(x) ∊ (1 ± ε) · (∫ f(x)dμ(x)).

A set of k balls B 1 , …, B k in a Euclidean space is said to cover a collection of lines if every line intersects some ball. We consider the k - center problem for lines in high-dimensional space: Given a set of n lines l = { l 1 ,…, l n in R d , find k balls of minimum radius which cover l . We present a 2-approximation algorithm for the cases k = 2, 3 of this problem, having running time quasi-linear in the number of lines and the dimension of the ambient space. Our result for 3-clustering is strongly based on a new result in discrete geometry that may be of independent interest: a Helly-type theorem for collections of axis-parallel “crosses” in the plane. The family of crosses does not have finite Helly number in the usual sense. Our Helly theorem is of a new type: it depends on ε-contracting the sets. In statistical practice, data is often incompletely specified; we consider lines as the most elementary case of incompletely specified data points. Clustering of data is a key primitive in nonparametric statistics. Our results provide a way of performing this primitive on incomplete data, as well as imputing the missing values.

There exist finite universal immersion spaces for the following: (a) Edge-colored graphs of bounded degree and boundedly many colors. (b) Nearest-neighbor metrics of bounded degree and boundedly many edge lengths.

Systems with automatic feedback control may consist of several remote devices, connected only by unreliable communication channels. It is necessary in these conditions to have a method for accurate, real-time state estimation in the presence of channel noise. This problem is addressed, for the case of polynomial-growth-rate state spaces, through a new type of error-correcting code that is online and computationally efficient. This solution establishes a constructive analog, for some applications in estimation and control, of the Shannon coding theorem.

The Vehicle Routing Problem (VRP) is a discrete optimization problem with high industrial relevance and high computational complexity. The problem has been extensively studied since it was introduced by Dantzig and Ramser. In this paper, we present a version of the VRP motivated by mobile sensor networks which we call the Capacitated Multivehicle Routing Problem (CMVRP). Our objective is to determine the minimum amount of energy required to serve all jobs, which takes into account both the service requirement and the travel overhead. We present a constant factor approximation algorithm for the off-line case and a distributed algorithm for the on-line problem that uses only a constant factor more energy than the off-line solution.

In this paper we obtain improved upper and lower bounds for the best approximation factor for Sparsest Cut achievable in the cut-matching game framework proposed in Khandekar et al. [9]. We show that this simple framework can be used to design combinatorial algorithms that achieve O(log n) approximation factor and whose running time is dominated by a poly-logarithmic number of single-commodity max-flow computations. This matches the performance of the algorithm of Arora and Kale [2]. Moreover, we also show that it is impossible to get an approximation factor of better than Ω(√log n) in the cut-matching game framework. These results suggest that the simple and concrete abstraction of the cut-matching game may be powerful enough to capture the essential features of the complexity of Sparsest Cut.

The dramatic exponential speedups of quantum algorithms over their best existing classical counterparts were ushered in by the technique of Fourier sampling, introduced by Bernstein and Vazirani and developed by Simon and Shor into an approach to the hidden subgroup problem. This approach has proved successful for abelian groups, leading to efficient algorithms for factoring, extracting discrete logarithms, and other number-theoretic problems. We show, however, that this method cannot resolve the hidden subgroup problem in the symmetric groups, even in the weakest, information-theoretic sense. In particular, we show that the Graph Isomorphism problem cannot be solved by this approach. Our work implies that any quantum approach based upon the measurement of coset states must depart from the original framework by using entangled measurements on multiple coset states.

Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonAbelian hidden subgroup problem, which generalizes the central problem solved by Shor's factoring algorithm. We suggest an alternative generalization, namely to problems of finding hidden nonlinear structures over finite fields. We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures.

We show that, given data from a mixture of k well-separated spherical Gaussians in ℜd, a simple two-round variant of EM will, with high probability, learn the parameters of the Gaussians to near-optimal precision, if the dimension is high (d >> ln k). We relate this to previous theoretical and empirical work on the EM algorithm.

Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which an unknown subgroup H of a group G must be determined from a quantum state $\psi$ over G that is uniformly supported on a left coset of H. These hidden subgroup problems are typically solved by Fourier sampling: the quantum Fourier transform of $\psi$ is computed and measured. When the underlying group is nonabelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement (i.e., the row and column of the representation, in a suitably chosen basis, as well as its name) occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups H of the q-hedral groups, i.e., semidirect products ${\mathbb Z}_q \ltimes {\mathbb Z}_p$, where $q \mid (p-1)$, and in particular the affine groups $A_p$, can be information-theoretically reconstructed using the strong standard method. Moreover, if $|H| = p/ {\rm polylog}(p)$, these subgroups can be fully reconstructed with a polynomial amount of quantum and classical computation. We compare our algorithms to two weaker methods that have been discussed in the literature—the “forgetful” abelian method, and measurement in a random basis—and show that both of these are weaker than the strong standard method. Thus, at least for some families of groups, it is crucial to use the full power of representation theory and nonabelian Fourier analysis, namely, to measure the high-dimensional representations in an adapted basis that respects the group's subgroup structure. We apply our algorithm for the hidden subgroup problem to new families of cryptographically motivated hidden shift problems, generalizing the work of van Dam, Hallgren, and Ip on shifts of multiplicative characters. Finally, we close by proving a simple closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.

Simultaneous near‐certain preparation of qubits (quantum bits) in their ground states is a key hurdle in quantum computing proposals as varied as liquid‐state NMR and ion traps. “Closed‐system” cooling mechanisms are of limited applicability due to the need for a continual supply of ancillas for fault tolerance and to the high initial temperatures of some systems. “Open‐system” mechanisms are therefore required. We describe a new, efficient initialization procedure for such open systems. With this procedure, an n‐qubit device that is originally maximally mixed, but is in contact with a heat bath of bias $\varepsilon \gg 2^{-n}$, can be almost perfectly initialized. This performance is optimal due to a newly discovered threshold effect: For bias $\varepsilon \ll 2^{-n}$ no cooling procedure can, even in principle (running indefinitely without any decoherence), significantly initialize even a single qubit.

We investigate variants of Lloyd's heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We propose and justify a clusterability criterion for data sets. We present variants of Lloyd's heuristic that quickly lead to provably near-optimal clustering solutions when applied to well-clusterable instances. This is the first performance guarantee for a variant of Lloyd's heuristic. The provision of a guarantee on output quality does not come at the expense of speed: some of our algorithms are candidates for being faster in practice than currently used variants of Lloyd's method. In addition, our other algorithms are faster on well-clusterable instances than recently proposed approximation algorithms, while maintaining similar guarantees on clustering quality. Our main algorithmic contribution is a novel probabilistic seeding process for the starting configuration of a Lloyd-type iteration

We prove that if a linear error-correcting code C:{0, 1} n →{0, 1} m is such that a bit of the message can be probabilistically reconstructed by looking at two entries of a corrupted codeword, then m = 2Ω (n). We also present several extensions of this result. We show a reduction from the complexity of one-round, information-theoretic Private Information Retrieval Systems (with two servers) to Locally Decodable Codes, and conclude that if all the servers’ answers are linear combinations of the database content, then t = Ω (n/2 a ), where t is the length of the user’s query and a is the length of the servers’ answers. Actually, 2 a can be replaced by O(a k ), where k is the number of bit locations in the answer that are actually inspected in the reconstruction.

Device initialization is a difficult challenge in some proposed realizations of quantum computers, and as such, must be treated as a computational resource. The degree of initialization can be quantified by k , the number of clean qubits in the initial state of the register. In this article, we show that unless m ∈ O ( k + log n ), oblivious (gate-by-gate) simulation of an ideal m -qubit quantum circuit by an n -qubit circuit with k clean qubits is impossible. Effectively, this indicates that there is no avoiding physical initialization of a quantity of qubits proportional to that required by the best ideal quantum circuit.

We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem in general groups. Specifically, we show that the hidden subgroup problem in the symmetric group cannot be efficiently solved by strong Fourier sampling. Indeed we prove the stronger statement that no measurement of a single coset state can reveal more than an exponentially small amount of information about the identity of the hidden subgroup, in the special case relevant to the graph isomorphism problem.

In many control-theory applications one can classify all possible states of the device by an infinite state graph with polynomially-growing expansion. In order for a controller to control or estimate the state of such a device, it must receive reliable communications from its sensors; if there is channel noise, the encoding task is subject to a stringent real-time constraint. We show a constructive on-line error correcting code that works for this class of applications. Our code is computationally efficient and enables on-line estimation and control in the presence of channel noise. It establishes a constructive (and optimal-within-constants) analog, for control applications, of the Shannon coding theorem.

We consider a multiple access channel shared by two sources. The channel is noiseless but there is interference between the transmissions of the sources. Because of applications to distributed control we are interested in the real-time version of this problem, in which the receiver must act immediately upon received information. Block coding is therefore not possible, and error probability cannot generally be made to tend to 0 in the interior of the multiple access capacity region. We study code design for a simple class of XOR channels. We provide several computationally efficient design methods. Under an assumption on the form of the correlation among the sources, one of these algorithms provides codes whose success probability is within 2/3 of optimal. In the absence of assumptions on the correlation, optimal code design is NP-hard

Queueing is a crucial component in effective router congestion control. If packets are dropped indiscriminately by the queueing system, in some cases, the effect can be to encourage senders to actually increase their transmission rates, worsening the congestion and destabilizing the system.We approach this congestion problem from the point of view of the elementary concepts of game theory and control theory. We provide a queueing mechanism with feedback-control. Our analysis shows that the protocol achieves high throughput as well as fairness in allocating capacity among sources, while maintaining bounded queue lengths and responding dynamically to changes in network flow conditions. Perhaps most importantly, the new protocol is shown in network simulations to have superior ability (compared with previous solutions) to protect responsive flows (specifically TCP) against router flooding by multiple high-volume unresponsive (e.g., UDP) flows.

We present a new algorithm for fixed-rate vector quantizer (VQ) design with deterministic data net. The algorithm also performs efficient VQ design for simply characterized continuous distributions. The algorithm also serves as an approximation algorithm for the d-dimensional fixed-rate operational distortion-rate function, extends to a variety of network VQ problems. The algorithm generalizes to give /spl epsiv/-approximation algorithms for many network VQ design problems. A few examples are multiresolution VQ (MRVQ), multiple description VQ (MDVQ), side information VQ (SIVQ), Broadcast VQ (BCVQ), joint source-channel VQ (JSCVQ) and remote source VQ (RSVQ).

Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function $f: X \times Y \rightarrow \{0,1\}$ and a probability distribution ${\cal D}$ over $X \times Y$, we define the sampling complexity of $(f, {\cal D})$ as the minimum number of bits that Alice and Bob must communicate for Alice to pick $x \in X$ and Bob to pick $y \in Y$ as well as a value z such that the resulting distribution of $(x,y,z)$ is close to the distribution $({\cal D}, f({\cal D}))$. In this paper we initiate the study of sampling complexity, in both the classical and quantum models. We give several variants of a definition. We completely characterize some of these variants and give upper and lower bounds on others. In particular, this allows us to establish an exponential gap between quantum and classical sampling complexity for the set-disjointness function.

We determine the precise threshold of component noise below which formulas composed of odd degree components can reliably compute all Boolean functions.

We provide positive and negative results concerning the “standard method” of identifying a hidden subgroup of a nonabelian group using a quantum computer.

We consider quantum computing in the one-qubit model where the starting state of a quantum computer consists of k qubits in a pure state and n − k qubits in a maximally mixed state. We ask the following question: is there a general method for simulating an arbitrary m-qubit pure state quantum computation by a quantum computation in the k-qubit model? We show that, under certain constraints, this is impossible, unless m = O(k + log n). 1.

We provide an $O(n^2 \log {1 \over \delta})$ time randomized algorithm to check whether a given operation $\circ :S \times S \rightarrow S$ is associative (where $n=|S|$ and $\delta>0$ is the error probability required of the algorithm). We prove that (for any constant $\delta$) this performance is optimal up to a constant factor, even if the operation is "cancellative." No sub-$n^3$ time algorithm was previously known for this task. More generally we give an $O(n^c)$ time randomized algorithm to check whether a collection of c-ary operations satisfy any given "read-once" identity.

A key step in counting via sampling is constructing an onbiased estimator, X, for the parameter .9 in question, and proving a bound on its second moment, E(X').A key applacation of this method is to obtaining a FPRAS for a #Pcomplete problem; a FPRAS results if the ratio r = m EIW is polynamially bounded in the size of the input.We show that if no additional information is available about the dis tribution of X, then this condition is also necessary.The proof involves establishing a new optimality result in parametric statistics.We introduce the notion of a majorizing estimator, a very strict optimality requirement that we need for making wont-case (over inputs) and in-probability (of falling in the desired accuracy range of the parameter 8) statements.We show that for the problem of estimating the mean of a Gaussian distribution (from the variable-location, fixed-scale family {GB}), the sample mean is a majorizing estimator.An extension of this argument shows that the sample mean is an optimal estimator in every central moment among all estimators.To compare, the celebrated Cramer-Rae lower bound, applied to the family {CS}, establishes that the sample mean is the optimal estimator in mean square error among alI unbiased estimators.We fixther show that the mean estimator is the unique majorizing estimator for {Ge}.

We describe a quantum mechanical heat engine.Like its classical counterpart introduced by Carnot, this entine carries out a reversible process in which an input of energy to the system results in a separation of cold and hot regions.The method begins with a reinterpretation in thermodynamic terms of a simple step introduced by van Neumann to extract fair coin flips from sequences of biased coin flips.Some of the experimental set-ups proposed for implementation of quantum computers, begin with the quantum bits of the computer initially in a mixed state.Each qubit is L polarized -in the state IO) with probability 9, and in the state 11) with probability *, independently (or nearly so) of all other bits.The heat engine may be used to trans.form this initial collection of n qubits into a state in which a near-optimal m = n[ FIg(l +e) + %Ig(l -c) -o(l)] qubits are in the joint state IO"').These qubits can then be used as the register for a quantum computation.The heat engine is described at the level of an algorithm implementable in any quantum system capable of massive coherent states.A particular implementation is also described for a system of nuclear spins arranged in a chain.The temperature the cold qubits reach is inverse polynomial in n.

The information carried by a signal decays when the signal is corrupted by random noise. This occurs when a message is transmitted over a noisy channel, as well as when a noisy component performs computation. We first study this signal decay in the context of communication and obtain a tight bound on the rate at which information decreases as a signal crosses a noisy channel. We then use this information theoretic result to obtain depth lower bounds in the noisy circuit model of computation defined by von Neumann. In this model, each component fails (produces 1 instead of 0 or vice-versa) independently with a fixed probability, and yet the output of the circuit is required to be correct with high probability. Von Neumann showed how to construct circuits in this model that reliably compute a function and are no more than a constant factor deeper than noiseless circuits for the function. We provide a lower bound on the multiplicative increase in circuit depth necessary for reliable computation, and an upper bound on the maximum level of noise at which reliable computation is possible.

We present simple, polynomial time encodable and decodable codes which are asymptotically good for channels allowing insertions, deletions, and transpositions. As a corollary, they achieve exponential error probability in a stochastic model of insertion-deletion.

Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f: X/spl times/Y/spl rarr/{0,1} and a probability distribution D over X/spl times/Y, we define the sampling complexity of (f,D) as the minimum number of bits Alice and Bob must communicate for Alice to pick x/spl isin/X and Bob to pick y/spl isin/Y as well as a valve z s.t. the resulting distribution of (x,y,z) is close to the distribution (D,f(D)). In this paper we initiate the study of sampling complexity, in both the classical and quantum model. We give several variants of the definition. We completely characterize some of these tasks, and give upper and lower bounds on others. In particular this allows us to establish an exponential gap between quantum and classical sampling complexity, for the set disjointness function. This is the first exponential gap for any task where the classical probabilistic algorithm is allowed to err.

Two sets of points in d-dimensional space are given: a data set D consisting of N points, and a pattern set or probe P consisting of k points. We address the problem of determining whether there is a transformation, among a specified group of transformations of the space, carrying P into or near (meaning at a small directed Hausdorff distance of) D. The groups we consider are translations and rigid motions. Runtimes of approximately O(nlogn) and O(n/sup d/logn) respectively are obtained (letting n=max{N,k} and omitting the effects of several secondary parameters). For translations, a runtime of approximately O(n(ak+1)log/sup 2/n) is obtained for the case that a constant fraction /spl alpha/<1 of the points of the probe is allowed to fail to match.

A basic task in distributed computation is the maintenance at each processor of the network, of a current and accurate copy of a common database. A primary example is the maintenance, for routing and other purposes, of a record of the current topology of the system. Such a database must be updated in the wake of locally generated changes to its contents. Due to previous disconnections of parts of the network, a maintenance protocol may need to update processors holding widely varying versions of the database. We provide a deterministic protocol for this problem, with only polylogarithmic overhead in both time and communication complexities. Previous deterministic solutions required polynomial overhead in at least one of these measures.

The authors provide an O/spl tilde/(n/sup 2/) time randomized algorithm to check whether a given operation f:S/spl times/S/spl rarr/S is associative (letting n=|S|). They prove this performance is optimal (up to polylogarithmic factors) even in case the operation is "cancellative". No sub-n/sup 3/ algorithm was previously known for this task. More generally they give an O(n/sup c/) time randomized algorithm to check whether a collection of c-ary operations satisfy any given "read-once" identity.

Let the input to a computation problem be split between two processors connected by a communication link; and let an interactive protocol /spl pi/ be known by which, on any input, the processors can solve the problem using no more than T transmissions of bits between them, provided the channel is noiseless in each direction. We study the following question: if in fact the channel is noisy, what is the effect upon the number of transmissions needed in order to solve the computation problem reliably? Technologically this concern is motivated by the increasing importance of communication as a resource in computing, and by the tradeoff in communications equipment between bandwidth, reliability, and expense. We treat a model with random channel noise. We describe a deterministic method for simulating noiseless-channel protocols on noisy channels, with only a constant slowdown. This is an analog for general, interactive protocols of Shannon's coding theorem, which deals only with data transmission, i.e., one-way protocols. We cannot use Shannon's block coding method because the bits exchanged in the protocol are determined only one at a time, dynamically, in the course of the interaction. Instead, we describe a simulation protocol using a new kind of code, explicit tree codes.

We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n,k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2/sup k/ configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal /spl Sigma/II/spl Sigma/ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits.

Shannon's Coding Theorem shows that in order to reliably transmit a message of T bits over a noisy communication channel, only a constant slowdown factor is necessary in the case when the channel is noisy, relative to the case in which the channel is noiseless. (The time required is asymptotically C , where 0 ! C 1 is the "Shannon capacity", a function only of the noise characteristics.) The theorem ensures that the probability of a decoding error is exponentially small in the message length T . Recently the second author obtained an analogous result for arbitrary interactive communication protocols between two processors. In the present

We study the decay of an information signal propagating through a series of noisy channels. We obtain exact bounds on such decay, and as a result provide a new lower bound on the depth of formulas with noisy components. This improves upon previous work of N. Pippenger (1988) and significantly decreases the gap between his lower bound and the classical upper bound of von Neumann. We also discuss connections between our work and the study of mixing rates of Markov chains.>

Article Deterministic coding for interactive communication Share on Author: Leonard J. Schulman View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 747–756https://doi.org/10.1145/167088.167279Online:01 June 1993Publication History 51citation521DownloadsMetricsTotal Citations51Total Downloads521Last 12 Months48Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Randomized algorithms for two sorting problems are presented. In the local sorting problem, a graph is given in which each vertex is assigned an element of a total order, and the task is to determine the relative order of every pair of adjacent vertices. In the set-maxima problem, a collection of sets whose elements are drawn from a total order is given, and the task is to determine the maximum element in each set. Lower bounds for the problems in the comparison model are described and it is shown that the algorithms are optimal within a constant factor.

Communication is critical to distributed computing, parallel computing, or any situation in which automata interact-hence its significance as a resource in computation. In view of the likelihood of errors occurring in a lengthy interaction, it is desirable to incorporate this possibility in the model of communication. The author relates the noisy channel and the standard (noise less channel) complexities of a communication problem by establishing a 'two-way' or interactive analogue of Shanon's coding theorem: every noiseless channel protocol can be simulated by a private-coin noisy channel protocol whose time bound is proportional to the original (noiseless) time bound and inversely proportional to the capacity of the channel, while the protocol errs with vanishing probability. The method involves simulating the original protocol while implementing a hierarchical system of progress checks which ensure that errors of any magnitude in the simulation are, with high probability, rapidly eliminated.>

Let a universe of m elements be given, along with a family of subsets of the universe (neighborhoods), each of size at most k. We describe methods for assigning the m elements to points in a small-dimensional vector space (over GF(2)), in such a way that the elements in each neighborhood are assigned to an independent set of vectors.

Given n points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally.We show that any n points in general position possess a crossing family of size at least ~, and describe an O(n log n)-time algorithm for finding one.

A basic task in distributed computation is the maintenance at each processor of the network, of a current and accurate copy of a common database. Such a database must be updated in the wake of locally generated changes to its contents. Due to previous disconnections of parts of the network, a maintenance protocol may need to update processors holding widely varying versions of the database. A deterministic protocol, which has only polylogarithmic overhead in its time and communication complexities, is provided for this problem. Previous deterministic solutions required polynomial overhead in at least one of these measures.>

We present randomized algorithms for two sorting problems.In the local sorting problem, a graph is given in which each vertex is assigned an element of a total order, and the task is to determine the relative order in every pair of adjacent vertices.In the set-maxima problem, a collection of sets whose elements are drawn from a total order is given, and the task is to determine the maximum element in each set.We describe lower bounds for the problems in the comparison model, and show that the algorithms are optimal within a constant factor.