Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
이 논문은 공간 민감형 압축 오라클 기법을 개발함으로써 레이블 대칭성 하에서의 충돌 찾기 및 원소 판별 문제에 대한 타이트한 시간-공간 하한을 확립하며, 이러한 알고리즘이 쿼리와 의 자원을 요구함을 증명함으로써 이 범주 내에서 BHT 및 Ambainis의 양자 워크와 같은 기존 양자 알고리즘의 최적성을 확인한다.