Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem
이 논문은 Lévy 과정으로 인덱스를 해싱하는 새로운 아이디어를 제시하여 -모멘트 추정을 위한 범용 스케치 기법을 개발하고, Lévy-Khintchine 정리를 통해 추정 가능한 함수의 범위를 체계적으로 규명하며 기존 기법들을 통합하고 다차원 및 이질적 모멘트 추정으로 확장 가능한 이론적 틀을 마련했습니다.
💻 Category
cs.DS
87 편의 논문
Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces
이 논문은 Hadamard 공간에서 선형 구조의 부재로 인한 어려움을 극복하기 위해 Busemann 함수에 기반한 새로운 하위 기울기 (subgradient) 개념을 도입하고, 이를 통해 확률적 및 점진적 하위 기울기 방법의 일반화와 복잡성 보장을 가능하게 하여 BHV 트리 공간의 중앙값 계산 등 다양한 최적화 문제에 적용할 수 있음을 제시합니다.
Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
이 논문은 기존 TSPTW 벤치마크 인스턴스의 구조적 취약점을 간파하여 50 개 이상의 고객으로 구성된 모든 사례를 초단위로 해결하는 정밀 알고리즘을 제시함으로써, 해당 인스턴스들이 더 이상 문제의 난이도를 평가하거나 머신러닝 학습용 데이터셋으로 적합하지 않음을 경고합니다.
Time warping with Hellinger elasticity
이 논문은 임의의 거리 공간에 있는 시계열 데이터 매칭을 위해 헬링거 커널을 스트레칭 패널티로 사용하는 '탄성 시간 왜곡 (Elastic Time Warping)' 알고리즘을 제안하며, 이는 의 계산 복잡도를 가집니다.
bsort: A theoretically efficient non-comparison-based sorting algorithm for integer and floating-point numbers
이 논문은 정수와 부동소수점 숫자를 위한 이진 퀵소트에서 유래한 비비교 기반 정렬 알고리즘 'bsort'를 제안하며, 이는 작은 단어 크기의 데이터 유형에서 시간 복잡도와 보조 공간으로 실행되어 최적화된 하이브리드 알고리즘과 경쟁력 있는 성능을 보입니다.
Unit Interval Selection in Random Order Streams
이 논문은 무작위 순서 스트리밍 모델에서 단위 구간 선택 문제를 해결하여, 기존 적대적 순서 모델의 2/3 근사 한계를 깨고 공간으로 0.7401 의 기대 근사율을 달성하는 알고리즘을 제시하고, 8/9 이상의 근사율 달성을 위해서는 공간이 필요함을 증명합니다.
A PTAS for Weighted Triangle-free 2-Matching
이 논문은 가중치 삼각형-프리 2-매칭 문제에 대해 기존에 알려진 2/3 근사 알고리즘을 개선하여, 임의의 에 대해 다항 시간 -근사 알고리즘 (PTAS) 을 제시합니다.
Fast and Optimal Differentially Private Frequent-Substring Mining
이 논문은 기존 연구의 비효율적인 공간 및 시간 복잡도를 획기적으로 줄이면서도 근사 최적의 오차 보장을 유지하는 새로운 -차별 프라이버시 알고리즘을 제안하여, 대규모 사용자 데이터에서 빈번한 부분 문자열을 효율적으로 마이닝하는 방법을 제시합니다.
Better Bounds for the Distributed Experts Problem
이 논문은 명의 전문가가 개의 서버에 분산된 환경에서 손실 함수를 고려할 때, 이전 연구보다 향상된 통신 비용으로 regret 을 최소화하는 새로운 프로토콜을 제안합니다.
On the Online Weighted Non-Crossing Matching Problem
이 논문은 유클리드 평면에서 비교차 제약 조건 하에 온라인으로 도착하는 가중치 점들의 매칭 문제를 연구하여, 결정론적 알고리즘의 한계를 밝히고 무작위화를 통한 상수 경쟁비 달성 가능성, 다양한 변형 문제에 대한 경계, 그리고 최적해를 위한 조언 복잡도 상한을 제시합니다.
A Critical Pair Enumeration Algorithm for String Diagram Rewriting
이 논문은 대칭 모노이드 범주에서 프라베니우스 구조가 없는 문자열 다이어그램 재작성 시스템의 모든 임계 쌍을 열거하고 그 정확성과 포괄성을 증명하여, 임계 쌍 분석을 자동화하는 알고리즘을 제시합니다.
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
이 논문은 저차원 유클리드 공간에서 -median 및 -means 클러스터링 문제에 대해 기존 결과를 개선한 거의 최적의 상한 알고리즘을 제시하고, 갭 지수 시간 가설 하에서 거의 일치하는 하한을 증명합니다.
Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
이 논문은 선호도에 동점과 하한 할당량이 존재하는 다대다 매칭 환경에서 하한 할당량을 최대한 충족하는 '크리티컬' 매칭과 '완화된 안정성'을 동시에 만족하는 매칭이 항상 존재함을 증명하고, 최대 크기의 그러한 매칭을 구하는 NP-난해 문제에 대해 다항 시간 내 근사 알고리즘을 제시합니다.
Optimizing Sparse SYK
본 논문은 희소화된 SYK 모델에서 특정 조건 하에 고전적 가우스 상태 알고리즘과 호스팅스-오도넬의 양자 알고리즘 간에 근사 해를 찾는 데 있어 계산 복잡도 격차가 여전히 존재함을 증명합니다.
Privately Estimating Black-Box Statistics
이 논문은 민감도 상한이 알려지지 않은 임의의 블랙박스 함수에 대해 통계적 효율성과 오라클 효율성 사이의 균형을 이루며 근사적으로 최적의 차분 프라이버시 추정 기법을 제안하고 그 최적성을 증명합니다.
Exploration Space Theory: Formal Foundations for Prerequisite-Aware Location-Based Recommendation
이 논문은 지식 공간 이론을 위치 기반 추천에 적용하여 방문 순서의 전제 조건을 격자 이론으로 형식화하고, 이를 바탕으로 구조적 유효성 보장을 제공하는 '탐색 공간 추천 시스템 (ESRS)'을 제안합니다.
Multi-Agent Reinforcement Learning with Submodular Reward
이 논문은 에이전트 간 기여도가 중복되는 현실적 시나리오를 모델링하는 협력적 다중 에이전트 강화학습을 위해, 하모듈성 보상을 고려한 새로운 프레임워크를 제시하고 알려진 동역학 하에서는 다항 시간 복잡도로 1/2-근사 해를, 알려지지 않은 동역학 하에서는 UCB 기반 알고리즘을 통해 regret bound 를 보장하는 알고리즘을 제안합니다.
A Class of Unrooted Phylogenetic Networks Inspired by the Properties of Rooted Tree-Child Networks
이 논문은 NP-난해한 '트리-차일드 오 rientable' 네트워크의 한계를 극복하고, 다항 시간 인식과 트리 포함 문제의 다항 시간 해결이 가능한 새로운 무방향 계통 네트워크 클래스인 '-컷터블 네트워크'를 제안합니다.
Complexity Lower Bounds of Small Matrix Multiplication over Finite Fields via Backtracking and Substitution
이 논문은 대입법과 체계적인 백트래킹 기법을 결합하여 유한체에서 행렬 곱셈의 쌍선형 복잡도 하한을 증명하는 새로운 방법을 제시하고, 이를 통해 위의 $3 \times 3$ 행렬 곱셈 복잡도 하한을 기존 19 에서 20 으로 개선하는 자동화된 증명을 제시합니다.
Approximating Tensor Network Contraction with Sketches
이 논문은 기존 방법론이 순환 구조를 지원하지 못하거나 계산 복잡도가 지수적으로 증가하는 한계를 극복하여, 순환 텐서 네트워크를 포함한 임의의 텐서 네트워크 곱셈을 근사할 수 있는 새로운 스케치 기법과 다항 시간 복잡도를 갖는 개선된 알고리즘을 제안합니다.