-
Push Relabel Algorithm (2)
2월의 Push-Relabel algorithm 관련 글에 이어서 Push-relabel에 기반한 다항 시간 MCMF 알고리즘 (Cost Scaling)에 대해서 다룰 예정이다. 이 글에서는 일반적으로 알려진 Successive Shortest Path Algorithm보다 훨씬 더 효율적인 알고리즘을 다룬다. MCMF (Minimum-Cost Maximum-Flow) 문제는 알고리즘 대회 입문서에 다 소개되어 있는 중요한 문제이다. 2월 중순에 글이 올라온 뒤, 3월 1일 Almost-Linear Time Minimum Cost Flow 가 가능하다는 사실이 알려져서 많은 화제를 모았다. 당연하지만 이론전산에서 아주 중요한 연구 결과이고, 저자들은 아마 권위있는 상 하나 정도는 수상하지 않을까...
-
Finite Nimber 계산
Aeren 님의 Nimber 포스트에서도 알 수 있듯이 $2^{2^k}$ 미만의 음이 아닌 정수는 nimber 덧셈(xor)과 nimber 곱에 대해서 체를 이룹니다. 이 글에서는 finite nimber에 대해서 nimber 곱, 제곱근, 곱셈 역원 등을 실제로 계산하기 위한 알고리즘을 소개합니다. https://www.ics.uci.edu/~eppstein/numth/를 참고했습니다. 기본 규칙 이 파트에서 소개하는 성질을 포함해서 앞으로 nimber의 몇가지 성질을 증명하지 않고 주어진 것으로 받아들이도록 하겠습니다. Nimber는 체를 이루므로 덧셈, 곱셈에 대해서 교환 법칙, 결합 법칙, 분배 법칙 등이 성립합니다. 따라서 앞으로 표기에서 불필요한 괄호를 생략하고, 곱셈은...
-
Vision Transformer (1)
들어가며 현재 컴퓨터 비전에서 가장 뜨거운 주제 중 하나는 vision transformer (ViT) 이다. 2017년에 발표되었지만 벌써 4만 번 가까이 인용된 [](https://arxiv.org/pdf/2010.11929.pdf) 논문 이후 본래 자연어처리를 위해 고안된 transfomer를 컴퓨터 비전에 사용하기 위한 연구가 이루어졌고, 2021년 ICLR에서 Google Brain 팀이 [<An Image Is Worth 16X16 Words: Transformers for Image Recognition at Scale>](https://arxiv.org/abs/2010.11929)라는 제목으로 ViT를 발표하면서 ViT를 image recognition, object detection, image restoration 등 수많은 컴퓨터 비전의 태스크에 적용한 연구가 쏟아져 나왔다. ViT를 소개하기 앞서 오늘은 transformer가...
-
암호학의 안전성 증명 테크닉
1. Introduction 안녕하세요, 이번 글에서는 암호학에서 특정 구조에 대한 안전성을 증명하는 테크닉을 알아보겠습니다. 이 테크닉을 통해 실제 Feistel cipher의 안전성을 증명해볼 것입니다. 2. 암호학의 안전성 암호학의 안전성에 대해서는 지금으로부터 대략 1년 전에 이미 포스팅을 한 적이 있습니다. Indistinguishability(구분 불가능성)이라는 용어를 처음 들어보신다면 해당 포스팅을 먼저 확인해보시는걸 추천드립니다. 이전 글에서도 언급했듯 Indistinguishability는 달성이 굉장히 어려운 성질입니다. 또한 만약 어떤 암호 체계가 랜덤한 메시지와 구분 불가능하다는건 공격자의 입장에서 그 어떤 방법으로 공격을 시도하더라도 아무런 의미있는 정보를 얻을...
-
Casual Inference and Diagram
Introduction Simpson’s Paradox 한 제약회사가 어떤 질병에 대해 치료제를 개발한 후 이 치료제가 실제로 효과가 있는지 700명의 환자들을 대상으로 실험을 진행하였다. 환자들의 3개월간 회복 경과를 지켜본 결과 아래와 같이 나타났다. 치료제 사용 치료제 미사용 남성 81/87 회복 (93%) 234/270 회복 (87%) 여성 192/263 회복 (73%) 55/80 회복 (69%) 합산 273/350 회복 (78%) 289/350 회복 (83%) 각각의 성별에 대해서는 분명 치료제를 사용한 경우에 더 회복률이 높았지만, 합산 회복률은 치료제를 사용하지 않았을 때 오히려 더 높게...