Expander graphs and their applications

DOI10.1090/S0273-0979-06-01126-8zbMath1147.68608OpenAlexW2018047324WikidataQ29400073 ScholiaQ29400073MaRDI QIDQ3514498

Avi Wigderson, Shlomo Hoory, Nathan Linial

Publication date: 21 July 2008

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0273-0979-06-01126-8

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Linear codes (general theory) (94B05) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Automorphisms and isogeny graphs of abelian varieties, with applications to the superspecial Richelot isogeny graph, Quasi-factorization and multiplicative comparison of subalgebra-relative entropy, A Spectral Moore Bound for Bipartite Semiregular Graphs, On directed analogues of expander and hyperfinite graph sequences, Spectral gap in random bipartite biregular graphs and applications, A Cheeger-Buser-type inequality on CW complexes, Sieve methods in group theory I: Powers in linear groups, Structure of Graphs with Locally Restricted Crossings, Expanders are counterexamples to the $\ell^p$ coarse Baum-Connes conjecture, Cryptographic properties of the quantum hashing based on expander graphs, Graphs with high second eigenvalue multiplicity, Finding any given 2‐factor in sparse pseudorandom graphs efficiently, Assouad-Nagata dimension and gap for ordered metric spaces, Matrix functions in network analysis, Optimal sufficient requirements on the embedded Ising problem in polynomial time, Reliable Spanners for Metric Spaces, A note on the trace method for random regular graphs, Gap sets for the spectra of cubic graphs, Global eigenvalue fluctuations of random biregular bipartite graphs, Generating Extended Resolution Proofs with a BDD-Based SAT Solver, Probabilistic analysis of optimization problems on sparse random shortest path metrics, One-matching bi-Cayley graphs and homogeneous bi-Cayley graphs over finite cyclic groups, Many nodal domains in random regular graphs, The boundary of a graph and its isoperimetric inequality, Connection of $p$-ary $t$-weight linear codes to Ramanujan Cayley graphs with $t+1$ eigenvalues, Explicit construction of $q+1$ regular local Ramanujan graphs, for all prime-powers $q$, Combinatorial Fiedler theory and graph partition, Arithmetic and dynamics on varieties of Markoff type, Toward super‐approximation in positive characteristic, Spectrum of random d‐regular graphs up to the edge, On the eigenvalues of the graphs $D(5,q)$, Paradigms for Unconditional Pseudorandom Generators, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Parameterized Counting and Cayley Graph Expanders, Balanced Subdivisions of a Large Clique in Graphs with High Average Degree, On the second eigenvalue of random bipartite biregular graphs, Anatomy of a Gaussian giant: supercritical level-sets of the free field on regular graphs, Orion: zero knowledge proof with linear prover time, Unnamed Item, Towards the Erdős-Gallai cycle decomposition conjecture, Bounded degree cosystolic expanders of every dimension, Optimization in graphical small cancellation theory, Nowhere to go but high: a perspective on high-dimensional expanders, Interactions of computational complexity theory and mathematics, Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication, Randomized Rumour Spreading: The Effect of the Network Topology, Property (𝑇) for Groups Graded by Root Systems, Unnamed Item, Unnamed Item, Structure of eigenvectors of random regular digraphs, Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems, Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile, Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks, Must the communication graph of MPC protocols be an expander?, Quantum logarithmic Sobolev inequalities and rapid mixing, Greedy Random Walk, Component Games on Regular Graphs, Coarse amenability versus paracompactness, On signed graphs whose second largest Laplacian eigenvalue does not exceed 3, Faster and enhanced inclusion-minimal cograph completion, The Complexity of Propositional Proofs, Generalizing the hypergraph Laplacian via a diffusion process with mediators, The spectrum of the random environment and localization of noise, Product-state approximations to quantum states, Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians, Pseudorandom Graphs from Elliptic Curves, Collisions for the LPS Expander Graph Hash Function, Fragile complexity of adaptive algorithms, Fragile complexity of adaptive algorithms, Identification protocols and signature schemes based on supersingular isogeny problems, Expanders with respect to Hadamard spaces and random graphs, The Weisfeiler-Leman algorithm and recognition of graph properties, EIGENVALUES AND LINEAR QUASIRANDOM HYPERGRAPHS, Periodic Walks on Large Regular Graphs and Random Matrix Theory, Explicit Near-Ramanujan Graphs of Every Degree, Unnamed Item, Unnamed Item, An explicit construction of graphs of bounded degree that are far from being Hamiltonian, (Dis)assortative partitions on random regular graphs, Cutoff for random lifts of weighted graphs, On atomic registers and randomized consensus in m\&m systems, Linear random walks on the torus, High-girth near-Ramanujan graphs with localized eigenvectors, On the second largest eigenvalue of some Cayley graphs of the symmetric group, Eigenvalues of Cayley graphs, Cutoff on graphs and the Sarnak-Xue density of eigenvalues, Boundedness and nuclearity of pseudo-differential operators on homogeneous trees, Regularity-based spectral clustering and mapping the Fiedler-carpet, Complete entropic inequalities for quantum Markov chains, Solution counts and sums of roots of unity, Finding structure in sequences of real numbers via graph theory: a problem list, On the spectrum of dense random geometric graphs, On the spectrum of finite, rooted homogeneous trees, Transition from Tracy-Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős-Rényi graphs, A surface with discontinuous isoperimetric profile and expander manifolds, The geometry of spontaneous spiking in neuronal networks, Constructions of given-depth and optimal multirate rearrangeably nonblocking distributors, Cops and Robber game with a fast robber on expander graphs and random graphs, Complexity of correspondence $H$-colourings, Expander construction in $\mathrm{VNC}^1$, Expansion in perfect groups., An introduction to the Ribe program, Parameterized random complexity, The complexity of inverting explicit Goldreich's function by DPLL algorithms, Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae, Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time, Groups of oscillating intermediate growth., Regular partitions of gentle graphs, Multi-way sparsest cut problem on trees with a control on the number of parts and outliers, A spanner for the day after, Connectivity for quantum graphs, Expander graphs -- both local and global, Spectral radii of sparse random matrices, Speed of random walks, isoperimetry and compression of finitely generated groups, On the order of regular graphs with fixed second largest eigenvalue, The lattice of cycles of an undirected graph, Discrete optimization methods for group model selection in compressed sensing, Explicit expanders of every degree and size, Phase transition of the 2-choices dynamics on core-periphery networks, On unitary Cayley graphs of matrix rings, Towards the linear arboricity conjecture, On some cycles in Wenger graphs, Nonlinear spectral calculus and super-expanders, Xheal: a localized self-healing algorithm using expanders, Pseudo-random graphs and bit probe schemes with one-sided error, The second eigenvalue of some normal Cayley graphs of highly transitive groups, Sums and products along sparse graphs, Super-approximation. II: The $p$-adic case and the case of bounded powers of square-free integers, No sublogarithmic-time approximation scheme for bipartite vertex cover, On graph parameters guaranteeing fast sandpile diffusion, Maximizing algebraic connectivity for certain families of graphs, Improved approximation for fractionally subadditive network design, Quantum expanders and growth of group representations, Counting sum-free sets in abelian groups, Kazhdan projections, random walks and ergodic theorems, Ricci curvature, graphs and eigenvalues, A spectral version of the Moore problem for bipartite regular graphs, Super-expanders and warped cones, $L^p$-expander graphs, Approximate Moore graphs are good expanders, Maximum rooted connected expansion, Cycle lengths in expanding graphs, Fast scramblers, horizons and expander graphs, Extremal eigenvalues of critical Erdős-Rényi graphs, Ramanujan graphs and expander families constructed from $p$-ary bent functions, Fluctuations of extreme eigenvalues of sparse Erdős-Rényi graphs, The spectral gap of sparse random digraphs, Beating treewidth for average-case subgraph isomorphism, Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey, Remarks on partitions into expanders, An average John theorem, On the spread of influence in graphs, Toward a spectral theory of cellular sheaves, Opinion forming in Erdős-Rényi random graph and expanders, Cut ratios and Laplacian eigenvalues, Prevalence expansion in NIMFA, Nonpositive curvature is not coarsely universal, Diffusion operator and spectral analysis for directed hypergraph Laplacian, On the local geometry of graphs in terms of their spectra, Square $(1,-1)$-matrices with large determinants and near-Hadamard matrices, Hypergraph expanders from Cayley graphs, Random Schreier graphs and expanders, Random Steiner systems and bounded degree coboundary expanders of every dimension, Quantitative aspects of acyclicity, Isoperimetric numbers of randomly perturbed intersection graphs, Levels of distribution and the affine sieve, Accelerated information dissemination on networks with local and global edges, Spectral properties of modularity matrices, Integral circulant Ramanujan graphs via multiplicativity and ultrafriable integers, A partial derandomization of phaselift using spherical designs, On vertex rankings of graphs and its relatives, On subexponential and FPT-time inapproximability, Self-similar groups and the zig-zag and replacement products of graphs, Expansion in supercritical random subgraphs of the hypercube and its consequences, Poisson statistics and localization at the spectral edge of sparse Erdős-Rényi graphs, Cycle lengths modulo $k$ in expanders, Long time dynamics for interacting oscillators on graphs, On the hierarchical community structure of practical Boolean formulas, Proof complexity of symbolic QBF reasoning, Planar lattice subsets with minimal vertex boundary, The fiber dimension of a graph, Quantum ergodicity for quantum graphs without back-scattering, Isoperimetric inequalities for Ramanujan complexes and topological expanders, Geometry of the smallest 1-form Laplacian eigenvalue on hyperbolic manifolds, Spectral estimates for infinite quantum graphs, Graph-theoretic design and analysis of key predistribution schemes, $\mathrm{SL}_2$ homomorphic hash functions: worst case to average case reduction and short collision search, Small complete minors above the extremal edge density, Adjacency matrices of random digraphs: singularity and anti-concentration, Linear-time list recovery of high-rate expander codes, A note about $k$-DNF resolution, Affine linear sieve, expanders, and sum-product, Costly circuits, submodular schedules and approximate Carathéodory theorems, Book review of: T. Tao, Expansion in finite simple groups of Lie type, Local expanders, Cutoff on all Ramanujan graphs, The isoperimetric number of the incidence graph of $\operatorname{PG}(n,q)$, Expansion in SL$_2(\mathbb R)$ and monotone expanders, Strong uniform expansion in $\text{SL}(2,p)$., Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms, Ramanujan coverings of graphs, Amenability, locally finite spaces, and bi-Lipschitz embeddings, Constructing uniquely realizable graphs, Spanders: distributed spanning expanders, Integral circulant Ramanujan graphs of prime power order, Random walks and diffusion on networks, Algebraic Cayley graphs over finite fields, A Cheeger-type inequality on simplicial complexes, On the spectrum of Wenger graphs, Discrepancy inequalities for directed graphs, Hardness amplification within NP against deterministic algorithms, Design of highly synchronizable and robust networks, Linear programming bounds for regular graphs, Randomized oblivious integral routing for minimizing power cost, Path Laplacian matrices: introduction and application to the analysis of consensus in networks, The first Cheeger constant of a simplex, Shaping bursting by electrical coupling and noise, Expansion in $\text{SL}_d(\mathbb Z/q\mathbb Z)$, $q$ arbitrary., On rigid matrices and $U$-polynomials, Nilprogressions and groups with moderate growth, Expander graphs, gonality, and variation of Galois representations, Fighting constrained fires in graphs, On the optimality of gluing over scales, Matrix and discrepancy view of generalized random and quasirandom graphs, Cheeger constants, growth and spectrum of locally tessellating planar graphs, rDAN: toward robust demand-aware network designs, On restricted edge-connectivity of replacement product graphs, Cayley graph expanders and groups of finite width., Interlacing families and the Hermitian spectral norm of digraphs, Colouring, constraint satisfaction, and complexity, Almost-Ramanujan graphs and prime gaps, Efficient structure of noisy communication networks, Ramanujan complexes and high dimensional expanders, Majority dynamics on trees and the dynamic cavity method, Concentration of the Kirchhoff index for Erdős-Rényi graphs, Cleaning random $d$-regular graphs with brooms, Regular graphs of large girth and arbitrary degree, Some properties of graphs constructed from 2-designs, The road to deterministic matrices with the restricted isometry property, Distance powers of unitary Cayley graphs, Beyond the expanders, Random Latin squares and 2-dimensional expanders, Spectral and combinatorial properties of some algebraically defined graphs, Minimal multiple blocking sets, Expansion of random graphs: new proofs, new results, Construction of graphs with exactly $k$ main eigenvalues, Discrete fundamental groups of warped cones and expanders, On eigenvalues of random complexes, Gracefully degrading consensus and $k$-set agreement in directed dynamic networks, Computing marginals using MapReduce, Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs, Size biased couplings and the spectral gap for random regular graphs, Efficient robust secret sharing from expander graphs, Lifts, derandomization, and diameters of Schreier graphs of Mealy automata, Expansion and random walks in $\text{SL}_d(\mathbb{Z}/p^n\mathbb{Z})$. I., Entropy and isoperimetry for linear and non-linear group actions., Some ``good properties of LDA lattices, Hypercube percolation, Better path-finding algorithms in LPS Ramanujan graphs, Connected graph searching, Eigenvalues and expansion of bipartite graphs, Testing the expansion of a graph, Generalizations of the Kolmogorov-Barzdin embedding estimates, Cubic polyhedral Ramanujan graphs with face size no larger than six, Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs, Spectra of lifted Ramanujan graphs, Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry, On regular induced subgraphs of generalized polygons, A generalized Alon-Boppana bound and weak Ramanujan graphs, Vertex percolation on expander graphs, Matchings in regular graphs from eigenvalues, Fast scramblers and ultrametric black hole horizons, Spectra of Cayley graphs of complex reflection groups, Graphs with average degree smaller than $\frac{30}{11}$ burn slowly, The set of solutions of random XORSAT formulae, Lower bounds for local versions of dimension reductions, Eigenvalues and edge-connectivity of regular graphs, Relating multiway discrepancy and singular values of nonnegative rectangular matrices, Expansion of building-like complexes, Well-mixing vertices and almost expanders, The Supersingular Isogeny Problem in Genus 2 and Beyond, Ricci curvature, Bruhat graphs and Coxeter groups, Large expanders in high genus unicellular maps, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, A Novel Compressed Sensing Scheme for Photoacoustic Tomography, Expander Construction in VNC1, Geometry and Combinatorics via Right-Angled Artin Groups, Cyclic Inclusion-Exclusion, Crux and Long Cycles in Graphs, Organisational hierarchy constructions with easy Kuramoto synchronisation, Updating and Downdating Techniques for Optimizing Network Communicability, Edge-Isoperimetric Problem for Cayley Graphs and Generalized Takagi Functions, Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes, Submodular Functions: Learnability, Structure, and Optimization, Rolling backwards can move you forward: On embedding problems in sparse expanders, Hereditary quasirandomness without regularity, Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders, Persistent Laplacians: Properties, Algorithms and Implications, Deconstructing 1-Local Expanders, On Constructing Expanders for Any Number of Vertices, Find Your Place: Simple Distributed Algorithms for Community Detection, Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions, Efficient and Reliable Overlay Networks for Decentralized Federated Learning, Graph coloring with no large monochromatic components, Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs, Tail Estimates for Sums of Variables Sampled by a Random Walk, Unnamed Item, Finding and Using Expanders in Locally Sparse Graphs, Unnamed Item, Sign rank versus Vapnik-Chervonenkis dimension, ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS, Aldous’s spectral gap conjecture for normal sets, Signatures, Lifts, and Eigenvalues of Graphs, Optimal Design of Process Flexibility for General Production Systems, Expander graphs and gaps between primes, Proof Complexity Meets Algebra, Spectral expansion of random sum complexes, Unitary homogeneous bi-Cayley graphs over finite commutative rings, On constructing expander families of G-graphs, Moments of the inverse participation ratio for the Laplacian on finite regular graphs, An Elementary Construction of Constant-Degree Expanders, ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES, Constructing concrete hard instances of the maximum independent set problem, Deterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automata, VERTEX ISOPERIMETRIC PARAMETER OF A COMPUTATION GRAPH, Measure expanding actions, expanders and warped cones, Quasirandom Cayley graphs, COBOUNDARY EXPANDERS, Explicit Bounds from the Alon–Boppana Theorem, Testing Expansion in Bounded-Degree Graphs, The idemetric property: when most distances are (almost) the same, Deterministic Tensor Completion with Hypergraph Expanders, Keyed hash function from large girth expander graphs, Counting problems in Apollonian packings, Unnamed Item, Snowflake universality of Wasserstein spaces, Unnamed Item, Unnamed Item, Computational topology and the Unique Games Conjecture, Unnamed Item, Layouts of Expander Graphs, Unnamed Item, Open problems in the spectral theory of signed graphs, Eigenvectors of random graphs: Nodal Domains, A combinatorial proof of Bass's determinant formula for the zeta function of regular graphs, Ramanujan Graphs for Post-Quantum Cryptography, Fragile complexity of comparison-based algorithms, Generalized quasirandom properties of expanding graph sequences, Distributed Corruption Detection in Networks, Gluing of graph Laplacians and their spectra, Unnamed Item, Interactive Communication, Diagnosis and Error Control in Networks, Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs, Opinion Forming in Erdös-Rényi Random Graph and Expanders, Local-global convergence, an analytic and structural approach, Quantum Chaos on Random Cayley Graphs of SL 2[Z/pZ], Unnamed Item, Compression functions of uniform embeddings of groups into Hilbert and Banach spaces, On the Expansion of Group-Based Lifts, High Dimensional Random Walks and Colorful Expansion, Outlaw distributions and locally decodable codes, Robustness of randomized rumour spreading, The Ramanujan conjecture and its applications, From Ramanujan graphs to Ramanujan complexes, Balanced Hashing, Color Coding and Approximate Counting, Navigating directed Cayley graphs of small diameter: A potent Solovay–Kitaev procedure, Mixing time and eigenvalues of the abelian sandpile Markov chain, Certifiably Pseudorandom Financial Derivatives, The non-backtracking spectrum of the universal cover of a graph, Unnamed Item, Spectra of the extended neighborhood corona and extended corona of two graphs, Ramanujan graphs arising as weighted Galois covering graphs, On the Expansion of Group-Based Lifts, Discrete Graphs – A Paradigm Model for Quantum Chaos, Constructing highly regular expanders from hyperbolic Coxeter groups, The poset of hypergraph quasirandomness, The Complexity of Public-Key Cryptography, Graph Powering and Spectral Robustness, Reflections on Proof Complexity and Counting Principles, From graphs to keyed quantum hash functions, Geometric complexity of embeddings in $\mathbb R^d$, Vector representation of graph domination, KAZHDAN CONSTANTS OF GROUP EXTENSIONS, Tight products and graph expansion, Rank-width of random graphs, DEX: self-healing expanders, Expanding Generating Sets for Solvable Permutation Groups, Expanders and time-restricted branching programs, Graphs, Vectors, and Matrices, Random Latin square graphs, On small world semiplanes with generalised Schubert cells, On Compiling Structured CNFs to OBDDs, Deterministic algorithms for matrix completion, Spectra of the neighbourhood corona of two graphs, Mean-field conditions for percolation on finite graphs, Extensions of Fractional Precolorings Show Discontinuous Behavior, Isoperimetric inequalities in simplicial complexes, Connectivity and diagnosability of center $k$-ary $n$-cubes, Elementary bounds on mixing times for decomposable Markov chains, Explicit expanding expanders, Sparse network optimization for synchronization, Generating sets for the multiplicative groups of algebras over finite fields and expander graphs, Multipoint entanglement in disordered systems, On compiling structured CNFs to OBDDs, Discrepancies of spanning trees and Hamilton cycles, Robustness of random graphs based on graph spectra, Correspondence homomorphisms to reflexive graphs, Geodesic geometry on graphs, Spectrum and combinatorics of two-dimensional Ramanujan complexes, The vertex-isoperimetric number of the incidence and non-incidence graphs of unitals, Mean isoperimetry with control on outliers: exact and approximation algorithms, Ricci curvature of Bruhat orders, Discrepancy properties for random regular digraphs, Tighter spectral bounds for the cut size, based on Laplacian eigenvectors, Finding large expanders in graphs: from topological minors to induced subgraphs, Expander spanning subgraphs with large girth, A combinatorial approach to quantum random functions, Leader election in well-connected graphs, QUASIRANDOM GROUP ACTIONS, Cayley sum graphs and their applications to codebooks, Aldous' spectral gap property for normal Cayley graphs on symmetric groups, Sharp spectral bounds for the edge-connectivity of regular graphs, Cryptographic hash functions from sequences of lifted Paley graphs, Constraints, MMSNP and expander relational structures, The Laplacian lattice of a graph under a simplicial distance function, On the diameter of permutation groups., Large regular bipartite graphs with median eigenvalue 1, Towards factoring in $\mathrm{SL}(2,\mathbb F_{2^n})$, Modular Orientations of Random and Quasi-Random Regular Graphs, Some physical and chemical indices of clique-inserted lattices, Algorithms for #BIS-Hard Problems on Expander Graphs, The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms, An Introduction to Randomness Extractors, Graphs (networks) with golden spectral ratio, Unnamed Item, The effect of induced subgraphs on quasi-randomness, A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem, Word maps and spectra of random graph lifts, How to pick a random integer matrix? (and other questions), Modularity spectra, eigen-subspaces, and structure of weighted graphs, Explicit Construction of Ramanujan Bigraphs, Cryptographic Hash Functions and Expander Graphs: The End of the Story?, Maximum algebraic connectivity augmentation is NP-hard, Edge Modification Criteria for Enhancing the Communicability of Digraphs, On tree width, bramble size, and expansion, Sphere equivalence, Property H, and Banach expanders, NONEXISTENCE OF A CIRCULANT EXPANDER FAMILY, SELECTED TOPICS IN SPECTRAL GRAPH THEORY, The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics, Maximizing the Order of a Regular Graph of Given Valency and Second Eigenvalue, Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs, A Sample of Samplers: A Computational Perspective on Sampling, Basic Facts about Expander Graphs, Poincaré inequalities, embeddings, and wild groups, Connectedness and Isomorphism Properties of the Zig-Zag Product of Graphs, Anatomy of a young giant component in the random graph, Discrepancy of high-dimensional permutations, Physical Expander in Virtual Tree Overlay, Experiments on Density-Constrained Graph Clustering, ON CONSTRUCTION OF ALMOST-RAMANUJAN GRAPHS, Communicability Angle and the Spatial Efficiency of Networks, Robustness of regular ring lattices based on natural connectivity, Rapid Mixing and Markov Bases, Expander graphs in pure and applied mathematics, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, Lipschitz Functions on Expanders are Typically Flat, Rumor spreading on random regular graphs and expanders, On Dinur’s proof of the PCP theorem, Linearized Wenger graphs, Relative expanders, Generalized river crossing problems, Counting independent sets in graphs, Local correctability of expander codes, Quadratic unitary Cayley graphs of finite commutative rings, Braess's paradox in expanders, Interlacing families. I: Bipartite Ramanujan graphs of all degrees, Generalized wreath products of graphs and groups, Synchronization of coupled chaotic maps, On Lipschitz extension from finite subsets

Cites Work