Aaronson-Ambainis Conjecture Is True For Random Restrictions
이 논문은 Aaronson-Ambainis 추측이 분산이 충분히 큰 다항식의 경우 무작위 제한 (random restriction) 에 대해 성립함을 증명하여, 양자 쿼리 알고리즘의 수용 확률이 고전 결정 트리로 근사될 수 있음을 보여줍니다.
💻 Category
cs.CC
46 편의 논문
Reversible Computation with Stacks and "Reversible Management of Failures"
이 논문은 스택 연산을 부분 전단사 함수가 아닌 전 전단사 함수로 해석하여 계산 복잡성 연구에 필수적인 총전단사성 (total bijectivity) 을 보장하는 새로운 역계산 언어 SCORE 를 제안하고, 증명 보조기구를 통해 그 정확성을 검증합니다.
When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
이 논문은 선형성 조건을 제거하고 작은 사운드니스 오류를 가진 임의의 -쿼리 완화 국소 복호 가능 코드 (RLDC) 가 동등한 매개변수를 갖는 표준 국소 복호 가능 코드 (LDC) 로 변환될 수 있음을 증명하여, RLDC 와 LDC 간의 관계를 규명하고 RLDC 및 PCPP 에 대한 새로운 하한을 제시합니다.
Advances in List Decoding of Polynomial Codes
이 책은 최근 리드 - 솔로몬 코드 및 관련 다항식 기반 코드들의 리스트 복호화 분야에서 정보이론적 용량까지 효율적으로 복호화하고 최적의 리스트 크기를 달성하며 거의 선형 시간 또는 부분 선형 시간 알고리즘을 통해 이루어진 획기적인 발전들을 종합적으로 개괄합니다.
Learning Read-Once Determinants and the Principal Minor Assignment Problem
이 논문은 주어진 다항식이 형태인지 확인하고 해당 행렬을 복원하는 '읽기-한번-행렬식 (ROD)' 학습 문제를, 행렬의 주소행렬식 할당 문제 (PMAP) 와의 동치 관계를 통해 다항식 시간 무작위 알고리즘으로 해결했음을 보여줍니다.
Quantum Algorithms for Approximate Graph Isomorphism Testing
이 논문은 MNRS 양자 보행 탐색을 기반으로 한 근사 그래프 동형성 테스트 양자 알고리즘을 제시하여 쿼리 복잡도로 고전적 하한선 대비 다항식 양자 가속을 입증합니다.