Expander graphs and their applications (Q3514498): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q29400073
@@ Property / Wikidata QID: Q29400073 / rank @@
+Normal rank
@@ Property / cites work @@
+Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
+Normal rank
@@ Property / cites work @@
+Pseudorandom Generators in Propositional Proof Complexity
+Normal rank
@@ Property / cites work @@
+Explicit construction of linear sized tolerant networks
+Normal rank
@@ Property / cites work @@
+Smaller Explicit Superconcentrators
@@ Property / cites work: Smaller Explicit Superconcentrators / rank @@
+Normal rank
@@ Property / cites work @@
+The non-backtracking spectrum of the universal cover of a graph
+Normal rank
@@ Property / cites work @@
+Derandomized graph products
@@ Property / cites work: Derandomized graph products / rank @@
+Normal rank
@@ Property / cites work @@
+Random Lifts of Graphs: Edge Expansion
@@ Property / cites work: Random Lifts of Graphs: Edge Expansion / rank @@
+Normal rank
@@ Property / cites work @@
+Random graph coverings. I: General theory and graph connectivity
+Normal rank
@@ Property / cites work @@
+On-Line Algorithms for Path Selection in a Nonblocking Network
+Normal rank
@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Random lifts of graphs: Independence and chromatic number
+Normal rank
@@ Property / cites work @@
+Eigenvalues and expanders
@@ Property / cites work: Eigenvalues and expanders / rank @@
+Normal rank
@@ Property / cites work @@
+On the Edge-Expansion of Graphs
@@ Property / cites work: On the Edge-Expansion of Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+\(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
+Normal rank
@@ Property / cites work @@
+Random Cayley graphs and expanders
@@ Property / cites work: Random Cayley graphs and expanders / rank @@
+Normal rank
@@ Property / cites work @@
+Expander flows, geometric embeddings and graph partitioning
+Normal rank
@@ Property / cites work @@
+Q2784326
@@ Property / cites work: Q2784326 / rank @@
+Normal rank
@@ Property / cites work @@
+Hamilton cycles in random lifts of graphs
@@ Property / cites work: Hamilton cycles in random lifts of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Inequalities in Fourier analysis
@@ Property / cites work: Inequalities in Fourier analysis / rank @@
+Normal rank
@@ Property / cites work @@
+Q4527020
@@ Property / cites work: Q4527020 / rank @@
+Normal rank
@@ Property / cites work @@
+On codes from hypergraphs.
@@ Property / cites work: On codes from hypergraphs. / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of testing whether a graph is a superconcentrator
+Normal rank
@@ Property / cites work @@
+Lifts, discrepancy and nearly optimal spectral gap
+Normal rank
@@ Property / cites work @@
+Are Bitvectors Optimal?
@@ Property / cites work: Are Bitvectors Optimal? / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002766
@@ Property / cites work: Q3002766 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3726125
@@ Property / cites work: Q3726125 / rank @@
+Normal rank
@@ Property / cites work @@
+Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
+Normal rank
@@ Property / cites work @@
+On Lipschitz embedding of finite metric spaces in Hilbert space
+Normal rank
@@ Property / cites work @@
+On the complexity of an optimal non-blocking commutation scheme without reorganization
+Normal rank
@@ Property / cites work @@
+On the complexity of approximating the independent set problem
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank
@@ Property / cites work @@
+A note on the isoperimetric constant
@@ Property / cites work: A note on the isoperimetric constant / rank @@
+Normal rank
@@ Property / cites work @@
+Q4039749
@@ Property / cites work: Q4039749 / rank @@
+Normal rank
@@ Property / cites work @@
+On the extreme eigenvalues of regular graphs.
@@ Property / cites work: On the extreme eigenvalues of regular graphs. / rank @@
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating Multicut and Sparsest-Cut
+Normal rank
@@ Property / cites work @@
+Q2747613
@@ Property / cites work: Q2747613 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness conductors and constant-degree lossless expanders
+Normal rank
@@ Property / cites work @@
+An Algorithm for the Machine Calculation of Complex Fourier Series
+Normal rank
@@ Property / cites work @@
+Q4507228
@@ Property / cites work: Q4507228 / rank @@
+Normal rank
@@ Property / cites work @@
+Minors in lifts of graphs
@@ Property / cites work: Minors in lifts of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Geometry of cuts and metrics
@@ Property / cites work: Geometry of cuts and metrics / rank @@
+Normal rank
@@ Property / cites work @@
+Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
+Normal rank
@@ Property / cites work @@
+Q4787524
@@ Property / cites work: Q4787524 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3267900
@@ Property / cites work: Q3267900 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3241504
@@ Property / cites work: Q3241504 / rank @@
+Normal rank
@@ Property / cites work @@
+The eigenvalues of random symmetric matrices
@@ Property / cites work: The eigenvalues of random symmetric matrices / rank @@
+Normal rank
@@ Property / cites work @@
+A proof of alon's second eigenvalue conjecture
@@ Property / cites work: A proof of alon's second eigenvalue conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+The Spectra of Infinite Hypertrees
@@ Property / cites work: The Spectra of Infinite Hypertrees / rank @@
+Normal rank
@@ Property / cites work @@
+Some geometric aspects of graphs and their eigenfunctions
+Normal rank
@@ Property / cites work @@
+Relative expanders or weakly relatively Ramanujan graphs.
+Normal rank
@@ Property / cites work @@
+On the second eigenvalue of hypergraphs
@@ Property / cites work: On the second eigenvalue of hypergraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3293678
@@ Property / cites work: Q3293678 / rank @@
+Normal rank
@@ Property / cites work @@
+Explicit constructions of linear-sized superconcentrators
+Normal rank
@@ Property / cites work @@
+A Chernoff Bound for Random Walks on Expander Graphs
+Normal rank
@@ Property / cites work @@
+Geometric algorithms and combinatorial optimization.
+Normal rank
@@ Property / cites work @@
+A Sample of Samplers: A Computational Perspective on Sampling
+Normal rank
@@ Property / cites work @@
+It is easy to determine whether a given integer is prime
+Normal rank
@@ Property / cites work @@
+Every connected regular graph of even degree is a Schreier coset graph
+Normal rank
@@ Property / cites work @@
+Filling Riemannian manifolds
@@ Property / cites work: Filling Riemannian manifolds / rank @@
+Normal rank
@@ Property / cites work @@
+Addendum to ``Random walk in random groups'' by M. Gromov.
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Monotone Circuits for the Majority Function
@@ Property / cites work: Monotone Circuits for the Majority Function / rank @@
+Normal rank
@@ Property / cites work @@
+The size of bipartite graphs with a given girth
@@ Property / cites work: The size of bipartite graphs with a given girth / rank @@
+Normal rank
@@ Property / cites work @@
+A lower bound on the spectral radius of the universal cover of a graph
+Normal rank
@@ Property / cites work @@
+Pseudorandomness for network algorithms
@@ Property / cites work: Pseudorandomness for network algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Q4798347
@@ Property / cites work: Q4798347 / rank @@
+Normal rank
@@ Property / cites work @@
+Extensions of Lipschitz mappings into a Hilbert space
+Normal rank
@@ Property / cites work @@
+Q4519896
@@ Property / cites work: Q4519896 / rank @@
+Normal rank
@@ Property / cites work @@
+Expanders obtained from affine transformations
@@ Property / cites work: Expanders obtained from affine transformations / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate counting, uniform generation and rapidly mixing Markov chains
+Normal rank
@@ Property / cites work @@
+A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
+Normal rank
@@ Property / cites work @@
+Eigenvalues and expansion of regular graphs
@@ Property / cites work: Eigenvalues and expansion of regular graphs / rank @@
+Normal rank
@@ Property / cites work @@
+KAZHDAN CONSTANTS FOR <font>SL</font><sub>n</sub>(ℤ)
+Normal rank
@@ Property / cites work @@
+Symmetric groups and expander graphs.
@@ Property / cites work: Symmetric groups and expander graphs. / rank @@
+Normal rank
@@ Property / cites work @@
+Connection of the dual space of a group with the structure of its closed subgroups
+Normal rank
@@ Property / cites work @@
+Finite simple groups as expanders
@@ Property / cites work: Finite simple groups as expanders / rank @@
+Normal rank
@@ Property / cites work @@
+Q4039790
@@ Property / cites work: Q4039790 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4549227
@@ Property / cites work: Q4549227 / rank @@
+Normal rank
@@ Property / cites work @@
+On the expansion rate of Margulis expanders.
@@ Property / cites work: On the expansion rate of Margulis expanders. / rank @@
+Normal rank
@@ Property / cites work @@
+The geometry of graphs and some of its algorithmic applications
+Normal rank
@@ Property / cites work @@
+Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders
+Normal rank
@@ Property / cites work @@
+Girth and Euclidean distortion
@@ Property / cites work: Girth and Euclidean distortion / rank @@
+Normal rank
@@ Property / cites work @@
+Improved low-density parity-check codes using irregular graphs
+Normal rank
@@ Property / cites work @@
+Not every uniform tree covers Ramanujan graphs
@@ Property / cites work: Not every uniform tree covers Ramanujan graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
+Normal rank
@@ Property / cites work @@
+Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
+Normal rank
@@ Property / cites work @@
+Q4276003
@@ Property / cites work: Q4276003 / rank @@
+Normal rank
@@ Property / cites work @@
+Ramanujan graphs
@@ Property / cites work: Ramanujan graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
+Normal rank
@@ Property / cites work @@
+Random lifts of graphs: perfect matchings
@@ Property / cites work: Random lifts of graphs: perfect matchings / rank @@
+Normal rank
@@ Property / cites work @@
+Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).
+Normal rank
@@ Property / cites work @@
+Finite simple groups of Lie type as expanders.
@@ Property / cites work: Finite simple groups of Lie type as expanders. / rank @@
+Normal rank
@@ Property / cites work @@
+Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
+Normal rank
@@ Property / cites work @@
+Q4273626
@@ Property / cites work: Q4273626 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4208451
@@ Property / cites work: Q4208451 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4071451
@@ Property / cites work: Q4071451 / rank @@
+Normal rank
@@ Property / cites work @@
+Explicit constructions of graphs without short cycles and low density codes
+Normal rank
@@ Property / cites work @@
+Q4530626
@@ Property / cites work: Q4530626 / rank @@
+Normal rank
@@ Property / cites work @@
+The expected eigenvalue distribution of a large regular graph
+Normal rank
@@ Property / cites work @@
+Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
+Normal rank
@@ Property / cites work @@
+Q4856179
@@ Property / cites work: Q4856179 / rank @@
+Normal rank
@@ Property / cites work @@
+New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
+Normal rank
@@ Property / cites work @@
+Q4146667
@@ Property / cites work: Q4146667 / rank @@
+Normal rank
@@ Property / cites work @@
+Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
+Normal rank
@@ Property / cites work @@
+Mathematical Aspects of Mixing Times in Markov Chains
+Normal rank
@@ Property / cites work @@
+Expanders from symmetric codes
@@ Property / cites work: Expanders from symmetric codes / rank @@
+Normal rank
@@ Property / cites work @@
+A product decomposition for the classical quasisimple groups
+Normal rank
@@ Property / cites work @@
+On the second eigenvalue of a graph
@@ Property / cites work: On the second eigenvalue of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Tight estimates for eigenvalues of regular graphs
@@ Property / cites work: Tight estimates for eigenvalues of regular graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness is linear in space
@@ Property / cites work: Randomness is linear in space / rank @@
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+Constructing disjoint paths on expander graphs
@@ Property / cites work: Constructing disjoint paths on expander graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic algorithm for testing primality
@@ Property / cites work: Probabilistic algorithm for testing primality / rank @@
+Normal rank
@@ Property / cites work @@
+Undirected ST-connectivity in log-space
@@ Property / cites work: Undirected ST-connectivity in log-space / rank @@
+Normal rank
@@ Property / cites work @@
+Upper bound on the characters of the symmetric groups
+Normal rank
@@ Property / cites work @@
+Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
+Normal rank
@@ Property / cites work @@
+Design of capacity-approaching irregular low-density parity-check codes
+Normal rank
@@ Property / cites work @@
+A new family of Cayley expanders (?)
@@ Property / cites work: A new family of Cayley expanders (?) / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom walks on regular digraphs and the RL vs. L problem
+Normal rank
@@ Property / cites work @@
+Modern Coding Theory
@@ Property / cites work: Modern Coding Theory / rank @@
+Normal rank
@@ Property / cites work @@
+The capacity of low-density parity-check codes under message-passing decoding
+Normal rank
@@ Property / cites work @@
+Q4340096
@@ Property / cites work: Q4340096 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Entropy waves, the zig-zag graph product, and new constant-degree expanders
+Normal rank
@@ Property / cites work @@
+Q4826727
@@ Property / cites work: Q4826727 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4126536
@@ Property / cites work: Q4126536 / rank @@
+Normal rank
@@ Property / cites work @@
+A Mathematical Theory of Communication
@@ Property / cites work: A Mathematical Theory of Communication / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded generation and Kazhdan's property (T)
@@ Property / cites work: Bounded generation and Kazhdan's property (T) / rank @@
+Normal rank
@@ Property / cites work @@
+Current Trends in Theoretical Computer Science
@@ Property / cites work: Current Trends in Theoretical Computer Science / rank @@
+Normal rank
@@ Property / cites work @@
+How to compute the volume in high dimension?
@@ Property / cites work: How to compute the volume in high dimension? / rank @@
+Normal rank
@@ Property / cites work @@
+Q3392273
@@ Property / cites work: Q3392273 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-time encodable and decodable error-correcting codes
+Normal rank
@@ Property / cites work @@
+A Fast Monte-Carlo Test for Primality
@@ Property / cites work: A Fast Monte-Carlo Test for Primality / rank @@
+Normal rank
@@ Property / cites work @@
+Expander codes
@@ Property / cites work: Expander codes / rank @@
+Normal rank
@@ Property / cites work @@
+Zeta functions of finite graphs and coverings. III
+Normal rank
@@ Property / cites work @@
+Q4650575
@@ Property / cites work: Q4650575 / rank @@
+Normal rank
@@ Property / cites work @@
+A recursive approach to low complexity codes
@@ Property / cites work: A recursive approach to low complexity codes / rank @@
+Normal rank
@@ Property / cites work @@
+Explicit Concentrators from Generalized <i>N</i>-Gons
+Normal rank
@@ Property / cites work @@
+On orthogonal and symplectic matrix ensembles
@@ Property / cites work: On orthogonal and symplectic matrix ensembles / rank @@
+Normal rank
@@ Property / cites work @@
+How to share memory in a distributed system
@@ Property / cites work: How to share memory in a distributed system / rank @@
+Normal rank
@@ Property / cites work @@
+Graph-theoretic properties in computational complexity
+Normal rank
@@ Property / cites work @@
+Q4230829
@@ Property / cites work: Q4230829 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2755077
@@ Property / cites work: Q2755077 / rank @@
+Normal rank
@@ Property / cites work @@
+Spectral norm of random matrices
@@ Property / cites work: Spectral norm of random matrices / rank @@
+Normal rank
@@ Property / cites work @@
+On the distribution of the roots of certain symmetric matrices
+Normal rank
@@ Property / cites work @@
+Q4263664
@@ Property / cites work: Q4263664 / rank @@
+Normal rank
@@ Property / cites work @@
+Expanders that beat the eigenvalue bound: Explicit construction and applications
+Normal rank
@@ Property / cites work @@
+Q3002782
@@ Property / cites work: Q3002782 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1090/s0273-0979-06-01126-8
+Normal rank
@@ Property / OpenAlex ID @@
+W2018047324
@@ Property / OpenAlex ID: W2018047324 / rank @@
+Normal rank