A note on approximating the average degree of bounded arboricity graphs
본 논문은 bounded arboricity 그래프의 평균 차수를 근사하는 Eden, Ron, Seshadhri 의 기존 알고리즘을 파라미터 탐색으로 인한 로그 인자 손실 없이 명확하게 제시하고, 쿼리 복잡도로 -근사치를 제공하는 알고리즘을 상세히 설명합니다.
💻 Category
cs.CC
45 편의 논문
The Power of Shallow-depth Toffoli and Qudit Quantum Circuits
이 논문은 양자 조언을 가진 상수 깊이 회로나 중간 측정 및 고전적 팬아웃이 포함된 Toffoli 게이트 기반 회로가 고전적 상수 깊이 회로보다 우월함을 증명하고, 무한 게이트 집합을 가진 회로가 임계값 게이트를 구현할 수 있음을 보이며, 고차원 힐베르트 공간의 양자 회로가 표준 큐비트 구현보다 추가적인 이점을 제공하지 않음을 규명합니다.
Computational Complexity in Property Testing
이 논문은 속성 테스트에서 쿼리 복잡도와 시간 복잡도 간의 관계를 체계적으로 연구하여 시간 - 쿼리 위계 정리를 제시하고, -SUM 가설과 통계적 쿼리 모델을 기반으로 반공간 (halfspace) 문제에서 두 복잡도 간의 본질적인 격차를 증명합니다.
Deciding winning strategies in Yu-Gi-Oh! TCG is hard
이 논문은 유-기-오! TCG 에서 주어진 게임 상태에서 특정 전략이 승리하는지 여부를 결정하는 문제가 계산 불가능하며, 실제로 -완전 (complete) 임을 증명하고 이를 위해 현재 금지/제한 목록에 따라 합법적으로 구성할 수 있는 두 가지 덱을 제시합니다.
The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory
이 논문은 생성과 인식이 확장적으로 동등하지만 계산 복잡성, 모호성, 방향성, 정보 가용성, 문법 추론, 시간성 등 여섯 가지 차원에서 근본적인 비대칭성을 보이며, 특히 '생성은 쉽고 구문 분석은 어렵다'는 통념이 생성이 제약받지 않을 때만 성립함을 지적하고 이를 언어 모델의 맥락에서 재해석합니다.
Fast polynomial computations with space constraints
이 논문은 다항식 연산의 시간-공간 복잡도 최적화 및 희소 다항식의 효율적 인터폴레이션과 같은 계산적 난제 해결을 위한 새로운 알고리즘들을 제시합니다.
Classical simulability of quantum circuits followed by sparse classical post-processing
이 논문은 희소 고전적 사후 처리 (SCP) 를 거친 양자 회로의 고전적 시뮬레이션 가능성을 분석하여, 특정 조건 하에서 IQP 나 클리포드 매직 회로와 같은 회로도 SCP 와 결합 시 시뮬레이션이 가능함을 증명하고, 상수 깊이 회로의 경우 교환 가능한 양자 회로를 활용한 확률적 알고리즘으로 시뮬레이션할 수 있음을 제시합니다.
Intrinsic Information Flow in Structureless NP Search
이 논문은 정보 이론적 관점에서 NP 증후 발견 문제를 재해석하여, 구조 없는 균등 사전 분포 하에서 등식 탐지만으로는 다항 시간 내에 필요한 정보를 획득할 수 없어 지수적 탐색 복잡성이 필연적으로 발생함을 보여줍니다.
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
이 논문은 모든 고정된 그래프 H 에 대해 P5-자유 그래프에서 최대 부분 리스트 H-채색 문제가 다항 시간에 해결 가능함을 증명하여, Agrawal 등 (SODA 2024) 의 열린 문제를 해결하고 Chudnovsky 등 (SIDMA 2021) 의 기존 알고리즘을 다항 시간 알고리즘으로 개선했습니다.
On complexity of restricted fragments of Decision DNNF
이 논문은 결정형 DNNF 의 제한된 부분인 -OBDD 모델에 대한 하한 증명 방법론을 제시하고 기존 결과를 재확인하며 FBDD 및 OBDD 와의 크기 분리, Apply 연산의 복잡도 분석, 그리고 incidence treewidth 가 제한된 CNF 에 대해 강력한 성능을 보이는 새로운 모델인 Structured -FBDD 를 도입합니다.
No exponential quantum speedup for anymore
이 논문은 Chen, Liu, Zhandry 가 제안한 양자 알고리즘이 이득을 보였던 것으로 알려진 및 관련 문제에 대해 효율적인 고전 알고리즘을 제시함으로써 더 이상 지수적 양자 가속이 존재하지 않음을 증명합니다.
A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing
이 논문은 지연 로컬-비율 (deferred local-ratio) 기법과 등반 (climbing) 전략을 도입하여 트리 보강 문제 (TAP) 에 대해 $4/3O(m\sqrt{n})$ 시간 복잡도로 해결하는 새로운 알고리즘을 제안합니다.
Classification of Local Optimization Problems in Directed Cycles
이 논문은 방향성 사이클에서의 국소 최적화 문제들에 대해 결정론적 및 확률적 LOCAL 모델에서의 계산 복잡성을 완전히 분류하고, 주어진 문제에 대한 복잡도 클래스를 자동으로 판별하며 점근적으로 최적의 분산 알고리즘을 효율적으로 생성하는 메타 알고리즘을 제시합니다.
Why Are Linear RNNs More Parallelizable?
이 논문은 선형 RNN(LRNN) 이 비선형 RNN 보다 병렬화가 용이한 이유를 복잡도 클래스 (Log-depth 회로 대 P-완전 문제) 와 오토마타 이론을 통해 이론적으로 규명하고, 다양한 LRNN 변형 간의 정밀한 표현력 차이를 분석하여 표현력과 병렬성 사이의 균형을 잡는 LLM 아키텍처 설계의 기초를 제공합니다.
Generalizing Fair Top- Selection: An Integrative Approach
이 논문은 다수의 보호 집단을 고려한 공정한 상위-k 선택 문제를 다루며, 기존 연구의 한계를 극복하기 위해 계산 복잡성 분석을 통해 효율성 회복 가능성을 규명하고, 편차 최소화를 넘어 더 안정적인 유틸리티 손실 지표를 도입하여 실세계 데이터에서 우수한 성능을 보이는 통합적 알고리즘을 제안합니다.
Quantum Algorithms for Network Signal Coordination
이 논문은 NP-완전 문제인 네트워크 신호 조정 (NSC) 문제를 해결하기 위해 그로버 알고리즘을 적용하고, 시스템 지연 임계값을 만족하는 해의 비율 (α) 에 무관하게 2 차 속도 향상을 제공하는 강건한 NSC 문제 및 다항식 정밀도 확장 알고리즘을 개발하여 시뮬레이션과 실제 양자 컴퓨터를 통해 검증했습니다.
Attacking the Polynomials in the Maze of Finite Fields problem
이 논문은 2025 년 GMV 가 주최한 유한체 다항식 시스템 해법 경진대회를 대상으로, 구조적 희소성과 결과식을 활용한 ResultantSolver 알고리즘을 제안하여 기존 방법론보다 훨씬 효율적으로 방정식 시스템을 해결하는 방법을 제시합니다.
Recurrent Graph Neural Networks and Arithmetic Circuits
이 논문은 메모리 게이트를 사용하는 재귀적 산술 회로와 재귀적 그래프 신경망 (GNN) 간의 계산 능력을 매핑하여, 실수 위에서 작동하는 두 모델의 표현력이 정확히 일치함을 증명합니다.
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
이 논문은 유한 정규 CW 복합체에서 최적 모스 매칭 문제를 $2^{O(k \log k)} n2^{o(k \log k)} n^{O(1)}k$ 에 대한 정확한 복잡도 하한을 확립했습니다.
Aaronson-Ambainis Conjecture Is True For Random Restrictions
이 논문은 Aaronson-Ambainis 추측이 분산이 충분히 큰 다항식의 경우 무작위 제한 (random restriction) 에 대해 성립함을 증명하여, 양자 쿼리 알고리즘의 수용 확률이 고전 결정 트리로 근사될 수 있음을 보여줍니다.