Entropy waves, the zig-zag graph product, and new constant-degree expanders
From MaRDI portal
Publication:1613289
DOI10.2307/3062153zbMath1008.05101arXivmath/0406038WikidataQ29036116 ScholiaQ29036116MaRDI QIDQ1613289
Omer Reingold, Avi Wigderson, Salil P. Vadhan
Publication date: 13 October 2002
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0406038
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
Related Items
On constructing expander families of G-graphs, Symmetric groups and expanders, Expander Construction in VNC1, Unnamed Item, Symmetric LDPC Codes and Local Testing, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Zeta functions of finite Schreier graphs and their zig-zag products, Unnamed Item, Constant-Round Interactive Proofs for Delegating Computation, Unnamed Item, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, Some graph theoretical aspects of generalized truncations, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, From Expanders to Hitting Distributions and Simulation Theorems, A fast new algorithm for weak graph regularity, Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that, Finite simple groups as expanders, Fast Interactive Coding against Adversarial Noise, Unnamed Item, Extracting all the randomness and reducing the error in Trevisan's extractors, Expanders with respect to Hadamard spaces and random graphs, Explicit Near-Ramanujan Graphs of Every Degree, An explicit construction of graphs of bounded degree that are far from being Hamiltonian, Connection of \(p\)-ary \(t\)-weight linear codes to Ramanujan Cayley graphs with \(t+1\) eigenvalues, On cylindrical graph construction and its applications, Affine extractors over large fields with exponential error, Expansion in SL\(_2(\mathbb R)\) and monotone expanders, Pseudorandom generators for combinatorial checkerboards, Recursive constructions of small regular graphs of given degree and girth, Almost-Ramanujan graphs and prime gaps, On eigenvalues of random complexes, Symmetric LDPC codes and local testing, Spectra of lifted Ramanujan graphs, Strong uniform expansion in \(\text{SL}(2,p)\)., Quotients of Gaussian graphs and their application to perfect codes, The Euclidean distortion of the lamplighter group., Cutoff phenomena for random walks on random regular graphs, Bounds on isoperimetric values of trees, Hamiltonian paths in Cayley graphs, A note about \(k\)-DNF resolution, Local expanders, On restricted edge-connectivity of replacement product graphs, Percolation on finite graphs and isoperimetric inequalities., Parameterized random complexity, Super-expanders and warped cones, Game-theoretic fairness meets multi-party protocols: the case of leader election, Expander construction in \(\mathrm{VNC}^1\), Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time, A spanner for the day after, Explicit expanders of every degree and size, Lossless dimension expanders via linearized polynomials and subspace designs, Nonlinear spectral calculus and super-expanders, Combinatorial algorithms for distributed graph coloring, Ramanujan graphs and expander families constructed from \(p\)-ary bent functions, Some degree and distance-based invariants of wreath products of graphs, Symmetry properties of generalized graph truncations, Nonpositive curvature is not coarsely universal, Permutational powers of a graph, Generalized cages, On subexponential and FPT-time inapproximability, Self-similar groups and the zig-zag and replacement products of graphs, Generalized wreath products of graphs and groups, The PCP theorem for NP over the reals, Synchronization of coupled chaotic maps, Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries, Bipartite multigraphs with expander-like properties, Explicit expanding expanders, Low-degree test with polynomially small error, Constraints, MMSNP and expander relational structures, Symmetric groups and expander graphs., Computation of best possible low degree expanders, Correlation clustering in general weighted graphs, An overview of periodic elliptic operators, Maximizing the Order of a Regular Graph of Given Valency and Second Eigenvalue, Connectedness and Isomorphism Properties of the Zig-Zag Product of Graphs, QUASIRANDOM GROUP ACTIONS, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, An Introduction to Randomness Extractors, Minimal selectors and fault tolerant networks, Bravely, Moderately: A Common Theme in Four Recent Works, Basic Facts about Expander Graphs, Combinatorial Algorithms for Distributed Graph Coloring, Expander graphs in pure and applied mathematics, KAZHDAN CONSTANTS OF GROUP EXTENSIONS, Expanding Generating Sets for Solvable Permutation Groups, Expander graphs and their applications, Expander graphs and gaps between primes, An Elementary Construction of Constant-Degree Expanders, Layouts of Expander Graphs
