Hardness of the Binary Covering Radius Problem in Large Norms
이 논문은 보다 큰 노름에서 결정형 격자 덮기 반지름 문제 (GapCRP) 가 명시적인 근사 인자 에 대해 NP-난해함을 증명하여, 해당 문제에 대한 최초의 NP-난해성 결과를 제시합니다.
💻 Category
cs.CC
45 편의 논문
d-QBF with Few Existential Variables Revisited
이 논문은 존재 변수 개수 에 대한 QBF 문제의 이중 지수적 시간 복잡도 하한이 ETH 가정 하에 최적임을 증명하고, 두 개의 양화자 블록으로 제한된 경우의 효율적인 알고리즘과 하한을 제시합니다.
Reinforced Generation of Combinatorial Structures: Ramsey Numbers
이 논문은 LLM 기반 코드 변이 에이전트인 'AlphaEvolve'를 활용하여 5 가지 고전적 램지 수의 하한을 개선하고, 기존에 알려진 모든 정확한 램지 수 하한을 재발견하며 다양한 경우에 최선의 하한을 달성했다는 점을 제시합니다.
A Simple Constructive Bound on Circuit Size Change Under Truth Table Perturbation
이 논문은 최소 회로 크기 문제의 암시적 관찰을 명시적으로 정립하여 진리표의 한 점 변경 시 최적 회로 크기가 이내로만 변함을 증명하고, 이를 일반화하며 에서의 AIG 기반 실험을 통해 이 상한이 최적임을 확인했습니다.
The framework to unify all complexity dichotomy theorems for Boolean tensor networks
이 논문은 부호화된 텐서 네트워크에 대한 모든 복잡도 이분화 정리를 통합하는 새로운 프레임워크를 제안하여, 해결되지 않은 문제들을 2x2 복소수 행렬로 구성된 유한 군의 범주에 따라 9 가지 경우로 분류하고, 군의 전치 닫힘 성질에 따른 행렬 형식의 단순화, 사원수 부분군 관련 장벽, 그리고 순환군 사례에 대한 정리를 다룹니다.
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
이 논문은 저차원 유클리드 공간에서 -median 및 -means 클러스터링 문제에 대해 기존 결과를 개선한 거의 최적의 상한 알고리즘을 제시하고, 갭 지수 시간 가설 하에서 거의 일치하는 하한을 증명합니다.
Has quantum advantage been achieved?
이 논문은 2019 년 이후 여러 실험을 통해 주장되어 왔으나 합의가 없었던 양자 우월성의 달성 여부를 논의하고, 실제로 달성되었음을 주장하며 향후 이론과 실험을 위한 다음 단계를 제시합니다.
Tetris is Hard with Just One Piece Type
이 논문은 표준 회전 시스템 (SRS) 하에서 O 테트로미노를 제외한 모든 단일 테트로미노 유형으로 구성된 테트리스 게임의 클리어 및 생존 문제가 NP-난해함을 증명하여 23 년 전의 추측을 반증하고, 반면 도미노나 특정 조건 하의 $1 \times k$ 조각에 대해서는 다항 시간 알고리즘을 제시합니다.
Quantum Automating -Frege Is LWE-Hard
이 논문은 학습 오류 (LWE) 가 안전하다는 가정 하에 양자 알고리즘이 -Frege 증명 시스템을 효율적으로 자동화할 수 없음을 증명하여 양자 계산과 명제 증명 탐색 간의 첫 번째 상호작용을 제시합니다.
Privately Estimating Black-Box Statistics
이 논문은 민감도 상한이 알려지지 않은 임의의 블랙박스 함수에 대해 통계적 효율성과 오라클 효율성 사이의 균형을 이루며 근사적으로 최적의 차분 프라이버시 추정 기법을 제안하고 그 최적성을 증명합니다.
Polynomial-time isomorphism test for -generated extensions of abelian groups
이 논문은 유한 환의 단위군을 다항 시간에 계산하는 새로운 알고리즘을 제시하여, -생성 군으로 확장된 아벨 군 (특히 아벨-순환 및 아벨-단순 군 확장) 의 동형 판별 문제를 다항 시간에 해결하는 방법을 증명합니다.
Three Fixed-Dimension Satisfiability Semantics for Quantum Logic: Implications and an Explicit Separator
이 논문은 유한 차원 힐베르트 공간에서 정의된 세 가지 양자 논리 만족도 개념 (표준 힐베르트 격자, 전역 가환 투영자, 국소 부분-부울) 을 비교하여, 특정 논리식이 표준 의미론에서는 만족 가능하지만 나머지 두 의미론에서는 만족 불가능함을 보여주는 명시적 분리자 (SEP-1) 를 제시하고 세 개념 간의 포함 관계를 규명합니다.
A base change framework for tensor functions
이 논문은 임의의 체에서 정의된 텐서 함수에 대한 결과를 확장하는 기저 변환 프레임워크를 제시하여, 3-텐서의 슬라이스 랭크가 기하학적 랭크에 의해 선형적으로 제한되고 점근적 슬라이스 랭크가 존재함을 증명합니다.
Complexity Lower Bounds of Small Matrix Multiplication over Finite Fields via Backtracking and Substitution
이 논문은 대입법과 체계적인 백트래킹 기법을 결합하여 유한체에서 행렬 곱셈의 쌍선형 복잡도 하한을 증명하는 새로운 방법을 제시하고, 이를 통해 위의 $3 \times 3$ 행렬 곱셈 복잡도 하한을 기존 19 에서 20 으로 개선하는 자동화된 증명을 제시합니다.
On Factorization of Sparse Polynomials of Bounded Individual Degree
본 논문은 개별 차수가 제한된 희소 다항식의 인수 분해에 대한 구조적 특성을 규명하고, 희소 다항식 및 그 곱의 인수들을 복원하는 다양한 결정론적 다항 시간 알고리즘을 제시하여 기존 연구의 효율성을 대폭 개선하고 임의의 체에서도 적용 가능한 새로운 수학적 도구를 도입했습니다.
The Theory and Practice of Computing the Bus-Factor
이 논문은 프로젝트의 인적 리스크를 정량화하는 '버스 지수'를 계산하기 위해 사람과 작업을 이분 그래프로 모델링한 통합 프레임워크를 제안하고, 기존 방법의 한계를 극복하며 NP-난해 문제를 해결하는 효율적인 근사 알고리즘과 더 안정적이고 정보적인 새로운 측정 지표를 개발했습니다.
Quantum information advantage based on Bell inequalities
이 논문은 KGD+25 의 실험적 제안과 구별되는 병렬 반복 CHSH 게임에 기반한 새로운 양자 정보 우위 프로토콜을 제시하며, 이는 효율적인 검증자와 잡음에 강인한 양자 증명자를 갖추고 있어 기존 방식보다 훨씬 효율적임을 보여줍니다.
The Unit Gap: How Sharing Works in Boolean Circuits
이 논문은 AND-NOT 기저에서 부울 회로와 부울 식의 최소 크기 차이가 항상 0 또는 1 임을 증명하고, 이 차이가 1 인 경우 오직 하나의 팬아웃 2 게이트에 의한 공유 구조에서만 발생하며, 특정 변수 수 조건 하에서 공유가 불필요하거나 임계값을 갖는다는 일련의 정리들을 제시합니다.
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
이 논문은 행과 열의 순서 제약 조건을 가진 격자 퍼즐의 해 존재 조건을 분석하고, 해의 개수를 훅 길이 공식으로 계산하며, 해가 없는 경우의 최소 수정 알고리즘을 제시하고 일반화된 버전의 NP-완전성을 증명합니다.
Intrinsic Sequentiality in P: Causal Limits of Parallel Computation
이 논문은 인과적 실행이 필수적인 다항 시간 결정 문제를 분석하여, 정보 전달의 인과적 제약으로 인해 병렬화 속도가 불가능하며 회로로 구현할 수 없는 문제를 제시함으로써 논리적 병렬성과 인과적 실행 가능성 사이의 간극을 규명합니다.