On the automorphism groups of strongly regular graphs. I

DOI10.1145/2554797.2554830MaRDI QIDQ2988892zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On the automorphism groups of strongly regular graphs. II.
• scientific article; zbMATH DE number 1256777
• GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
• Faster canonical forms for primitive coherent configurations (extended abstract)
• Quasipolynomial-time canonical form for steiner designs

Cites work

• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• (Leveled) fully homomorphic encryption without bootstrapping
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Evaluating Branching Programs on Encrypted Data
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Fully homomorphic encryption using ideal lattices
• Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
• New lattice-based cryptographic constructions
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• Public-key cryptosystems from the worst-case shortest vector problem
• Toward basing fully homomorphic encryption on worst-case hardness
• Trapdoors for hard lattices and new cryptographic constructions
• Trapdoors for lattices: simpler, tighter, faster, smaller

Cited in

(17)

• On the automorphism groups of strongly regular graphs. II.
• On fixity of arc-transitive graphs
• Faster canonical forms for primitive coherent configurations (extended abstract)
• Applications of dimensionality reduction and exponential sums to graph automorphism
• The QAP-polytope and the graph isomorphism problem
• \(r\)-regular families of graph automorphisms
• On the automorphism groups of rank-4 primitive coherent configurations
• A characterization of Johnson and Hamming graphs and proof of Babai's conjecture
• On automorphisms of strongly regular graphs with $ \lambda=0$, $ \mu=2$
• Vertex-primitive digraphs with large fixity
• scientific article; zbMATH DE number 3908464 (Why is no real title available?)
• On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
• On the complexity of identifying strongly regular graphs
• On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
• On the number of fixed points of automorphisms of vertex-transitive graphs
• On the spectral gap and the automorphism group of distance-regular graphs
• Strongly regular graphs with non-trivial automorphisms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988892)