Marcus, Spielman and Srivastava (Annals of Mathematics 2014) solved the Kadison-Singer Problem by proving a strong form of Weaver’s conjecture: they showed that for all α > 0 and all lists of vectors of norm at most √α whose outer products sum to the identity, there exists a signed sum of those outer products with operator norm at most √{8α} + 2α. We prove that it is NP-hard to distinguish such a list of vectors for which there is a signed sum that equals the zero matrix from those in which every signed sum has operator norm at least η √α, for some absolute constant η > 0. Thus, it is NP-hard to construct a signing that is a constant factor better than that guaranteed to exist. For α = 1/4, we prove that it is NP-hard to distinguish whether there is a signed sum that equals the zero matrix from the case in which every signed sum has operator norm at least 1/4.

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on an analysis of the expected characteristic polynomial of a union of random perfect matchings and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real-rooted and that the family of polynomials considered in this sum is an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions introduced recently by the authors.

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process. We use these new algorithms to derive the first nearly linear time algorithms for solving systems of equations in connection Laplacians---a generalization of Laplacian matrices that arise in many problems in image and signal processing. We also prove that every connection Laplacian has a linear sized approximate inverse. This is an LU factorization with a linear number of nonzero entries that is a strong approximation of the original matrix. Using such a factorization one can solve systems of equations in a connection Laplacian in linear time. Such a factorization was unknown even for ordinary graph Laplacians.

We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large p of p-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in expected time \widetildeO (m n). The latter algorithm has variants that seem to run much faster in practice. These extensions are particularly amenable to regularization: we can perform l_0-regularization on the given values in polynomial time and l_1-regularization on the initial function values and on graph edge weights in time \widetildeO (m^3/2). Our definitions and algorithms naturally extend to directed graphs.

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on analyzing the expected characteristic polynomial of a union of random perfect matchings, and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real rooted and that the family of polynomials considered in this sum is an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions introduced recently by the authors.

We present the first parallel algorithm for solving systems of linear equations in symmetric, diagonally dominant (SDD) matrices that runs in polylogarithmic time and nearly-linear work. The heart of our algorithm is a construction of a sparse approximate inverse chain for the input matrix: a sequence of sparse matrices whose product approximates its inverse. Whereas other fast algorithms for solving systems of equations in SDD matrices exploit low-stretch spanning trees, our algorithm only requires spectral graph sparsifiers.

We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c, d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by √c-1+√d-1, for all c, d ≥ q 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials".

This section of SIAM Journal on Computing contains extended versions of selected papers from the 50th Annual Symposium on Foundations of Computer Science, sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing. The conference was held in Atlanta, Georgia, October 24--27, 2009, at the Renaissance Atlanta Hotel Downtown. The program committee consisted of Sanjeev Arora, Maria Florina Balcan, Boaz Barak, Mark Braverman, Amit Chakrabarti, Ken Clarkson, Alon Efrat, Martin Fürer, Anna Gilbert, Phil Klein, Ming Li, Mihai Pătraşcu, Dana Ron, Tim Roughgarden, Daniel Spielman, Mario Szegedy, Kunal Talwar, Eli Upfal, Umesh Vazirani, Vijay Vazirani, and Berthold Vöcking. They accepted 75 papers from 249 submissions. We briefly describe the papers that appear here. In “On the Power of Randomization in Algorithmic Mechanism Design,” Shahar Dobzinski and Shaddin Dughmi analyze multi-unit auctions to show that truthfulness in expectation is more powerful than universal truthfulness. In “Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers,” Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan strengthen Dvir's proof of the Kakeya conjecture for finite fields. In “The Intersection of Two Halfspaces Has High Threshold Degree,” Alexander Sherstov proves a lower bound on the degree of polynomials whose signs agree with the conjunction of two threshold functions. This implies a lower bound on the complexity of using perceptron-type algorithms to learn such functions. In “KKL, Kruskal--Katona, and Monotone Nets,” Ryan O'Donnell and Karl Wimmer prove isoperimetric theorems for Cayley and Schreier graphs and give applications of their results to combinatorics and learning theory. In “Vertex Sparsification and Oblivious Reductions,” Ankur Moitra proves that one can approximate the values of all flows between a small number of terminals in a large graph by constructing a much smaller graph and measuring the values of flows in the smaller graph. In “Dynamic and Nonuniform Pricing Strategies for Revenue Maximization,” Tanmoy Chakraborty, Zhiyi Huang, and Sanjeev Khanna show that dynamic nonuniform pricing strategies can achieve significantly higher expected revenue than does static uniform pricing. In “Composition of Low-Error 2-Query PCPs Using Decodable PCPs,” Irit Dinur and Prahladh Harsha simplify Moshkovitz and Raz's construction of low-error 2-query probabilistically checkable proofs. In “A Parallel Repetition Theorem for Any Interactive Argument,” Iftach Haitner shows that, after a slight modification, the soundness error of any interactive argument can be decreased through parallel repetition.

