Samsung Software Membership
    • BLOG
    • ABOUT US

    S/W 멤버십 기술 블로그

    • leejseo's profile image

      leejseo

      January 24, 2024

      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$는 짝수인...

      graph

    • billcho's profile image

      billcho

      December 28, 2023

      CUDA #01: Introduction to Many-Core Programming

      Introduction Many-Core Programming Many-core processor는 많은 수의 core를 가져 대규모의 병렬 연산이 가능한 프로세서를 의미하며, 이를 활용하는 것을 many-core programming이라고 부른다. 유사한 용어인 multi-core는 수~수십 개 정도의 core들에 대한 의미를 주로 포함하는 것과는 달리, many-core는 그보다 훨씬 많은 수천~수만 개의 core들에 대하여 사용한다. 최근 many-core programming은 GPU(Graphics Processing Unit)가 게임, 계산과학, 인공지능 등 다양한 workload들을 처리하기 시작하면서 매우 중요해지고 있는 추세이다. 특히 GPT, ViT 등 Transformer 기반의 거대 AI 모델들은 실수의 행렬곱이라는 병렬화가 매우 잘...

      parallel cuda many-core

    • ainta's profile image

      ainta

      December 26, 2023

      Communication complexity

      Introduction two-party model of deterministic communication (늘 그렇듯이) Alice와 Bob이라는 이름의 두 사람이 있다. 함수 $f: X \times Y \rightarrow Z$에 대해, Alice는 $x \in X$, Bob은 $y \in Y$를 알고 있을 때 두 사람이 $f(x,y)$를 최소 bit의 커뮤니케이션으로 알아내는 것이 목표이다. 즉, 목표는 $f(x,y)$의 값을 두 명이 알아내는 것이고, cost가 주고받은 bit의 개수일 때 cost를 minimize하는 문제이다. 먼저 여러 가지 $f$의 예를 살펴보며 각각 어떤 방식으로 해결하는 것이 확인해 보자. Example 1. $EQ_n: \{...

      complexity theory

    • edenooo's profile image

      edenooo

      December 25, 2023

      플로우 그래프 커팅

      개요 Problem Solving을 하다 보면, 주어진 문제에서 플로우 그래프를 모델링했을 때 그래프의 크기가 너무 커서 단순히 플로우 알고리즘을 사용할 경우에 시간 초과를 받게 되는 상황이 종종 발생합니다. 이 글에서는 위와 같은 상황에서 추가적인 관찰을 통해 플로우 그래프의 크기를 줄이는 몇 가지 방법을 소개합니다. 문제마다 필요한 관찰과 해결 방법이 제각기 다를 수 있으므로 다양한 연습 문제를 예시로 들어서 설명하겠습니다. 디닉 알고리즘의 구현체를 통일하기 위해 AtCoder Library의 MaxFlow를 사용하겠습니다. 연습 문제 AtCoder Beginner Contest 320 G. Slot...

      algorithm graph-theory maximum-flow

    • cs71107's profile image

      cs71107

      December 25, 2023

      Secure Matrix Multiplication with Homomorphic Encryption - 1

      Introduction 동형암호 (Homomorphic Encryption)은 암호문간의 연산을 평문의 정보유출 없이 가능하게 하는 암호 scheme입니다. 간단하게 말해서, 어떤 두 plaintext $m_0, m_1$을 encrypt한 것이 $ct_0, ct_1$이라고 할 때, $dec(ct_0+ct_1) = m_0 + m_1$이 성립합니다. 동형암호 scheme 중에서도, 두 가지 연산, 즉 addition과 multiplication을 제한 없이 사용할 수 있다면 그런 동형암호 scheme을 Fully Homomorphic Encryption, 줄여서 FHE라고 부릅니다. 현재 나와 있는 대부분의 동형암호 scheme의 경우, RLWE problem의 Hardness에 의존하고 있습니다. 대표적인 FHE scheme으로는 BGV, BFV, CKKS, TFHE 등이...

      cryptography

    • Previous Page
    • 11
    • 12
    • 13
    • 14
    • 15
    • Next Page
    • github
    • facebook
    • instagram
    • youtube
    • S/W Membership

    Copyright © SAMSUNG SOFTWARE MEMBERSHIP. All rights reserved.