Huffman-Bucket Sketch: A Simple Algorithm for Cardinality Estimation
이 논문은 HyperLogLog 스케치를 최적의 공간 효율성으로 압축하면서도 병합 가능성과 업데이트 효율성을 유지하는 새로운 데이터 구조인 '허프먼 버킷 스케치 (HBS)'를 제안하고, 그 이론적 성능과 실용성을 입증합니다.
💻 Category
cs.DS
87 편의 논문
Simple minimally unsatisfiable subsets of 2-CNFs
이 논문은 2-CNF 부울 공식의 최소 불만족 부분집합 (MUS) 을 식별하는 선형 시간 절차를 제시하고, 특정 조건을 만족하는 MUS 의 존재 여부 판별 및 탐색이 다항 시간 내에 가능함을 증명하며, 2-CNF 의 MUS 난이도 지형을 규명하기 위한 향후 연구 방향을 논의합니다.
Linear-Scaling Tensor Train Sketching
이 논문은 텐서 트레인 형식에 특화된 블록 희소 텐서 트레인 (BSTT) 스케치를 도입하여 기존 방법들을 통합하고, 텐서 차수 와 부분공간 차원 에 대해 선형적으로만 의존하는 효율적인 이론적 보장과 수치적 검증을 제시합니다.
Separating Oblivious and Adaptive Differential Privacy under Continual Observation
이 논문은 스트리밍 알고리즘의 개인정보보호 모델인 '연속 관찰'에서, 사전에 고정된 데이터 흐름을 가정하는 무관심 (oblivious) 설정과 알고리즘 출력에 기반해 데이터가 선택되는 적응적 (adaptive) 설정 간의 근본적인 차이를 최초로 명확히 증명하여, 무관심 설정에서는 지수적으로 긴 시간 동안 정확한 -DP 알고리즘이 존재하지만 적응적 설정에서는 상수 개수의 시간 단계 후에도 정확성을 보장할 수 없음을 보여줍니다.
Instruction set for the representation of graphs
이 논문은 임의의 유한 단순 그래프를 9 개 문자 명령어 알파벳으로 구성된 compact 한 문자열로 인코딩하여, 모든 문자열이 유효한 그래프로 디코딩되고 그래프 편집 거리와 강한 상관관계를 보이는 IsalGraph 라는 새로운 표현 방법을 제시합니다.
Testing Graph Properties with the Container Method
이 논문은 그래프 컨테이너 방법 (graph container method) 을 확장하여 밀집 그래프 모델에서 -클릭 존재 여부 및 -색칠 가능성 테스트에 필요한 샘플 복잡도 한계를 거의 최적 수준으로 증명합니다.
Online Flexible Busy Time Scheduling on Heterogeneous Machines
이 논문은 이질적인 머신 환경에서 온라인으로 도착하는 작업들을 마감 기한 내에 스케줄링하여 총 비용을 최소화하는 문제를 연구하며, 단위 길이 작업에 대해 8-경쟁 알고리즘을 제안하고 비포함 구간 설정에서 하한이 2 임을 증명합니다.
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
이 논문은 갈라이 - 밀그람 정리를 확장하여 독립수 (independence number) 를 매개변수로 하는 고정 매개변수 tractable (FPT) 알고리즘을 제시함으로써, 주어진 그래프가 개 미만의 경로로 커버될 수 있는지 판별하는 문제를 해결하고, 이를 통해 3 이하의 독립수를 가진 그래프의 해밀턴 경로 존재 여부 판별 등 다양한 그래프 문제에 대한 새로운 알고리즘적 통찰을 제공합니다.
-Motif: Parallel Subgraph Isomorphism via Tabular Operations
이 논문은 데이터베이스 조인 및 필터링 연산을 GPU 병렬 처리에 적용하여 기존 알고리즘 대비 최대 595 배의 속도 향상을 달성하고 양자 회로 최적화 등 다양한 분야에서 고성능 서브그래프 동형성 문제를 해결하는 '-Motif'라는 새로운 알고리즘을 제안합니다.
Space-efficient B-tree Implementation for Memory-Constrained Flash Embedded Devices
이 논문은 메모리 제약이 있는 임베디드 장치를 위해 B-트리의 다양한 변형을 개발하고 실험적으로 평가하여, 이러한 장치에서도 효율적인 인덱싱이 가능하며 저장소 특화 최적화를 통해 성능을 크게 향상시킬 수 있음을 입증했습니다.
How to Sort in a Refrigerator: Simple Entropy-Sensitive Strictly In-Place Sorting Algorithms
이 논문은 메모리 제약이 있는 임베디드 시스템 (예: 냉장고) 을 위해 입력 데이터 외에 O(1) 의 추가 메모리만 사용하면서도 입력 배열의 런 기반 엔트로피에 기반한 최적 시간 복잡도인 O(n(1 + H(A))) 을 달성하는 최초의 비교 기반 정렬 알고리즘 두 가지를 제안합니다.
Agnostic learning in (almost) optimal time via Gaussian surface area
이 논문은 가우스 표면적 를 갖는 개념 클래스의 아노스틱 학습 복잡도를 기존 차수에서 차수로 개선하여 통계적 쿼리 모델에서 다항식 임계 함수 학습의 (거의) 최적 경계를 제시합니다.
Forwarding Packets Greedily
이 논문은 2014 년에 제기된 오픈 문제인 온라인 패킷 전달 문제에서, 각 패킷이 1 개 또는 2 개의 라우터만 통과해야 하는 특수한 경우에 대해 기존에 고려되지 않았던 그리드 알고리즘이 개의 활성 라우터 수에 따라 $2-2^{1-k}4/3$임을 보임으로써 해당 문제에 대한 첫 번째 진전을 이루었습니다.
Transversal Rank, Conformality and Enumeration
이 논문은 초그래프의 횡단 랭크 (transversal rank) 판별 및 최소 히팅 집합 열거를 위해 '선도 (look-ahead)' 기법을 도입하여 실행 시간을 개선하고, 이를 더 최적화하는 것이 -준형 (conformal) 초그래프 인식 및 균일 초그래프의 최대 하이퍼클릭 열거와 동치임을 증명합니다.
Induced Minors and Coarse Tree Decompositions
이 논문은 완전 이분 그래프와 격자 그래프를 유도 마이너로 배제하는 그래프가 로그 다항식 크기의 거리 16-독립수 제한을 가진 거친 트리 분해 구조를 가진다는 Chudnovsky 등의 추측을 약화시킨 형태로 증명했습니다.
Graph Generation Methods under Partial Information
이 논문은 이분, 방향, 무방향 네트워크의 차수 시퀀스를 가진 그래프 생성 문제를 해결하기 위해 순차적 방법을 제안하고, 전역 실현 가능성을 보장하는 조건을 규명하여 대규모 인스턴스에 확장 가능한 효율적인 열거 및 샘플링 알고리즘을 개발했습니다.
The Complexity of Distance- Dominating Set Reconfiguration
이 논문은 거리- 지배 집합 재구성 문제에서 일 때 -완전인 분할 그래프가 일 때 에 속한다는 복잡도 이분법을 증명하고, 트리에서의 선형 시간 알고리즘을 제시하며, 평면 그래프 및 이분 그래프 등 다른 그래프 클래스에 대한 -완전성 결과를 확장합니다.
Weighted Reservoir Sampling With Replacement from Data Streams
이 논문은 데이터 스트림에서 가중치에 비례하는 확률로 요소를 복원 추출하는 새로운 1-pass 샘플링 알고리즘을 제안하고, 그 정확성과 효율성을 이론적으로 증명하며 실험을 통해 기존 최첨단 방법들과의 성능을 비교 분석합니다.
Efficient Computation of Time-Index Powered Weighted Sums Using Cascaded Accumulators
이 논문은 캐스케이드 적분기를 활용하여 시간 인덱스 거듭제곱 가중합을 계산할 때 저장 공간 없이 곱셈 횟수를 회로 줄여 실시간 처리 효율성을 극대화하는 새로운 방법을 제안합니다.
On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
이 논문은 양의 분해적 제약 조건 하의 최단 경로 문제에 대한 매개변수 복잡성 연구를 통해, 해의 크기나 H 의 구조적 속성을 매개변수로 하여 다항 커널화 및 고정 매개변수 가용성 결과를 제시합니다.