-
An Automatic System to Detect Equivalence Between Iterative Algorithms
논문 링크 : https://arxiv.org/abs/2105.04684 논문 저자 : Shipu Zhao, Laurent Lessard, Madeleine Udell Introduction : Optimization Algorithms and Their Equivalence 수학적 최적화에는 문제를 해결하기 위한 다양한 알고리즘이 있습니다. 각 알고리즘은 그 형태를 통해서 우리에게 최적화에 대한 직관을 주기도 하고 훌륭한 성능으로 우리가 최적화 문제를 어떻게 해결할 수 있는지 알려줍니다. 이는 이미 작성했던 여러 글에서도 강조했던 내용입니다. 예를 들어, 단순히 smooth differentiable convex function $f$를 최소화하는 문제에는 여러 알고리즘이 있고, 특히 Accelerated Gradient Method를 기반으로 하는...
-
Introduction To Retroactivity
Table Of Contents Introduction Preliminaries Operations Partial Retroactivity Full Retroactivity Runtime General Retroactivity Specific Retroactivity Queue Deque Union-Find Priority-Queue Summary Introduction 안녕하세요, Aeren입니다! Persistent data structure는 어떤 data structure의 여러 상태를 저장하면서 임의의 상태로부터의 연산을 통해 도달한 새로운 상태를 관리할 수 있게 합니다. 이렇게 만들어진 상태들의 관계는 tree 구조룰 이루게 되죠. 이번 글에서 소개할 내용은 이와 대비되는 개념인 retroactive data structure입니다. Retroactive data structure에서 각 상태들의 관계는 line graph형태로 고정되있습니다. 그리고 어떤 상태가 연산을 통해...
-
서로 다른 수와 쿼리
개요 다음 문제를 생각해 봅시다. 수열과 쿼리 5 길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$과 쿼리 $Q$개가 주어집니다. $i$번 쿼리마다 $l_i, r_i$가 주어지면, $[l_i,r_i]$ 구간에 존재하는 서로 다른 수의 개수를 구해야 합니다. ($1 \leq N \leq 10^5, 1 \leq Q \leq 10^5, 1 \leq A_i \leq 10^6, 1 \leq l_i \leq r_i \leq N$) 위 문제(이하 서로 다른 수와 쿼리 문제)는 problem solving을 하다 보면 가끔 맞닥뜨리게 되는데, 유명한 문제인 만큼 $O(N\sqrt{Q})$나 $O((N+Q)\log{N})$등의 다양한 풀이...
-
Wireless Digital Communication 2
서론 지난 글에서 아주 기본적인 (noise가 없는) Binary modulation / demodulation에 대해서 알아보고, 현재 통신 시스템에서 가장 쉽게 볼 수 있는 AWGN 채널에 대해서 간략하게 알아보았습니다. 이번 글에서는 지난 글에서 짧게 언급한 AWGN 채널에 대해 좀 더 자세히 다룰 예정입니다. 또한 AWGN 채널에서의 Binary modulation / demodulation에 대해서 데이터가 잘못 전송될 확률을 구하고, 기존 Binary에서 이를 M개의 bit로 확장시킨 M-ary modulation / demodulation에 대해서 알아보도록 하겠습니다. 본론 AWGN 채널 지난 글에서 작성한 내용을 잠깐 언급하고...
-
Zero Knowledge Proof using AES
1. Introduction 이전에 썼던 글들을 통해 MPC를 이용해 Zero-Knowledge Proof를 만들 수 있다 Fiat-Shamir Transform을 이용해 Zero-Knowledge Proof을 Non-Interactive로 변경할 수 있다 NIZK를 통해 전자 서명을 만들 수 있다 는 것을 알게 되었습니다. 이미 RSA 혹은 ECC 등을 이용한 전자서명이 존재하지만 RSA 혹은 ECC 등은 아직 증명되지 않은 정수론/대수학적 안전성을 가정해야 하는 반면, MPC를 이용한 전자서명은 오로지 해시 함수의 안전성에만 의존한다는 장점이 있습니다. 더 나아가 양자컴퓨터가 개발된 이후에도 안전한 양자 내성 성질을 가지고 있습니다. 전자서명을...