On the automorphism groups of strongly regular graphs I

DOI10.1145/2554797.2554830zbMath1365.05202OpenAlexW2064091274MaRDI QIDQ2988892

László Babai

Publication date: 19 May 2017

Published in: Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2554797.2554830

zbMATH Keywords

algorithmsstrongly regular graphsautomorphism groupsisomorphism testing

Mathematics Subject Classification ID

Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Association schemes, strongly regular graphs (05E30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (10)

On fixity of arc-transitive graphs ⋮ On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ The QAP-polytope and the graph isomorphism problem ⋮ On the automorphism groups of rank-4 primitive coherent configurations ⋮ Unnamed Item ⋮ On the automorphism groups of strongly regular graphs. II. ⋮ On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions ⋮ A characterization of Johnson and Hamming graphs and proof of Babai's conjecture ⋮ On the spectral gap and the automorphism group of distance-regular graphs ⋮ On the number of fixed points of automorphisms of vertex-transitive graphs

Cites Work

• Unnamed Item
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• (Leveled) fully homomorphic encryption without bootstrapping
• Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Trapdoors for hard lattices and new cryptographic constructions
• Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
• Evaluating Branching Programs on Encrypted Data
• Bounds for Width Two Branching Programs
• Fully homomorphic encryption using ideal lattices
• Public-key cryptosystems from the worst-case shortest vector problem
• Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
• New lattice-based cryptographic constructions
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: On the automorphism groups of strongly regular graphs I