We study the design of local algorithms for massive graphs. A local graph algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster---a subset of vertices whose internal connections are significantly richer than its external connections---near a given vertex. The running time of our algorithm, when it finds a nonempty local cluster, is nearly linear in the size of the cluster it outputs. The running time of our algorithm also depends polylogarithmically on the size of the graph and polynomially on the conductance of the cluster it produces. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph. Using the partitioning algorithm of this paper, we have designed a nearly linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly linear time algorithm for solving linear systems in symmetric, diagonally dominant matrices. The linear system solver also leads to a nearly linear time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers.

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every $d>1$ and every undirected, weighted graph $G=(V,E,w)$ on $n$ vertices, there exists a weighted graph $H=(V,F,\tilde{w})$ with at most $\lceil d(n-1)\rceil$ edges such that for every $x\in\mathbb{R}^{V}$, $x^{T}L_{G}x\leq x^{T}L_{H}x\leq\bigl(\frac{d+1+2\sqrt{d}}{d+1-2\sqrt{d}}\bigr)\cdot x^{T}L_{G}x$, where $L_{G}$ and $L_{H}$ are the Laplacian matrices of $G$ and $H$, respectively. Thus, $H$ approximates $G$ spectrally at least as well as a Ramanujan expander with $dn/2$ edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing $H$.

