On the Complexity of Identifying Strongly Regular Graphs
In this paper, we show that Graph Isomorphism (GI) is not $\textsf{AC}^{0}$-reducible to several problems, including the Latin Square Isotopy problem, isomorphism testing of several families of Steiner designs, and isomorphism testing of conference graphs. As a corollary, we obtain that GI is not $\...
Kaydedildi:
| Yazar: | |
|---|---|
| Materyal Türü: | Makale |
| Baskı/Yayın Bilgisi: |
2022
|
| Konular: | |
| Online Erişim: | https://arxiv.org/abs/2207.05930 http://arxiv.org/abs/2207.05930 |
| Etiketler: |
Etiket eklenmemiş, İlk siz ekleyin!
|