통신 복잡도와 분산 표현의 지문

분산된 두 표현이 같은가

Alice와 Bob이 각각 8비트 표현 x,y를 가지고 있다고 합시다. Alice는 한 번만 메시지를 보내고 Bob이 두 값이 같은지 결정합니다. 입력 분포 가정은 없고 공개 프로토콜은 사전에 고정합니다. 계산 시간보다 전송하는 비트 수를 묻는 문제입니다.

원문을 모두 보내면 8비트로 정확히 판정합니다. k<8비트의 결정론 메시지로 항상 정확할 수는 없습니다. 256개 입력을 2ᵏ개 메시지로 보내면 같은 메시지를 내는 서로 다른 x,x′가 있습니다. Bob의 입력이 x일 때 두 경우의 메시지는 같은데 필요한 판정은 달라 모순입니다.

단순 절단과 난수 지문

낮은 k비트만 보내면 x=0,y=128은 k=3에서 모두 000입니다. 이를 같다고 판정하면 거짓 양성입니다. 이웃 거리나 의미 유사성을 보존하는 표현 문제와도 다릅니다. 현재 과제는 비트열의 정확한 동일성 하나입니다.

공개된 균등 8비트 행 r와 x의 GF(2) 내적을 전송해 봅시다. 차이 δ=x XOR y가 0이 아니면 r·δ는 공정한 비트입니다. δ에서 1인 한 위치를 택하면 그 r 비트를 뒤집는 일대일 대응이 내적 0과 1인 행을 짝짓기 때문입니다.

독립한 행과 오류 확률

공유한 k개의 독립 균등 행으로 k비트 지문을 만듭니다. 서로 다른 고정 입력 쌍이 모든 행에서 충돌할 확률은 2⁻ᵏ입니다. 같은 입력은 항상 같은 지문이므로 거짓 음성은 없습니다. 이 보장은 난수를 보기 전에 고정한 입력 쌍과 독립 공개 난수에 대한 것이며, 행을 본 뒤 공격자가 입력을 고르는 다른 모형에는 그대로 적용할 수 없습니다.

k=3이면 이상 충돌 확률은 1/8입니다. k=0이면 아무 메시지도 보내지 않고 항상 같다고 하므로 서로 다른 쌍의 오류가 1입니다. k=8의 무작위 행도 선형 종속일 수 있어 충돌 확률 1/256이지만, 8비트 원문 전송은 정확합니다.

실습의 고정 seed가 뜻하는 것

실습의 파랑은 이상적인 공개 난수 모형의 고정 쌍 충돌 확률, 주황은 결정론 절단의 최악 경우 오류입니다. 서로 다른 평가 기준이므로 같은 표본의 두 오류율로 읽지 마세요. 같은 입력을 선택하면 파란 곡선은 0이지만, 절단의 전체 입력 쌍에 대한 최악 경우 곡선은 그대로입니다. 표의 공개 mask는 재현 가능한 작은 생성 규칙으로 만든 한 실행 예시입니다. 이 고정 seed의 행들이 독립 균등하다는 보장은 붙이지 않습니다.

공유 난수 모형에서는 mask 전송 비용을 따로 세지 않습니다. 실제 분산 시스템에서 mask를 공유·갱신해야 하면 그 통신도 포함해야 합니다. 학습한 임베딩 차원 수만으로 네트워크 전송량이나 정확 동일성 보장을 추론할 수 없습니다.

확인 문제와 해설

1. 내적 행 256개를 모두 검사하면 비영 차이의 충돌 행은? 128개입니다. 앞의 비트 반전 짝짓기로 정확히 반반입니다.
2. 지문이 같으면 원문도 같은가요? 보장하지 않습니다. 충돌이 가능하며 같은 지문은 후보 필터로 쓸 수 있습니다.
3. 공개 난수는 공짜 물리 자원인가요? 아니요. 이는 통신 복잡도 모형의 공유 가정입니다. 실제 배포의 동기화 비용은 별도입니다.

추가 읽기: Stanford CS369E, Randomized Communication Complexity.