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