-
기하 문제를 스스로 해결하는 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...
-
HE Sanitization - Washing Machine
Introduction 지금까지는 주로 동형암호(Homomorphic Encryption)의 scheme들에 관해 글을 써왔는데, 이번 글에서는 동형암호와 관련돼 있는 연구 분야 중 하나인 Circuit Privacy에 관련된 Sanitization에 관련된 글을 써보려고 합니다. 이 글에서는 Ducas - Stehlé Washing machine에 대해서 중점적으로 설명하도록 하겠습니다. 원 논문은 이 링크에서 확인하실 수 있습니다. Backgrounds Homomorphic Encryption 동형암호 (Homomorphic Encryption)은 암호문간의 연산을 평문의 정보유출 없이 가능하게 하는 암호 scheme입니다. 지금까지 쓴 글들에 설명이 자세하게 나와 있으니, 자세한 설명은 생략하겠습니다. Bootstrapping 동형암호들의 경우 error를 필수적으로 가지게...
-
Learning shallow quantum circuits
올해 1월 18일, Learning shallow quantum circuits라는 제목의 연구가 arxiv에 올라왔고, 가장 큰 양자정보 학회인 QIP에서 해당 논문을 가지고 발표까지 진행되었다. 이 연구는 양자 회로를 학습하던 방식을 바꿔놓을 가능성이 있는 연구이고, 어쩌면 Quantum Machine Learning(QML)의 미래 자체에 영향을 줄 수도 있을것 같아 보인다. 굉장히 좋은 아이디어도 얻어갈 것이 많은 연구라고 생각하여서 공유해보고자 한다. 요약 이 논문에서 해결하고자 하는 문제는 두 가지이다. Unknown unitary $U$에 여러 입력으로 여러 번 접근할 수 있을 때, 최대한 가까운 unitary...
-
Degree Bounded Travel Salesman Problem
1. Introduction 우리가 아는 일반적인 TSP(Travel Salesman Problem) 문제는 간선에 가중치가 있는 연결 그래프 $G = (V, E, c) (c : E \to \mathbb{R}_{\ge 0})$ 가 주어질 때 아무 정점에서 시작해 다른 모든 정점을 방문하고 다시 시작 정점으로 돌아오는 최소 비용의 이동 방법을 구하는 문제이다. 이 글에서는 Degree Bounded TSP 문제에 대해 ISAAC 2022에서 발표된 내용을 다룬다. 이 문제에서는 각 정점에 차수 제한 $b_v \ge 0 (v \in V)$ 가 추가적으로 주어진다. (단, $b_v$는 짝수인...