We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges, our algorithm computes a (1-ε)-approximately maximum s-t flow in time ~O(mn1/3ε-11/3). A dual version of our approach gives the fastest known algorithm for computing a (1+ε)-approximately minimum s-t cut. It takes ~O(m+n4/3ε-16/3) time. Previously, the best dependence on m and n was achieved by the algorithm of Goldberg and Rao (J. ACM 1998), which can be used to compute approximately maximum s-t flows in time ~O({m√nε-1), and approximately minimum s-t cuts in time ~O(m+n3/2ε-3).

We present a nearly linear time algorithm that produces high-quality spectral sparsifiers of weighted graphs. Given as input a weighted graph $G=(V,E,w)$ and a parameter $\epsilon>0$, we produce a weighted subgraph $H=(V,\tilde{E},\tilde{w})$ of G such that $|\tilde{E}|=O(n\log n/\epsilon^2)$ and all $x\in\mathbb{R}^V$ satisfy $(1-\epsilon)\sum_{uv\in E}\,(x(u)-x(v))^2w_{uv}\leq\sum_{uv\in\tilde{E}}\,(x(u)-x(v))^2\tilde{w}_{uv}\leq(1+\epsilon)\sum_{uv\in E}\,(x(u)-x(v))^2w_{uv}$. This improves upon the spectral sparsifiers constructed by Spielman and Teng, which had $O(n\log^{c}n)$ edges for some large constant c, and upon the cut sparsifiers of Benczúr and Karger, which only satisfied these inequalities for $x\in\{0,1\}^V$. A key ingredient in our algorithm is a subroutine of independent interest: a nearly linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in $O(\log n)$ time.

We introduce a new notion of graph sparsification based on spectral similarity of graph Laplacians: spectral sparsification requires that the Laplacian quadratic form of the sparsifier approximate that of the original. This is equivalent to saying that the Laplacian of the sparsifier is a good preconditioner for the Laplacian of the original. We prove that every graph has a spectral sparsifier of nearly linear size. Moreover, we present an algorithm that produces spectral sparsifiers in time $O(m\log^{c}m)$, where m is the number of edges in the original graph and c is some absolute constant. This construction is a key component of a nearly linear time algorithm for solving linear equations in diagonally dominant matrices. Our sparsification algorithm makes use of a nearly linear time algorithm for graph partitioning that satisfies a strong guarantee: if the partition it outputs is very unbalanced, then the larger part is contained in a subgraph of high conductance.

We introduce a measure of how well a combinatorial graph fits a collection of vectors. The optimal graphs under this measure may be computed by solving convex quadratic programs and have many interesting properties. For vectors in d dimensional space, the graphs always have average degree at most 2(d+1), and for vectors in 2 dimensions they are always planar. We compute these graphs for many standard data sets and show that they can be used to obtain good solutions to classification, regression and clustering problems. 1.

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every d > 1 and every undirected, weighted graph G = (V,E,w) on n vertices, there exists a weighted graph H=(V,F,~{w}) with at most ⌈d(n-1)⌉ edges such that for every x ∈ RV, [xT LG x ≤ xT LH x ≤ ((d+1+2√d)/(d+1-2√d)) • xT LG x] where LG and LH are the Laplacian matrices of G and H, respectively. Thus, H approximates G spectrally at least as well as a Ramanujan expander with dn/2 edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing H.

Worst-case upper bounds are derived on the minimum distance of parallel concatenated turbo codes, serially concatenated convolutional codes, repeat-accumulate codes, repeat-convolute codes, and generalizations of these codes obtained by allowing nonlinear and large-memory constituent codes. It is shown that parallel-concatenated turbo codes and repeat-convolute codes with sub-linear memory are asymptotically bad. It is also shown that depth-two serially concatenated codes with constant-memory outer codes and sublinear-memory inner codes are asymptotically bad. Most of these upper bounds hold even when the convolutional encoders are replaced by general finite-state automata encoders. In contrast, it is proven that depth-three serially concatenated codes obtained by concatenating a repetition code with two accumulator codes through random permutations can be asymptotically good.

We present asymptotically faster approximation algorithms for the generalized flow problems in which multipliers on edges are at most 1. For this lossy version of the maximum generalized flow problem, we obtain an additive ε approximation of the maximum flow in time O{m3/2 log (U/ε)2}, where m is the number of edges in the graph, all capacities are integers in the range {1, ... , U}, and all loss multipliers are ratios of integers in this range. For minimum cost lossy generalized flow with costs in the range {1,... ,U}, we obtain a flow that has value within an additive ε of the maximum value and cost at most the optimal cost. In many parameter ranges, these algorithms improve over the previously fastest algorithms for the generalized maximum flow problem by a factor of m1/2 and for the minimum cost generalized flow problem by a factor of approximately m1/2/ ε2. The algorithms work by accelerating traditional interior point algorithms by quickly solving the system of linear equations that arises in each step. The contributions of this paper are twofold. First, we analyze the performance of interior point algorithms with approximate linear system solvers. This analysis alone provides an algorithm for the standard minimum cost flow problem that runs in time Om3/2 log U}--an improvement of roughly O{n / m1/2} over previous algorithms. Second, we examine the linear equations that arise when using an interior point algorithm to solve generalized flow problems. We observe that these belong to the family of symmetric M-matrices, and we then develop Om-time algorithms for solving linear systems in these matrices. These algorithms reduce the problem of solving a linear system in a symmetric M-matrix to that of solving O{log n} linear systems in symmetric diagonally-dominant matrices, which we can do in time Om using the algorithm of Spielman and Teng. All of our algorithms operate on numbers of bit length at most O{log n U / ε}.

