k-parity 테스트의 비적응적 쿼리 복잡도

Source

• Evernote/IFTTT Feedly/The non-adaptive query complexity of testing k-parities.md

Summary

함수 f:{0,1}^n→{0,1}가 k-parity인지 또는 모든 k-parity에서 멀리 떨어져 있는지 비적응적(non-adaptively)으로 테스트하는 데 필요한 쿼리 수의 정확한 하한과 상한이 Θ(k log k)임을 증명합니다. 이 하한 증명은 Blais, Brody, Matulef의 통신 복잡성을 통한 테스트 하한 도출 방법과 k-disjointness의 일방향 통신 복잡성에 대한 Ω(k log k) 하한을 결합하여 이루어졌습니다.

Key Points

• 비적응적 k-parity 테스트의 쿼리 복잡도는 Θ(k log k)입니다.
• 하한 증명은 통신 복잡성 이론과 k-disjointness 문제의 하한을 활용합니다.
• 출처: Google Research 논문 (Buhrman, Garcia, Matsliah, Wolf 등)

Related

• Join 및 관련 큐잉 시스템 분석

• Reducing Lookups for Invariant Checking

• Approximation Algorithms for the Directed k-Tour and k-Stroll Problems

• k-원자성 검증 문제 (k-atomicity-verification problem) 연구

• Patent Query Formulation by Synthesizing Multiple Sources of Relevance Evidence

• 웹 검색의 내재적 다양성(Intrinsic Diversity)과 전체 세션 관련성

• Query-Adaptive Image Search With Hash Codes

• 관계 추출을 위한 원거리 감독에서 지식 베이스의 간극 메우기

• XML 데이터에 대한 키워드 쿼리의 컨텍스트 기반 다양화

• XXS: 압축된 XML 문서에서의 효율적인 XPath 평가

• 비디오 검색 결과의 의미론적 계층 구조화

• 규칙 기반 엔티티 해결 (Rule-Based Entity Resolution)

• 검색 엔진 쿼리 로그를 통한 사용자 작업(Task) 발견

• Efficient Index-Based Snippet Generation

• X-Class: XML 문서 구조 기반 연관 분류

• Deep Web 소스의 관련성 및 신뢰도 평가 (Inter-source Agreement 기반)

• Spaces, Trees, and Colors: 시퀀스 기반 문서 검색의 알고리즘 풍경

• vlHMM 기반 컨텍스트 인식 검색

• A term-based inverted index partitioning model for efficient distributed query processing

• Small-Document Approaches to Resource Selection 분석

• 웹 애플리케이션 모델 저장소의 텍스트 및 내용 기반 검색

• Enriching Documents with Examples: A Corpus Mining Approach

• 대용량 텍스트 컬렉션에서의 효율적 퍼지 검색

• 위키피디아 문서 품질 평가 알고리즘

• TSum: Fast, Principled Table Summarization

• Scalable Database-Driven Reverse Dictionary

• Effective and Robust Query-Based Stemming

• 정보 기하학을 통한 순수 고차 단어 연관성 마이닝

• Query Reformulation Modeling using Query Distributions

• Approximate Recall Confidence Intervals

• Source-Side Classifier Preordering for Machine Translation

• Beyond Text QA: Multimedia Answer Generation by Harvesting Web Information

• 온라인 건강 검색의 콘텐츠 편향성

• 피드백 세션을 통한 사용자 검색 목표 추론 알고리즘

• 통계적 기계 번역 표현을 활용한 교차 언어 정보 검색

• Semantic Queries by Example

• HEADY: 이벤트 패턴 클러스터링을 통한 뉴스 헤드라인 추상화

• StatParser: 통계적 파싱을 통한 쿼리 인터페이스 이해

• Efficient Estimation of Word Representations in Vector Space

• Supporting Flexible, Efficient, and User-Interpretable Retrieval of Similar Time Series

• 웹상 어린이의 검색 및 브라우징 행동 분석

• 수치 추상 도메인을 이용한 프로세스 발견 알고리즘

• 영어 책 코퍼스 기반 시계열 구문 N-그램 데이터셋

• Iustitia: 정보 이론적 접근을 통한 고속 플로우 성격 식별

• JSONiq: 쿼리 언어의 역사

• 온라인 리뷰 요약: Starlet 접근법

• 웹사이트 구조 개선을 통한 사용자 탐색 효율화