Expander graphs and their applications
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Linear codes (general theory) (94B05)
Recommendations
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- A Chernoff Bound for Random Walks on Expander Graphs
- A course in combinatorics.
- A Fast Monte-Carlo Test for Primality
- A lower bound on the spectral radius of the universal cover of a graph
- A Mathematical Theory of Communication
- A new family of Cayley expanders (?)
- A note on the isoperimetric constant
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A product decomposition for the classical quasisimple groups
- A proof of alon's second eigenvalue conjecture
- A recursive approach to low complexity codes
- A sample of samplers: a computational perspective on sampling
- Addendum to ``Random walk in random groups by M. Gromov.
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Are Bitvectors Optimal?
- Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
- Bounded generation and Kazhdan's property (T)
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Connection of the dual space of a group with the structure of its closed subgroups
- Constructing disjoint paths on expander graphs
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Current Trends in Theoretical Computer Science
- Derandomized graph products
- Design of capacity-approaching irregular low-density parity-check codes
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
- Eigenvalues and expanders
- Eigenvalues and expansion of regular graphs
- Embedding the diamond graph in L_p and dimension reduction in L₁
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Every connected regular graph of even degree is a Schreier coset graph
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Expander codes
- Expander flows, geometric embeddings and graph partitioning
- Expanders from symmetric codes
- Expanders obtained from affine transformations
- Expanders that beat the eigenvalue bound: Explicit construction and applications
- Explicit Concentrators from Generalized N-Gons
- Explicit construction of linear sized tolerant networks
- Explicit constructions of graphs without short cycles and low density codes
- Explicit constructions of linear-sized superconcentrators
- Explicit constructions of Ramanujan complexes of type A_d.
- Extensions of Lipschitz mappings into a Hilbert space
- Filling Riemannian manifolds
- Finite simple groups as expanders
- Finite simple groups of Lie type as expanders.
- Geometric algorithms and combinatorial optimization.
- Geometry of cuts and metrics
- Girth and Euclidean distortion
- Graph-theoretic properties in computational complexity
- Hamilton cycles in random lifts of graphs
- How to compute the volume in high dimension?
- How to share memory in a distributed system
- scientific article; zbMATH DE number 3126031 (Why is no real title available?)
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 3174791 (Why is no real title available?)
- scientific article; zbMATH DE number 5595151 (Why is no real title available?)
- scientific article; zbMATH DE number 3957109 (Why is no real title available?)
- scientific article; zbMATH DE number 192855 (Why is no real title available?)
- scientific article; zbMATH DE number 192902 (Why is no real title available?)
- scientific article; zbMATH DE number 3487716 (Why is no real title available?)
- scientific article; zbMATH DE number 3552764 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 1195779 (Why is no real title available?)
- scientific article; zbMATH DE number 1250549 (Why is no real title available?)
- scientific article; zbMATH DE number 1342092 (Why is no real title available?)
- scientific article; zbMATH DE number 475380 (Why is no real title available?)
- scientific article; zbMATH DE number 487720 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1022519 (Why is no real title available?)
- scientific article; zbMATH DE number 1518742 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 1559568 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- scientific article; zbMATH DE number 1789916 (Why is no real title available?)
- scientific article; zbMATH DE number 2134909 (Why is no real title available?)
- scientific article; zbMATH DE number 1849959 (Why is no real title available?)
- scientific article; zbMATH DE number 1885142 (Why is no real title available?)
- scientific article; zbMATH DE number 2115090 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Improved low-density parity-check codes using irregular graphs
- Inequalities in Fourier analysis
- Introduction to algorithms
- It is easy to determine whether a given integer is prime
- KAZHDAN CONSTANTS FOR SLn(ℤ)
- Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders
- Lifts, discrepancy and nearly optimal spectral gap
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Linear-time encodable and decodable error-correcting codes
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- Mathematical aspects of mixing times in Markov chains.
- Minors in lifts of graphs
- Modern Coding Theory
- Monotone Circuits for the Majority Function
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
- Not every uniform tree covers Ramanujan graphs
- On codes from hypergraphs.
- On Lipschitz embedding of finite metric spaces in Hilbert space
- On orthogonal and symplectic matrix ensembles
- On the complexity of an optimal non-blocking commutation scheme without reorganization
- On the complexity of approximating the independent set problem
- On the distribution of the roots of certain symmetric matrices
- On the Edge-Expansion of Graphs
- On the expansion rate of Margulis expanders.
- On the extreme eigenvalues of regular graphs.
- On the hardness of approximating Multicut and Sparsest-Cut
- On the second eigenvalue of a graph
- On the second eigenvalue of hypergraphs
- On-Line Algorithms for Path Selection in a Nonblocking Network
- Probabilistic algorithm for testing primality
- Proof verification and the hardness of approximation problems
- Pseudorandom Generators in Propositional Proof Complexity
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- Pseudorandomness for network algorithms
- Ramanujan graphs
- Random Cayley graphs and expanders
- Random graph coverings. I: General theory and graph connectivity
- Random Lifts of Graphs: Edge Expansion
- Random lifts of graphs: Independence and chromatic number
- Random lifts of graphs: perfect matchings
- Randomness conductors and constant-degree lossless expanders
- Randomness is linear in space
- Rank bounds and integrality gaps for cutting planes procedures
- Relative expanders or weakly relatively Ramanujan graphs.
- Short proofs are narrow—resolution made simple
- Smaller Explicit Superconcentrators
- Some geometric aspects of graphs and their eigenfunctions
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- Spectral norm of random matrices
- Symmetric groups and expander graphs.
- The capacity of low-density parity-check codes under message-passing decoding
- The complexity of testing whether a graph is a superconcentrator
- The eigenvalues of random symmetric matrices
- The expected eigenvalue distribution of a large regular graph
- The geometry of graphs and some of its algorithmic applications
- The non-backtracking spectrum of the universal cover of a graph
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The size of bipartite graphs with a given girth
- The Spectra of Infinite Hypertrees
- Tight estimates for eigenvalues of regular graphs
- Undirected ST-connectivity in log-space
- Upper bound on the characters of the symmetric groups
- Zeta functions of finite graphs and coverings. III
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
Cited in
(only showing first 100 items - show all)- Vertex percolation on expander graphs
- Matchings in regular graphs from eigenvalues
- Lower bounds for local versions of dimension reductions
- Expander graphs based on GRH with an application to elliptic curve cryptography
- Eigenvalues and edge-connectivity of regular graphs
- Expanding graphs and invariant means
- Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
- Essentially every unimodular matrix defines an expander
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- The fiber dimension of a graph
- Geometry of the smallest 1-form Laplacian eigenvalue on hyperbolic manifolds
- Spectral estimates for infinite quantum graphs
- A note about k-DNF resolution
- Costly circuits, submodular schedules and approximate Carathéodory theorems
- Local expanders
- The isoperimetric number of the incidence graph of \(\operatorname{PG}(n,q)\)
- Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
- Ramanujan coverings of graphs
- Random walks and diffusion on networks
- The first Cheeger constant of a simplex
- rDAN: toward robust demand-aware network designs
- On restricted edge-connectivity of replacement product graphs
- Interlacing families and the Hermitian spectral norm of digraphs
- Some properties of graphs constructed from 2-designs
- Distance powers of unitary Cayley graphs
- Discrete fundamental groups of warped cones and expanders
- 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
- Some ``good properties of LDA lattices
- Better path-finding algorithms in LPS Ramanujan graphs
- Generalizations of the Kolmogorov-Barzdin embedding estimates
- Sums and products along sparse graphs
- Fast scramblers, horizons and expander graphs
- Universal traversal sequences for expander graphs
- Weighted expanders and the anisotropic Alon-Boppana theorem
- 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
- 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
- Groups of oscillating intermediate growth.
- Phase transition of the 2-choices dynamics on core-periphery networks
- Towards the linear arboricity conjecture
- On some cycles in Wenger graphs
- The second eigenvalue of some normal Cayley graphs of highly transitive groups
- Super-approximation. II: The p-adic case and the case of bounded powers of square-free integers
- Improved approximation for fractionally subadditive network design
- Quantum expanders and growth of group representations
- Counting sum-free sets in abelian groups
- Ricci curvature, graphs and eigenvalues
- Super-expanders and warped cones
- Maximum rooted connected expansion
- Cycle lengths in expanding graphs
- Extremal eigenvalues of critical Erdős-Rényi graphs
- 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
- Prevalence expansion in NIMFA
- Square \((1,-1)\)-matrices with large determinants and near-Hadamard matrices
- Random Schreier graphs and expanders
- Accelerated information dissemination on networks with local and global edges
- 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
- 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
- Complexity of correspondence \(H\)-colourings
- Expander construction in \(\mathrm{VNC}^1\)
- Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
- 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
This page was built for publication: Expander graphs and their applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3514498)