We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph G=(V,E,w) and a parameter ε>0, we produce a weighted subgraph H=(V,~E,~w) of G such that |~E|=O(n log n/ε2) and for all vectors x in RV. (1-ε) ∑uv ∈ E (x(u)-x(v))2wuv≤ ∑uv in ~E(x(u)-x(v))2~wuv ≤ (1+ε)∑uv ∈ E(x(u)-x(v))2wuv. This improves upon the sparsifiers constructed by Spielman and Teng, which had O(n logc n) edges for some large constant c, and upon those of Benczur and Karger, which only satisfied (1) for x in {0,1}V. We conjecture the existence of sparsifiers with O(n) edges, noting that these would generalize the notion of expander graphs, which are constant-degree sparsifiers for the complete graph. A key ingredient in our algorithm is a subroutine of independent interest: a nearly-linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in O(log n) time.

We show that every weighted connected graph G contains as a subgraph a spanning tree into which the edges of G can be embedded with average stretch $O (\log^{2} n \log \log n)$. Moreover, we show that this tree can be constructed in time $O (m \log n + n \log^2 n)$ in general, and in time $O (m \log n)$ if the input graph is unweighted. The main ingredient in our construction is a novel graph decomposition technique. Our new algorithm can be immediately used to improve the running time of the recent solver for symmetric diagonally dominant linear systems of Spielman and Teng from $ m 2^{(O (\sqrt{\log n\log\log n})) }$ to $m \log^{O (1)}n$, and to $O ( n \log^{2} n \log \log n)$ when the system is planar. Our result can also be used to improve several earlier approximation algorithms that use low-stretch spanning trees.

Spectral graph theory is the study of the eigenvalues and eigenvectors of matrices associated with graphs. In this tutorial, we will try to provide some intuition as to why these eigenvectors and eigenvalues have combinatorial significance, and will sitn'ey some of their applications.

We present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input.We begin by reducing the input linear program to a special form in which we merely need to certify boundedness. As boundedness does not depend upon the right-hand-side vector, we run the shadow-vertex simplex method with a random right-hand-side vector. Thus, we do not need to bound the diameter of the original polytope.Our analysis rests on a geometric statement of independent interest: given a polytope A x ≤ b in isotropic position, if one makes a polynomially small perturbation to b then the number of edges of the projection of the perturbed polytope onto a random 2-dimensional subspace is expected to be polynomial.

