Expander graphs and their applications
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Linear codes (general theory) (94B05)
Recommendations
Cites work
- 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?)
- A Chernoff Bound for Random Walks on Expander Graphs
- A Fast Monte-Carlo Test for Primality
- A Mathematical Theory of Communication
- A course in combinatorics.
- A lower bound on the spectral radius of the universal cover of a graph
- 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 Ramanujan complexes of type A_d.
- Explicit constructions of graphs without short cycles and low density codes
- Explicit constructions of linear-sized superconcentrators
- 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
- 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 Lipschitz embedding of finite metric spaces in Hilbert space
- On codes from hypergraphs.
- On orthogonal and symplectic matrix ensembles
- On the Edge-Expansion of Graphs
- 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 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 Lifts of Graphs: Edge Expansion
- Random graph coverings. I: General theory and graph connectivity
- 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 Spectra of Infinite Hypertrees
- 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
- 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
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
Cited in
(only showing first 100 items - show all)- Organisational hierarchy constructions with easy Kuramoto synchronisation
- Component games on regular graphs
- Graphs (networks) with golden spectral ratio
- Constructing uniquely realizable graphs
- Spectrum and combinatorics of two-dimensional Ramanujan complexes
- Monotone expanders: constructions and applications
- Expansion in matrix-weighted graphs
- Planar lattice subsets with minimal vertex boundary
- Deterministic tensor completion with hypergraph expanders
- A Cheeger-Buser-type inequality on CW complexes
- Cryptographic hash functions from sequences of lifted Paley graphs
- On the expansion of group-based lifts
- scientific article; zbMATH DE number 1552121 (Why is no real title available?)
- On the local geometry of graphs in terms of their spectra
- Expander construction in \(\mathsf{VNC}^1\)
- Robustly self-ordered graphs: constructions and applications to property testing
- Leader election in well-connected graphs
- Proof Complexity Meets Algebra
- The supersingular isogeny problem in genus 2 and beyond
- Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders
- Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
- Vector representation of graph domination
- The spectral gap of sparse random digraphs
- Spanders: distributed spanning expanders
- Integral circulant Ramanujan graphs of prime power order
- A partial derandomization of phaselift using spherical designs
- Algebraic Cayley graphs over finite fields
- On the spectrum of Wenger graphs
- Explicit expanders of every degree and size
- Identification protocols and signature schemes based on supersingular isogeny problems
- Efficient and reliable overlay networks for decentralized federated learning
- Path Laplacian matrices: introduction and application to the analysis of consensus in networks
- Expansion in \(\text{SL}_d(\mathbb Z/q\mathbb Z)\), \(q\) arbitrary.
- Eigenvalues and expansion of bipartite graphs
- Graph algorithm based submodular function for sparsest cut problem
- Expansion of building-like complexes
- Relating multiway discrepancy and singular values of nonnegative rectangular matrices
- Generalized quasirandom properties of expanding graph sequences
- Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- Cubic polyhedral Ramanujan graphs with face size no larger than six
- Reflections on Proof Complexity and Counting Principles
- Isoperimetric inequalities for Ramanujan complexes and topological expanders
- Expansion in supercritical random subgraphs of the hypercube and its consequences
- Expanders and right-angled Artin groups
- The lattice of cycles of an undirected graph
- Regular partitions of gentle graphs
- Multi-way sparsest cut problem on trees with a control on the number of parts and outliers
- Structure of eigenvectors of random regular digraphs
- The road to deterministic matrices with the restricted isometry property
- Fragile complexity of comparison-based algorithms
- Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks
- On compiling structured CNFs to OBDDs
- Random Steiner systems and bounded degree coboundary expanders of every dimension
- Toward super‐approximation in positive characteristic
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Open problems in the spectral theory of signed graphs
- Computational topology and the unique games conjecture
- Perfect matching in random graphs is as hard as Tseitin
- Persistent Laplacians: properties, algorithms and implications
- Spectral expansion of random sum complexes
- Process flexibility revisited: the graph expander and its applications
- From Ramanujan graphs to Ramanujan complexes
- Distance powers of unitary Cayley graphs
- Some properties of graphs constructed from 2-designs
- Ramanujan complexes and high dimensional expanders
- Xheal: a localized self-healing algorithm using expanders
- On constructing expander families of G-graphs
- Random Latin squares and 2-dimensional expanders
- Explicit construction of Ramanujan bigraphs
- Ricci curvature, Bruhat graphs and Coxeter groups
- Generalized wreath products of graphs and groups
- Highly symmetric expanders
- Cycle lengths modulo k in expanders
- Joins of normal matrices, their spectrum, and applications
- On Lipschitz extension from finite subsets
- The spectral edge of constant degree Erdős-Rényi graphs
- Generalisations of matrix partitions: complexity and obstructions
- A spanner for the day after
- Matrix functions in network analysis
- Coarse amenability versus paracompactness
- Expansion and random walks in \(\text{SL}_d(\mathbb{Z}/p^n\mathbb{Z})\). I.
- Vertex isoperimetric parameter of a computation graph
- Hypercube percolation
- An elementary construction of constant-degree expanders
- On Dinur’s proof of the PCP theorem
- Spectrum of random d‐regular graphs up to the edge
- On the eigenvalues of the graphs D(5,q)
- Spectral properties of generalized Paley graphs
- Balanced Subdivisions of a Large Clique in Graphs with High Average Degree
- Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
- The Complexity of Propositional Proofs
- Extensions of fractional precolorings show discontinuous behavior
- Tangled paths: a random graph model from Mallows permutations
- Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
- Linearized Wenger graphs
- Strong blocking sets and minimal codes from expander graphs
- Essentially every unimodular matrix defines an expander
- Discrete fundamental groups of warped cones and expanders
- High dimensional random walks and colorful expansion
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)
