Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
From MaRDI portal
Publication:920104
zbMath0708.05030MaRDI QIDQ920104
Publication date: 1988
Published in: Problems of Information Transmission (Search for Journal in Brave)
Related Items
On the Origins, Nature, and Impact of Bourgain’s Discretized Sum-Product Theorem, The complexity of error-correcting codes, The Graph Curvature Calculator and the Curvatures of Cubic Graphs, Graphs with high second eigenvalue multiplicity, Assouad-Nagata dimension and gap for ordered metric spaces, Gap sets for the spectra of cubic graphs, A simple proof for the lower bound of the girth of graphs \(D(n,q)\), A spectral bound for vertex-transitive graphs and their spanning subgraphs, Kneser's method of neighbors, On sparse parity check matrices (extended abstract), On the eigenvalues of the graphs \(D(5,q)\), Paradigms for Unconditional Pseudorandom Generators, Explicit non-malleable codes from bipartite graphs, Equitable partition for some Ramanujan graphs, Turán‐type problems for long cycles in random and pseudo‐random graphs, Interactions of computational complexity theory and mathematics, Mixing in High-Dimensional Expanders, On the family of cubical multivariate cryptosystems based on the algebraic graph over finite commutative rings of characteristic 2, Keyed hash function from large girth expander graphs, On the parallel approximability of a subclass of quadratic programming., Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity, Unnamed Item, Sparse and limited wavelength conversion in all-optical tree networks, Ramanujan Graphs for Post-Quantum Cryptography, Distributed Corruption Detection in Networks, A fast new algorithm for weak graph regularity, Unnamed Item, On the Expansion of Group-Based Lifts, Infinite series of quaternionic 1-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes, The Ramanujan conjecture and its applications, From Ramanujan graphs to Ramanujan complexes, Certifiably Pseudorandom Financial Derivatives, Explicit Near-Ramanujan Graphs of Every Degree, On the Expansion of Group-Based Lifts, What Do Networks and Elliptic Curves Have in Common?, Tensor quasi-random groups, Shift lifts preserving Ramanujan property, Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling, Tight products and graph expansion, Hash functions and Cayley graphs, Quantum ergodicity for quantum graphs without back-scattering, Tough Ramsey graphs without short cycles, Explicit construction of graphs with an arbitrary large girth and of large size, Graphs, Vectors, and Matrices, Linear-time list recovery of high-rate expander codes, Upper bounds on the bisection width of 3- and 4-regular graphs, On small world semiplanes with generalised Schubert cells, Cutoff on all Ramanujan graphs, Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes, The eigenvalues of the graphs \(D(4,q)\), From the geometry of box spaces to the geometry and measured couplings of groups, New spectral lower bounds on the bisection width of graphs, On the chromatic number of structured Cayley graphs, Strong uniform expansion in \(\text{SL}(2,p)\)., A characterization of the components of the graphs \(D(k,q)\), Spectrum and combinatorics of two-dimensional Ramanujan complexes, Ramanujan coverings of graphs, Pseudorandom generators for combinatorial checkerboards, On regular hypergraphs of high girth, Optimal strong approximation for quadrics over \(\mathbb{F}_q [t\)], Local Kesten-McKay law for random regular graphs, Constructions of permutation arrays for certain scheduling cost measures, Cayley-type graphs for group-subgroup pairs, Low-distortion embeddings of graphs with large girth, On Multivariate Cryptosystems Based on Computable Maps with Invertible Decomposition, Ramanujan graphs and exponential sums over function fields, Expanders and property A., Edge rigidity and universality of random regular graphs of intermediate degree, On families of graphs of large cycle indicator, matrices of large order and key exchange protocols with nonlinear polynomial maps of small degree, On the comparison of cryptographical properties of two different families of graphs with large cycle indicator, Box spaces, group extensions and coarse embeddings into Hilbert space, Constraints, MMSNP and expander relational structures, Optimal induced universal graphs for bounded-degree graphs, Almost-Ramanujan graphs and prime gaps, On the connectivity of certain graphs of high girth., Embeddable box spaces of free groups, Ramanujan complexes and high dimensional expanders, New bounds on even cycle creating Hamiltonian paths using expander graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, An Elementary Construction of Constant-Degree Expanders, Formal Zeta function expansions and the frequency of Ramanujan graphs, Regular graphs of large girth and arbitrary degree, On the second eigenvalue of a graph, On the spectral gap and the diameter of Cayley graphs, Expansion of random graphs: new proofs, new results, Matching nuts and bolts faster, Explicit expanders of every degree and size, Corrigendum to: ``Almost-Ramanujan graphs and prime gaps, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, On eigenvalues of random complexes, Quasirandom Cayley graphs, Cycle lengths in sparse graphs, Lifts, derandomization, and diameters of Schreier graphs of Mealy automata, Quasi-local algebras and asymptotic expanders, On sparse spanners of weighted graphs, Laplace eigenvalues of graphs---a survey, Cubic Ramanujan graphs, Combinatorial algorithms for distributed graph coloring, Optimal slope selection via expanders, Clumsy packings of graphs, Highly symmetric expanders, Logarithmic reduction of the level of randomness in some probabilistic geometric constructions, A lower bound on the spectral radius of the universal cover of a graph, Spectra of lifted Ramanujan graphs, Toughness in graphs -- a survey, Optimal strong approximation for quadratic forms, A note on the Size-Ramsey number of long subdivisions of graphs, On the girth of random Cayley graphs, Super-expanders and warped cones, On universal hypergraphs, The chromatic number of random Cayley graphs, Recent progress in combinatorial random matrix theory, Character sums, automorphic forms, equidistribution, and Ramanujan graphs Part I. The Kloosterman sum conjecture over function fields, Ramanujan graphs and expander families constructed from \(p\)-ary bent functions, Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey, On the homogeneous algebraic graphs of large girth and their applications, An explicit infinite family of \(\mathbb{M}\)-vertex graphs with maximum degree \(K\) and diameter \([1+o(1)\log_{K-1}\mathbb{M}\) for each \(K-1\) a prime power], Expander graphs based on GRH with an application to elliptic curve cryptography, The Littlewood-Offord problem for Markov chains, The integrity of a cubic graph, Hypergraph expanders from Cayley graphs, Hamiltonian paths in Cayley graphs, Ramanujan graphs on cosets of \(\operatorname{PGL}_2(\mathbb F_q)\), Kazhdan groups have cost 1, On the second eigenvalue of hypergraphs, Kissing numbers of regular graphs, Ramanujan edge-indexed graphs, Regular honest graphs, isoperimetric numbers, and bisection of weighted graphs, On the decisional complexity of problems over the reals, Median eigenvalues and the HOMO-LUMO index of graphs, Local correctability of expander codes, Interlacing families. I: Bipartite Ramanujan graphs of all degrees, New and explicit constructions of unbalanced Ramanujan bipartite graphs, Ramanujan complexes of type \(\widetilde A_d\), Synchronization of coupled chaotic maps, Wavelength routing in optical networks of diameter two
