Random Cayley graphs and expanders

DOI10.1002/rsa.3240050203zbMath0798.05048OpenAlexW2057648657MaRDI QIDQ4286294

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

zbMATH Keywords

eigenvalue Cayley graph adjacency matrix random graph expander

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Quantum hashing for finite abelian groups, On quantum \((\delta,\varepsilon)\)-resistant hashing, Partition expanders, KAZHDAN CONSTANTS OF GROUP EXTENSIONS, Flexibility and movability in Cayley graphs, Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations, Secure computation using leaky correlations (asymptotically optimal constructions), Random walks supported on random points of \(Z/nZ\), Eigenvalues of Cayley graphs, Group representations that resist random sampling, Expander Construction in VNC1, Expanding Generating Sets for Solvable Permutation Groups, Tough Ramsey graphs without short cycles, On the Banach-Space-Valued Azuma Inequality and Small-Set Isoperimetry of Alon–Roichman Graphs, Secure Computation from Leaky Correlated Randomness, Random Latin square graphs, Binary quantum hashing, Expansion properties of Cayley graphs of the alternating groups, Thin \(\text{II}_1\) factors with no Cartan subalgebras, EXPANDER GRAPHS AND SIEVING IN COMBINATORIAL STRUCTURES, On sensitivity in bipartite Cayley graphs, The Graph Curvature Calculator and the Curvatures of Cubic Graphs, Hamiltonian normal Cayley graphs, Expander construction in \(\mathrm{VNC}^1\), Combinatorics. Abstracts from the workshop held January 1--7, 2023, Geometry of random Cayley graphs of abelian groups, Classical and Quantum Computations with Restricted Memory, On rigid matrices and \(U\)-polynomials, Nilprogressions and groups with moderate growth, Expander graphs and their applications, Mixing time and expansion of non-negatively curved Markov chains, RAMANUJAN CAYLEY GRAPHS OF FROBENIUS GROUPS, Communication constraints in the average consensus problem, Unnamed Item, Spectral expansion of random sum complexes, Towards dimension expanders over finite fields, Small Sample Spaces Cannot Fool Low Degree Polynomials, An Elementary Construction of Constant-Degree Expanders, Cayley graphs and complexity geometry, \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials, The hardest halfspace, Comparison of Metric Spectral Gaps, Attacking quantum hashing. Protocols and their cryptanalysis, Highly symmetric expanders, The diameter of a random Cayley graph of ℤ q, The Euclidean distortion of the lamplighter group., Closed walks and eigenvalues of abelian Cayley graphs, Symmetric groups and expanders, On the girth of random Cayley graphs, The size-Ramsey number of trees, The chromatic number of random Cayley graphs, Hamiltonian cycles in normal Cayley graphs, Bakry–Émery Curvature Functions on Graphs, Eigenvalue Ratios of Non-Negatively Curved Graphs, NONEXISTENCE OF A CIRCULANT EXPANDER FAMILY, An average John theorem, Expander graphs based on GRH with an application to elliptic curve cryptography, Bounded budget connection (BBC) games or how to make friends and influence people, on a budget, Mixing and covering in the symmetric groups, Generating an equidistributed net on a sphere using random rotations, Babai's conjecture for high-rank classical groups with random generators, Outlaw distributions and locally decodable codes, Balanced Hashing, Color Coding and Approximate Counting, Enumeration and random walks on finite groups, On random random walks, Hypergraph expanders from Cayley graphs, Random Schreier graphs and expanders, Hamiltonian paths in Cayley graphs, Analysis of properties of quantum hashing, Spectral estimates for abelian Cayley graphs

Cites Work