Expander graphs and their applications (Q3514498)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Expander graphs and their applications	scientific article

Statements

scholarly article

0 references

Expander graphs and their applications (English)

0 references

zbMATH Open document ID

0 references

10.1090/S0273-0979-06-01126-8

0 references

0 references

0 references

0 references

Bulletin of the American Mathematical Society

0 references

publication date

21 July 2008

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs

0 references

Pseudorandom Generators in Propositional Proof Complexity

0 references

Explicit construction of linear sized tolerant networks

0 references

Smaller Explicit Superconcentrators

0 references

The non-backtracking spectrum of the universal cover of a graph

0 references

Derandomized graph products

0 references

Random Lifts of Graphs: Edge Expansion

0 references

Random graph coverings. I: General theory and graph connectivity

0 references

On-Line Algorithms for Path Selection in a Nonblocking Network

0 references

Proof verification and the hardness of approximation problems

0 references

Random lifts of graphs: Independence and chromatic number

0 references

Eigenvalues and expanders

0 references

On the Edge-Expansion of Graphs

0 references

\(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

0 references

Random Cayley graphs and expanders

0 references

Expander flows, geometric embeddings and graph partitioning

0 references

0 references

Hamilton cycles in random lifts of graphs

0 references

Inequalities in Fourier analysis

0 references

0 references

On codes from hypergraphs.

0 references

The complexity of testing whether a graph is a superconcentrator

0 references

Lifts, discrepancy and nearly optimal spectral gap

0 references

Are Bitvectors Optimal?

0 references

0 references

0 references

Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)

0 references

On Lipschitz embedding of finite metric spaces in Hilbert space

0 references

On the complexity of an optimal non-blocking commutation scheme without reorganization

0 references

On the complexity of approximating the independent set problem

0 references

Short proofs are narrow—resolution made simple

0 references

A note on the isoperimetric constant

0 references

0 references

On the extreme eigenvalues of regular graphs.

0 references

On the hardness of approximating Multicut and Sparsest-Cut

0 references

0 references

Randomness conductors and constant-degree lossless expanders

0 references

An Algorithm for the Machine Calculation of Complex Fourier Series

0 references

0 references

Minors in lifts of graphs

0 references

Geometry of cuts and metrics

0 references

Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks

0 references

0 references

0 references

0 references

The eigenvalues of random symmetric matrices

0 references

A proof of alon's second eigenvalue conjecture

0 references

The Spectra of Infinite Hypertrees

0 references

Some geometric aspects of graphs and their eigenfunctions

0 references

Relative expanders or weakly relatively Ramanujan graphs.

0 references

On the second eigenvalue of hypergraphs

0 references

0 references

Explicit constructions of linear-sized superconcentrators

0 references

A Chernoff Bound for Random Walks on Expander Graphs

0 references

Geometric algorithms and combinatorial optimization.

0 references

A Sample of Samplers: A Computational Perspective on Sampling

0 references

It is easy to determine whether a given integer is prime

0 references

Every connected regular graph of even degree is a Schreier coset graph

0 references

Filling Riemannian manifolds

0 references

Addendum to ``Random walk in random groups'' by M. Gromov.

0 references

Clique is hard to approximate within \(n^{1-\epsilon}\)

0 references

Monotone Circuits for the Majority Function

0 references

The size of bipartite graphs with a given girth

0 references

A lower bound on the spectral radius of the universal cover of a graph

0 references

Pseudorandomness for network algorithms

0 references

0 references

Extensions of Lipschitz mappings into a Hilbert space

0 references

0 references

Expanders obtained from affine transformations

0 references

Approximate counting, uniform generation and rapidly mixing Markov chains

0 references

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

0 references

Eigenvalues and expansion of regular graphs

0 references

KAZHDAN CONSTANTS FOR <font>SL</font><sub>n</sub>(ℤ)

0 references

Symmetric groups and expander graphs.

0 references

Connection of the dual space of a group with the structure of its closed subgroups

0 references

Finite simple groups as expanders

0 references

0 references

0 references

On the expansion rate of Margulis expanders.

0 references

The geometry of graphs and some of its algorithmic applications

0 references

Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders

0 references

Girth and Euclidean distortion

0 references

Improved low-density parity-check codes using irregular graphs

0 references

Not every uniform tree covers Ramanujan graphs

0 references

Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)

0 references

Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity

0 references

0 references

Ramanujan graphs

0 references

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

0 references

Random lifts of graphs: perfect matchings

0 references

Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).

0 references

Finite simple groups of Lie type as expanders.

0 references

Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski

0 references

0 references

0 references

0 references

Explicit constructions of graphs without short cycles and low density codes

0 references

0 references

The expected eigenvalue distribution of a large regular graph

0 references

Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)

0 references

0 references

New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities

0 references

0 references

Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds

0 references

Mathematical Aspects of Mixing Times in Markov Chains

0 references

Expanders from symmetric codes

0 references

A product decomposition for the classical quasisimple groups

0 references

On the second eigenvalue of a graph

0 references

Tight estimates for eigenvalues of regular graphs

0 references

Randomness is linear in space

0 references

0 references

Constructing disjoint paths on expander graphs

0 references

Probabilistic algorithm for testing primality

0 references

Undirected ST-connectivity in log-space

0 references

Upper bound on the characters of the symmetric groups

0 references

Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates

0 references

Design of capacity-approaching irregular low-density parity-check codes

0 references

A new family of Cayley expanders (?)

0 references

Pseudorandom walks on regular digraphs and the RL vs. L problem

0 references

Modern Coding Theory

0 references

The capacity of low-density parity-check codes under message-passing decoding

0 references

0 references

Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

0 references

Entropy waves, the zig-zag graph product, and new constant-degree expanders

0 references

0 references

0 references

A Mathematical Theory of Communication

0 references

Bounded generation and Kazhdan's property (T)

0 references

Current Trends in Theoretical Computer Science

0 references

How to compute the volume in high dimension?

0 references

0 references

Linear-time encodable and decodable error-correcting codes

0 references

A Fast Monte-Carlo Test for Primality

0 references

0 references

Zeta functions of finite graphs and coverings. III

0 references

0 references

A recursive approach to low complexity codes

0 references

Explicit Concentrators from Generalized <i>N</i>-Gons

0 references

On orthogonal and symplectic matrix ensembles

0 references

How to share memory in a distributed system

0 references

Graph-theoretic properties in computational complexity

0 references

0 references

0 references

Spectral norm of random matrices

0 references

On the distribution of the roots of certain symmetric matrices

0 references

0 references

Expanders that beat the eigenvalue bound: Explicit construction and applications

0 references

0 references

full work available at URL

https://doi.org/10.1090/s0273-0979-06-01126-8

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:3514498

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q3514498&oldid=37318396"