-
FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores
Introduction 이번 글에서는 작년 11월에 처음 arXiv에 게재되었고 ICLR 2024 poster로 발표될 예정인 FlashFFTConv에 대해 다루어 보고자 한다. 먼저 introduction에서는 논문과 조금 다르게 필자가 생각하는 motivation들을 적어 보고자 한다. Scaling Law of LLM Scaling Laws for Neural Language Models는 OpenAI에서 연구한 결과를 정리한 article로, 다음 [Figure 1]의 결과를 제시한다. [Figure 1]은 여러 metric들이 지수적으로 증가함에 따라, LLM의 성능이 개선되는 것을 잘 보여주고 있다. 이러한 transformer 기반 모델의 특성은 현재 LLM을 NLP의 중심으로 만들었을 뿐만 아니라...
-
카운팅 테크닉
개요 AtCoder에서 문제를 풀다 보면 백준 온라인 저지나 한국의 대학생 대회에서와 다르게 경우의 수, 기댓값, 확률을 묻는 조합론 문제들이 더 자주 등장한다는 사실을 관찰할 수 있습니다. 한 대회에 출제된 문제 절반 이상에서 $\pmod{998244353}$이 등장해서 너무 과하다고 느껴질 때도 있을 정도입니다. 이 글에서는 제가 문제를 풀면서 자주 보았던 유형들을 몇 가지 선정해서 소개해 보려고 합니다. 각 유형마다 이를 해결하는 테크닉을 소개(널리 통용되는 이름이 없다면 적당히 이름을 붙였습니다)하고, 연습 문제로 AtCoder Regular Contest에서 등장했던 문제를 2개씩 선정했습니다....
-
Garbled Circuit and Functional Encryption
Introduction 이 글에서는 Multi-party computation(MPC)에서 사용되는 Garbled Circuit과 Oblivious Transfer에 대해 알아볼 것입니다. 그 뒤에는 public key encryption을 확장한 개념인 Functional Encryption이라는 개념을 소개할 것입니다. 배경지식이 크게 필요하지 않도록 작성했기 때문에, 암호학에 관심이 있는 독자들에게 흥미를 줄 수 있기를 바랍니다. Garbled Circuit Garbled Circuit(GC) 는 두 사람 $Alice$와 $Bob$이 각각 input $x$와 $y$를 갖고 있을 때, 서로에게 자신의 input을 노출하지 않고 $f(x,y)$를 계산하는 two-party computation을 위해 고안되었습니다. 이는 필자의 직전 포스트인 two-party communication 모델과 동일하지만,...
-
기하 문제를 스스로 해결하는 AI
2024년 1월 17일, Solving olympiad geometry without human demonstrations이라는 논문이 Nature에 실렸습니다. 논문에 따르면, AlphaGeomtery라는 AI가 IMO(국제 수학 올림피아드)에 출제된 기하 문제 30개 중 무려 25개를 스스로 해결하였으며, 이는 IMO 금메달리스트의 성적 평균에 준하는 수준이라 합니다. 해당 글에서는 논문의 내용을 간단히 정리한 후, AI의 실제 풀이를 구체적으로 살펴보며 AI의 성능을 분석해보려 합니다. Background AI 연구에서 관심받던 주제 중 하나로, 스스로 증명을 구축하는 AI의 개발은 이전부터 다양한 연구가 진행되어 왔습니다. 해당 연구의 가장 큰 장벽은, 사람의...
-
Proximity Testing with Logarithmic Randomness
Code-Based PCS의 복습 Linear code $V$에 대하여, 벡터 $x$와 $V$의 거리를 \[d(x, V) = \lVert x - V \rVert_0 = \min_{y \in V} (\lVert x - y \rVert_0)\] 또, 행렬 $X$와 $V$의 거리를 각 column이 전부 $V$의 원소인 행렬 $Y$에 대하여, $X - Y$가 갖는 non-zero row의 최소 개수라고 정의한다. 이 거리의 정의를 기반으로, $q$-close와 $q$-far를 정의할 수 있다. 이때, code-based PCS의 안정성을 증명하는 가장 핵심적인 결과는 \[\left\lVert \sum_{i=1}^n r_i x_i - V \right\rVert_0 \le...