-
Hash Functions Monolith for ZK Applications: May the Speed of SHA-3 be With You
이 내용은 https://eprint.iacr.org/2023/1025.pdf 의 요약입니다. ZK Friendly Hash Function의 필요성 해시함수는 굉장히 많은 곳에서 사용되고 있습니다. 그런만큼 ZKP 상에서도 해시함수의 계산에 대한 증명을 하게 될 필요가 상당히 많습니다. 그런데 일반적인 해시함수는 일반적인 컴퓨팅 환경에서 빠르게 작동하는 것을 목표로 하기 때문에, 비트 연산 등을 많이 활용합니다. 이는 비트 연산을 다루는 비용이 큰 ZKP 상에서는 큰 문제로 작용합니다. 이에 따라, ZKP 상에서 비용이 적은, 즉 적은 constraint로 증명을 할 수 있는 해시함수를 만드는 것이 필요해졌습니다. 또한, ZKP...
-
A 1.5-Approximation for s-t Path TSP
이 글에서는 cost function이 metric인 경우에 대해서만 논의한다. 1. Introduction 외판원 문제(Traveling Salesman Problem)와 s-t 경로 외판원 문제(s-t path TSP)는 다음과 같이 정의된다. Traveling Salesman Problem. 완전 그래프 $G = (V, E)$ 와 간선 집합 $E$ 상의 metric cost function $c$가 있을 때, $G$의 모든 정점을 순회하고 돌아오는 최소 cost의 cycle을 구하여라. s-t Path Traveling Salesman Problem. 완전 그래프 $G = (V, E)$ 와 그 상의 두 정점 $s$, $t$ 및 간선 집합 $E$ 상의...
-
Separating Hyperplanes, Lagrange Multipliers, KKT Conditions, and Convex Duality
2021년 발표된 Minimum Cost Flow가 Almost-Linear Time에 풀린다는 결과는 현대적인 Convex Optimization 기법들이 전통적인 알고리즘 문제를 해결하는 아주 강력한 도구를 제공함을 보여주는 상징적인 순간이라고 할 수 있다. 요즘은 기계 학습의 인기가 워낙 엄청나기 때문에 Convex Optimization은 대개 기계 학습의 관점에서 다뤄지지만, Convex Optimization은 현대 전산학 전반에 있어서 중요도가 아주 높으며, 그래프 알고리즘적인 관점에서 Convex Optimization을 다뤘을 때 얻어갈 수 있는 것이 아주 많다. 최근 관심 있는 학생들과 함께 ETH Zurich의 Advanced Graph Algorithms and Optimization...
-
Dulmage-Mendelsohn Decomposition (Part 1)
개요 이 글에서는 Dulmage-Mendelsohn Decomposition의 개념과 성질을 소개하고 이를 구하는 방법에 대해서 다룹니다. Dulmage-Mendelsohn Decomposition의 코드와 PS에서의 활용은 다음으로 이어지는 글에서 다루겠습니다. 사전 지식으로 이분 매칭과 SCC를 알고 있다고 가정하고 진행하겠습니다. Dulmage-Mendelsohn Decomposition(DM 분해)는 이분 그래프의 모든 최대 매칭의 구조를 알아내기 위해서 정점 집합을 여러 개의 부분집합들로 unique하게 분할하는 방법입니다. 구체적으로 예를 들면, DM 분해를 사용해서 아래와 같은 질문들에 대해 빠르게 답변할 수 있습니다. 주어진 이분 그래프의 각 정점 $u$에 대해, 모든 최대 매칭에서 $u$가...
-
SmoothMix: a Simple Yet Effective Data Augmentation to Train Robust Classifiers (CVPRW 2020)
SmoothMix: a Simple Yet Effective Data Augmentation to Train Robust Classifiers SmoothMix는 제가 앞서 소개했던 RandomMix, SAGE 등에 비하면 꽤나 오래전에 나온 논문입니다. 그렇기 때문에 해당 논문에서 baseline들로 비교하고 있는 기법들도 꽤나 기본적인 것들만을 사용하여 비교하고 있으며 엄청 특출난 성능을 보인다고 보기는 어렵습니다. 그러나 해당 mixup 방법 및 발견한 model의 이미지에서의 visualization attention, 그리고 data augmentation이 어떻게 Robustness에 영향을 줄 수 있는지 에 대한 기초적인 접근 방향의 아이디어를 찾을 수 있습니다. 최근에 computer vision과 data...