Spielman and Teng (JACM '04), proved that the smoothed complexity of a two-phase shadow-vertex method for linear programming is polynomial in the number of constraints n, the number of variables d, and the parameter of perturbation 1//spl sigma/. The key geometric result in their proof was an upper bound of O(nd/sup 3//min (/spl sigma/, (9d ln n)/sup 1/2 /)/sup 6/) on the expected size of the shadow of the polytope defined by the perturbed linear program. In this paper, we give a much simpler proof of a better bound: O(n/sup 2/ d ln n/min (/spl sigma/, (4d ln n)/sup 1/2 /)/sup 2/). When evaluated at /spl sigma/ = (9d ln n)/sup 1/2 /, this improves the size estimate from O(nd/sup 6/ ln/sup 3/ n) to O(n/sup 2/d/sup 2/ ln n). The improvement only becomes better as /spl sigma/ decreases. The bound on the running time of the two-phase shadow vertex proved by Spielman and Teng is dominated by the exponent of /spl sigma/ in the shadow-size bound. By reducing this exponent from 6 to 2, we decrease the exponent in the smoothed complexity of the two-phase shadow vertex method by a multiplicative factor of 3.

We show that every weighted connected graph G contains as a subgraph a spanning tree into which the edges of G can be embedded with average stretch O (log2 n log log n). Moreover, we show that this tree can be constructed in time O (m log2n) in general, and in time O (mlog n) if the input graph is unweighted. The main ingredient in our construction is a novel graph decomposition technique.Our new algorithm can be immediately used to improve the running time of the recent solver for symmetric diagonally dominant linear systems of Spielman and Teng from m2(O√lognlog log n) to m log O(1)n and to O (n log2n log log n) when the system is planar. Our result can also be used to improve several earlier approximation algorithms that use low-stretch spanning trees.

An effective method in practice to compute quality Delaunay triangulations is to apply parallel refinements that insert Steiner points whose prestars in the triangulation do not overlap. We show that these algorithms can be implemented in O(logm) time using m processors, where m is the output size. To our knowledge, this is the first such analysis. Categories and Subject Descriptors F.2.2 [Nonnumerical Algorithms and Problems]: Geo-metrical problems and computations; G.2.m [Discrete Math-

We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where κf (A) is the condition number of the matrix defining the linear system. Our algorithm applies the preconditioned Chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning.

We introduce the smoothed analysis of algorithms , which continuously interpolates between the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has smoothed complexity polynomial in the input size and the standard deviation of Gaussian perturbations.

We present a linear-system solver that, given an n-by-n symmetric positive semi-definite, diagonally dominant matrix A with m non-zero entries and an n-vector b, produces a vector x/spl tilde/ within relative distance /spl epsi/ of the solution to Ax = b in time O(m/sup 1.31/log(n//spl epsi/)b/sup O(1)/), where b is the log of the ratio of the largest to smallest non-zero entry of A. If the graph of A has genus m/sup 2/spl theta// or does not have a K/sub m/spl theta// minor, then the exponent of m can be improved to the minimum of 1 + 5/spl theta/ and (9/8)(1 + /spl theta/). The key contribution of our work is an extension of Vaidya's techniques for constructing and analyzing combinatorial preconditioners.

We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.

We present a randomized polynomial time algorithm to determine if a multivariate polynomial is zero using O(\log mnδ) random bits where n is the number of variables, m is the number of monomials, and δ is the total degree of the unknown polynomial. All other known randomized identity tests (see for example [7, 12, 1]) use ω(n) random bits even when the polynomial is sparse and has low total degree. In such cases our algorithm has an exponential savings in randomness. In addition, we obtain the first polynomial time algorithm for interpolating sparse polynomials over finite fields of large characteristic. Our approach uses an error correcting code combined with the randomness optimal isolation lemma of [8] and yields a generalized isolation lemma which works with respect to a set of linear forms over a base set.

We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. Essentially, we study the performance of algorithms under small random perturbations of their inputs. We show that the shadow-vertex simplex algorithm has polynomial smoothed complexity.

In the 50 years since Shannon determined the capacity of ergodic channels, the construction of capacity-approaching coding schemes has been the supreme goal of coding research. Finally today, we know of practical codes and decoding algorithms that can closely approach the channel capacity of some classical memoryless channels. It is a remarkable fact motivating this special issue that all known practical, capacity-approaching coding schemes are now understood to be codes defined on graphs, together with the associated iterative decoding algorithms.

We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyze the algorithm by analyzing a corresponding discrete-time random process. As a result, we obtain a simple criterion involving the fractions of nodes of different degrees on both sides of the graph which is necessary and sufficient for the decoding process to finish successfully with high probability. By carefully designing these graphs we can construct for any given rate R and any given real number /spl epsiv/ a family of linear codes of rate R which can be encoded in time proportional to ln(1//spl epsiv/) times their block length n. Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1+/spl epsiv/)Rn or more. The recovery algorithm also runs in time proportional to n ln(1//spl epsiv/). Our algorithms have been implemented and work well in practice; various implementation issues are discussed.

We construct new families of error-correcting codes based on Gallager's (1973) low-density parity-check codes. We improve on Gallager's results by introducing irregular parity-check matrices and a new rigorous analysis of hard-decision decoding of these codes. We also provide efficient methods for finding good irregular structures for such decoding algorithms. Our rigorous analysis based on martingales, our methodology for constructing good irregular codes, and the demonstration that irregular structure improves performance constitute key points of our contribution. We also consider irregular codes under belief propagation. We report the results of experiments testing the efficacy of irregular codes on both binary-symmetric and Gaussian channels. For example, using belief propagation, for rate 1/4 codes on 16000 bits over a binary-symmetric channel, previous low-density parity-check codes can correct up to approximately 16% errors, while our codes correct over 17%. In some cases our results come very close to reported results for turbo codes, suggesting that variations of irregular low density parity-check codes may be able to match or beat turbo code performance.

In this paper, we contrast some fundamental assumptions of coding theory with those used in complexity theory. In particular, we explain the differences in algorithms used in the software and hardware implementations of Reed-Solomon codes. We also explain how, when studying error-correcting codes, one must consider energy and communication delay to be resources, in addition to the usual space and time.

In [6], Gallager introduces a family of codes based on sparse bipartite graphs, which he calls low-density parity-check codes. He suggests a natural decoding algorithm for these codes, and proves a good bound on the fraction of errors that can be corrected. As the codes that Gallager builds are derived from regular graphs, we refer to them as regular codes. Following the general approach introduced in [7] for the design and analysis of erasure codes, we consider error-correcting codes based on random irregular bipartite graphs, which we call irregular codes. We introduce tools based on linear programming for designing linear time irregular codes with better error-correcting capabilities than possible with regular codes. For example, the decoding algorithm for the rate 1/2 regular codes of Gallager can provably correct up to 5.17% errors asymptotically, whereas we have found irregular codes for which our decoding algorithm can provably correct up to 6.27 % errors asymptotically. We include the results of simulations demonstrating the effectiveness of our codes on systems of reasonable size. 1

Abstract | We present randomized constructions of linear-time encodable and decodable codes that can transmit over lossy channels at rates extremely close to capacity. The encoding and decoding algorithms for these codes have fast and simple software implementations. Implementations of our algorithms are faster by orders of magnitude than the software implementations of previous algorithms. We expect these codes will be extremely useful for applications where lossy channels are common and fast decoding is a requirement, e.g., satellite transmission and multicast transmission over the Internet. I.

We demonstrate that the geometric separator algorithm of Miller, Teng, Thurston, and Vavasis finds a 3/4-separator of size 1.84+ for every n node planar graph.Our bound is derived from an analysis of disk packings on the sphere,

We re-introduce the coded model of fault-tolerant computation in which the input and output of a computational device are treated as words in an error-correcting code. A computational device correctly computes a function in the coded model if its input and output, once decoded, are a valid input and output of the function. In the coded model, it is reasonable to hope to simulate all computational devices by devices whose size is greater by a constant factor but which are exponentially reliable even if each of their components can fail with some constant probability. We consider fine-grained parallel computations in which each processor has a constant probability of producing the wrong output at each time step. We show that any parallel computation that runs for time t on w processors can be performed reliably on a faulty machine in the coded model using wlog/sup 0(1/)w processors and time tlog/sup 0(1)/w. The failure probability of the computation will be at most t/spl middot/exp(-w/sup 1/4 /). The codes used to communicate with our fault-tolerant machines are generalized Reed-Solomon codes and can thus be encoded and decoded in O(nlog/sup 0(1)/n) sequential time and are independent of the machine they are used to communicate with. We also show how coded computation can be used to self-correct many linear functions in parallel with arbitrarily small overhead.

Spectral partitioning methods use the Fiedler vector-the eigenvector of the second-smallest eigenvalue of the Laplacian matrix-to find a small separator of a graph. These methods are important components of many scientific numerical algorithms and have been demonstrated by experiment to work extremely well. In this paper, we show that spectral partitioning methods work well on bounded-degree planar graphs and finite element meshes-the classes of graphs to which they are usually applied. While active spectral bisection does not necessarily work, we prove that spectral partitioning techniques can be used to produce separators whose ratio of vertices removed to edges cut is O(/spl radic/n) for bounded-degree planar graphs and two-dimensional meshes and O(n/sup 1/d/) for well-shaped d-dimensional meshes. The heart of our analysis is an upper bound on the second-smallest eigenvalues of the Laplacian matrices of these graphs: we prove a bound of O(1/n) for bounded-degree planar graphs and O(1/n/sup 2/d/) for well-shaped d-dimensional meshes.

We demonstrate that isomorphism of strongly regular graphs may be tested in time n~m''''ogm).Our approach is to analyze the standard individualization and refinement algorithm in light of Neumaier's claw bound, which implies that low degree strongly regular graphs have a small second-largest eigenvalue, unless they are Steiner or Latin square graphs.

Using expander graphs, we construct a new family of asymptotically good, linear error-correcting codes. These codes have linear time sequential decoding algorithms and logarithmic time parallel decoding algorithms that use a linear number of processors. We present both randomized and explicit constructions of these codes. Experimental results demonstrate the good performance of the randomly chosen codes.

We present a new class of asymptotically good, linear error-correcting codes. These codes can be both encoded and decoded in linear time. They can also be encoded by logarithmic-depth circuits of linear size and decoded by logarithmic depth circuits of size O(nlogn). We present both randomized and explicit constructions of these codes.

We present a class of asymptotically good errorcorrecting codes that can be both encoded and decoded in linear sequential time and logarithmic parallel time with a linear number of processors.We present both randomized and explicit constructions of these codes.An important step in our construction is the introduction of error-reducing codes: codes that have a decoder that can very quickly remove a constant fraction of the errors from a corrupted codeword.1.

In this seminal paper on probabilistic Turing machines, Gill asked whether the class PP is closed under intersection and union. We give a positive answer to this question. We also show that PP is closed under a variety of polynomial-time truth-table reductions. Consequences in complexity theory include the definite collapse and (assuming P ≠ PP) separation of certain query hierarchies over PP. Similar techniques allow us to combine several threshold gates into a single threshold gate. Consequences in the study of circuits include the simulation of circuits with a small number of threshold gates by circuits having only a single threshold gate at the root (perceptrons) and a lower bound on the number of threshold gates that are needed to compute the parity function.

We present a new class of asymptotically good, linear error-correcting codes based upon expander graphs. These codes have linear time sequential decoding algorithms, logarithmic time parallel decoding algorithms with a linear number of processors, and are simple to understand. We present both randomized and explicit constructions for some of these codes. Experimental results demonstrate the extremely good performance of the randomly chosen codes.>

Article Nearly-linear size holographic proofs Share on Authors: Alexander Polishchuk Moscow Independent University Moscow Independent UniversityView Profile , Daniel A. Spielman Dept. of Applied Mathematics, Massachusetts Institute of Technology, Cambridge, MA Dept. of Applied Mathematics, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 194–203https://doi.org/10.1145/195058.195132Online:23 May 1994Publication History 92citation349DownloadsMetricsTotal Citations92Total Downloads349Last 12 Months14Last 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

Consider a set of processors, V, that can communicate with each other.Assume that each processor can be either "good" or "faulty".Also assume that the processors can be used to test each other.We provide a parallel algorithm that determines which processors are good and which are faulty in 32 rounds of testing, pre Tided that a strict majority of the processors are good.

In his seminal paper on probabilistic Turing machines, Gill [13] asked whether the class PP is closed under intersection and union. We give a positive answer to this question. We also show that PP is closed under a variety of polynomial-time truth-table reductions. Consequences in complexity theory include the definite collapse and (assuming P 6= PP) separation of certain query hierarchies over PP. Similar techniques allow us to combine several threshold gates into a single threshold gate. Consequences in the study of circuits include the simulation of circuits with a small number of threshold gates by circuits having only a single threshold gate at the root (perceptrons), and a lower bound on the number of threshold gates needed to compute the parity function. 1. Introduction The class PP was defined in 1972 by John Gill [13, 14] and independently by Janos Simon [26] in 1974. PP is the class of languages accepted by a polynomial-time bounded nondeterministic Turing machine t...