Key points are not available for this paper at this time.
모든 k ≥ 2에 대해 C₂₊-자유성을 O(n^{1-1/k}) 라운드에서 결정할 수 있음을 보입니다. 이는 오류 확률이 1/3인 무작위 몬테카를로 분산 알고리즘에 의해 모델에서 수행됩니다. 이는 Drucker et al. PODC'14 및 Censor-Hillel et al. DISC'20에 의해 알려진 알고리즘의 k=2, 3, 4, 5에 대한 최상의 라운드 복잡성과 일치하지만, Eden et al. DISC'19에 의해 알려진 k>5에 대한 알고리즘의 복잡성을 O(n^{1-2/k²}) 형태에서 개선합니다. 우리의 알고리즘은 임계값을 가진 색상 BFS 탐색을 사용하나, 최근 Fraigniaud et al. SIROCCO'23가 제시한 지역 임계값을 사용한 색상 BFS 탐색으로 사이클을 감지하는 것에 대한 불가능성을 극복할 수 있도록 하는 원래의 글로벌 접근 방식을 활용합니다. 또한 C₂₊ 자유성을 결정하기 위한 양자 설정에서 O(n^{1{2-12k}}) 라운드 복잡성을 달성하기 위해 우리의 알고리즘을 양자화하는 방법도 보여줍니다. 더 나아가, 이는 van Apeldoorn과 de Vos가 PODC'22에서 제시한 최대 길이 2k의 사이클 감지 문제를 위한 알려진 양자 복잡성을 개선할 수 있도록 합니다. 우리의 양자화는 두 단계로 이루어지며, 첫째, 우리의 무작위 알고리즘의 혼잡도를 줄이는 대신 성공 확률도 줄어듭니다. 둘째, 순차 알고리즘에서 유도된 새로운 양자 프레임워크를 사용하여 성공 확률을 높입니다. 즉 몬테카를로 양자 증폭을 사용합니다.
Fraigniaud et al. (Mon,)이 이 질문을 연구했습니다.