A symmetric recursive algorithm for mean-payoff games
이 논문은 평균 보상 게임을 해결하기 위한 새로운 결정론적 대칭 재귀 알고리즘을 제안합니다.
💻 Category
cs.DS
87 편의 논문
Succinct QUBO formulations for permutation problems by sorting networks
이 논문은 비교-교환 네트워크를 활용하여 개의 이진 변수만으로 치환 문제를 표현하는 새로운 QUBO 형식을 제안함으로써, 기존 치환 행렬 인코딩보다 변수 수와 상호작용 밀도가 크게 감소된 효율적인 모델을 제시합니다.
Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks
이 논문은 DHT 핑거 테이블과 패시브 안정화 기법을 활용하여 메시지 복잡도를 줄이고 글로벌 조정 없이도 임의의 네트워크 분할에 견고한 일관성을 보장하는 '구조화된 속삭임 DNS(Structured Gossip DNS)'를 제안합니다.
The Theory and Practice of Computing the Bus-Factor
이 논문은 프로젝트의 인적 리스크를 정량화하는 '버스 지수'를 계산하기 위해 사람과 작업을 이분 그래프로 모델링한 통합 프레임워크를 제안하고, 기존 방법의 한계를 극복하며 NP-난해 문제를 해결하는 효율적인 근사 알고리즘과 더 안정적이고 정보적인 새로운 측정 지표를 개발했습니다.
The Li-Chao Tree: Algorithm Specification and Analysis
이 논문은 경쟁 프로그래밍 커뮤니티에서 널리 사용되지만 공식적인 학술 규격이 부재했던 '리차오 트리'에 대한 최초의 공식 명세서를 제시하며, 완전한 알고리즘 사양, 형식적 정확성 증명, 이론적 복잡도 분석 및 실증적 성능 평가를 포함합니다.
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
이 논문은 행과 열의 순서 제약 조건을 가진 격자 퍼즐의 해 존재 조건을 분석하고, 해의 개수를 훅 길이 공식으로 계산하며, 해가 없는 경우의 최소 수정 알고리즘을 제시하고 일반화된 버전의 NP-완전성을 증명합니다.
Sampling Colorings with Fixed Color Class Sizes
이 논문은 다변수 다항식의 기하학적 프레임워크를 활용하여 조건에서 균형 잡힌 그래프 색칠을 다항 시간 내에 무작위 표본 추출하는 알고리즘을 제시하고, 이를 통해 균등 색칠의 존재성을 증명하며 색칠 클래스 크기에 대한 다변수 국소 중심극한정리를 확립합니다.
Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
이 논문은 1 차원에서 상관관계가 있는 두 점 집합 간의 매칭을 추론하는 베이지안 문제에서, 부분 매칭 모델에서는 국소 알고리즘으로 사후 분포를 근사할 수 있고 무한 부피 극한이 잘 정의됨을 보였으며, 완전 매칭 모델의 경우에도 전역 정렬과 흐름 개념을 도입하면 국소 근사와 극한 정의가 가능함을 증명했습니다.
A note on approximating the average degree of bounded arboricity graphs
본 논문은 bounded arboricity 그래프의 평균 차수를 근사하는 Eden, Ron, Seshadhri 의 기존 알고리즘을 파라미터 탐색으로 인한 로그 인자 손실 없이 명확하게 제시하고, 쿼리 복잡도로 -근사치를 제공하는 알고리즘을 상세히 설명합니다.
Faster shortest-path algorithms using the acyclic-connected tree
이 논문은 그래프를 선형 시간으로 분해하는 '비순환 연결 (A-C) 트리'를 도입하여 최단 경로 알고리즘의 시간 복잡도를 그래프의 중첩 너비에 따라 개선하고, 특정 그래프 클래스에 대해 선형 시간 알고리즘을 제시합니다.
Computational Complexity in Property Testing
이 논문은 속성 테스트에서 쿼리 복잡도와 시간 복잡도 간의 관계를 체계적으로 연구하여 시간 - 쿼리 위계 정리를 제시하고, -SUM 가설과 통계적 쿼리 모델을 기반으로 반공간 (halfspace) 문제에서 두 복잡도 간의 본질적인 격차를 증명합니다.
Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
이 논문은 정보이론적 관점에서 볼 때, 제한된 용량을 가진 언어 모델이 최적의 압축 전략을 따를 때 사실과 비사실의 확률 분포 차이를 최소화하는 과정에서 할루시네이션이 불가피하게 발생한다는 것을 증명합니다.
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
이 논문은 -DRESS 프레임워크가 CFI 그래프 쌍을 구별한다는 무조건적 증명과 WL-Deck 분리 가설 하에 모든 그래프에서 -WL 보다 강력하다는 조건부 증명을 통해, 기존 실증적 연구에 대한 이론적 근거를 제시합니다.
Transposition is Nearly Optimal for IID List Update
이 논문은 요청 확률 분포를 알지 못하는 상황에서 전위 (Transposition) 규칙이 고정된 분포에서 최적 비용에 1 을 더한 수준으로 기대 접근 비용을 보장하여, 50 년 전 Rivest 의 추측을 확인하고 확률 추정을 위한 순수 메모리리스 프로세스를 제시함을 증명합니다.
Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
이 논문은 최대 차수와 트리길이가 제한된 연결 그래프의 간선을 재구성하기 위해 결정론적 알고리즘을 사용하여 개의 최단 경로 거리 쿼리만으로 충분함을 증명하여 기존 알고리즘의 성능을 배 개선하고 하한과 일치시킵니다.
Density-Dependent Graph Orientation and Coloring in Scalable MPC
이 논문은 그래프의 부분그래프 밀도 () 에 따라 정점을 개의 색상으로 색칠하고 간선을 최대 외차수 로 방향성을 부여하는, 기존 의 한계를 깨는 회로 수행 가능한 확장 가능한 대규모 병렬 계산 (MPC) 알고리즘을 제시합니다.
Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
이 논문은 3 차원 공간에서 타겟의 크기와 모양이 탐지 효율에 결정적인 영향을 미치며, 특히 카우시 보행 (레비 지수 ) 이 다양한 크기와 모양의 타겟에 대해 스케일 불변적이며 최적의 탐지 성능을 보인다는 것을 수학적으로 증명합니다.
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
이 논문은 정수값 대칭 서모듈러 함수에서 특정 값 를 갖는 모든 컷을 다항식 크기의 표현으로 효율적으로 인코딩하는 방법을 제시하고, 이를 통해 고정된 에 대해 다항 시간 내에 특정 크기 조건을 만족하는 집합을 찾는 알고리즘을 제안합니다.
Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
이 논문은 보조 가정 없이 중앙 집중식 알고리즘을 사용하여 개의 아모보트 구조를 라운드 내에 표준 선형 구조로 재구성할 수 있음을 증명함으로써, 결합 이동 모델을 통한 아모보트의 선형 시간 미만 재구성 가능성을 입증했습니다.
Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
이 논문은 예측 오차율을 활용하여 기존 학습 증강 k-중앙값 클러스터링 알고리즘의 시간 복잡도와 차원 의존성을 획기적으로 개선하는 '샘플링 및 탐색 (Sample-and-Search)' 알고리즘을 제안하고, 이를 통해 계산 복잡도를 줄이면서도 더 낮은 클러스터링 비용을 달성함을 실험을 통해 입증합니다.