Random Cayley graphs and expanders
From MaRDI portal
Publication:4286294
DOI10.1002/RSA.3240050203zbMATH Open0798.05048OpenAlexW2057648657MaRDI QIDQ4286294FDOQ4286294
Publication date: 27 April 1994
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240050203
Recommendations
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)
Cites Work
- Eigenvalues and expanders
- Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
- Ramanujan graphs
- Characteristic vectors of bordered matrices with infinite dimensions
- Title not available (Why is that?)
- On the distribution of the roots of certain symmetric matrices
- On the second eigenvalue of a graph
- On the second eigenvalue and random walks in random \(d\)-regular graphs
- Some geometric aspects of graphs and their eigenfunctions
- Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Construction of a Thin Set with small Fourier Coefficients
Cited In (88)
- The hardest halfspace
- Bakry–Émery Curvature Functions on Graphs
- Babai's conjecture for high-rank classical groups with random generators
- Spectral expansion of random sum complexes
- Attacking quantum hashing. Protocols and their cryptanalysis
- Comparison of Metric Spectral Gaps
- Highly symmetric expanders
- On random random walks
- Closed walks and eigenvalues of abelian Cayley graphs
- Balanced Hashing, Color Coding and Approximate Counting
- Random walks supported on random points of \(Z/nZ\)
- \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials
- On sensitivity in bipartite Cayley graphs
- Quantum hashing for finite abelian groups
- Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem
- Cayley graphs and complexity geometry
- KAZHDAN CONSTANTS OF GROUP EXTENSIONS
- Title not available (Why is that?)
- Eigenvalues of Cayley graphs
- Secure computation using leaky correlations (asymptotically optimal constructions)
- Random Latin square graphs
- Flexibility and movability in Cayley graphs
- Analysis of properties of quantum hashing
- The diameter of a random Cayley graph of ℤ q
- On the girth of random Cayley graphs
- Tough Ramsey graphs without short cycles
- The size-Ramsey number of trees
- Addendum to ``Random walk in random groups by M. Gromov.
- An Elementary Construction of Constant-Degree Expanders
- Hamiltonian normal Cayley graphs
- The Euclidean distortion of the lamplighter group.
- Spectral estimates for abelian Cayley graphs
- Binary quantum hashing
- On rigid matrices and \(U\)-polynomials
- Expander Construction in VNC1
- Hamiltonian cycles in normal Cayley graphs
- Enumeration and random walks on finite groups
- Discrepancy and eigenvalues of Cayley graphs
- An average John theorem
- Title not available (Why is that?)
- NONEXISTENCE OF A CIRCULANT EXPANDER FAMILY
- Nilprogressions and groups with moderate growth
- On quantum \((\delta,\varepsilon)\)-resistant hashing
- Group representations that resist random sampling
- Hamiltonian paths in Cayley graphs
- Secure Computation from Leaky Correlated Randomness
- The Graph Curvature Calculator and the Curvatures of Cubic Graphs
- Partition expanders
- Symmetric groups and expanders
- Random Schreier graphs and expanders
- The chromatic number of random Cayley graphs
- Generating an equidistributed net on a sphere using random rotations
- On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon-Roichman graphs
- RAMANUJAN CAYLEY GRAPHS OF FROBENIUS GROUPS
- Expander graphs and their applications
- Towards dimension expanders over finite fields
- Expander construction in \(\mathrm{VNC}^1\)
- Hypergraph expanders from Cayley graphs
- Eigenvalue Ratios of Non-Negatively Curved Graphs
- Expansion properties of Cayley graphs of the alternating groups
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Mixing and covering in the symmetric groups
- Thin \(\text{II}_1\) factors with no Cartan subalgebras
- Title not available (Why is that?)
- Title not available (Why is that?)
- Expander graphs based on GRH with an application to elliptic curve cryptography
- Title not available (Why is that?)
- Title not available (Why is that?)
- Small Sample Spaces Cannot Fool Low Degree Polynomials
- Random subgraphs of Cayley graphs over \(p\)-groups
- Classical and Quantum Computations with Restricted Memory
- Communication constraints in the average consensus problem
- Geometry of random Cayley graphs of abelian groups
- On the largest product-free subsets of the alternating groups
- Outlaw distributions and locally decodable codes
- Characterizations of \(B\)-valued concentration inequalities via the Rademacher type
- EXPANDER GRAPHS AND SIEVING IN COMBINATORIAL STRUCTURES
- Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
- Random balanced Cayley complexes
- Hamilton cycles in pseudorandom graphs
- Universality and sharp matrix concentration inequalities
- Bounded budget connection (BBC) games or how to make friends and influence people, on a budget
- Expanding Generating Sets for Solvable Permutation Groups
- Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations
- Title not available (Why is that?)
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- Mixing time and expansion of non-negatively curved Markov chains
- Cutoff for non-negatively curved Markov chains
This page was built for publication: Random Cayley graphs and expanders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4286294)
