순서가 있습니다. 포털 넷(연구방·지식센터·커뮤니티·아카데미)을 먼저 담고,
SSRA 는 맨 나중에 담아 주세요. SSRA 를 먼저 담으면 나머지가 그 안에 포함된 것으로
잡혀 따로 담기지 않습니다. 아이콘도 담을 차례대로 놓았습니다 — 왼쪽부터 차례로 누르시면 됩니다.
Interactive particle systems on hypergraphs, drift analysis and the WalkSAT algorithm
Gabriel Istrate, Cosmin Bonchiş, Mircea Marin · Journal of Complexity · 2026년 · 조회 14
왜 이 논문인가 — 선정 기준
NEW PAPER · 최근 발표된 참신한 논문 — 게재일 기준 최신 + 정상 등재 저널
2026-11 발표 · 게재 2일차 · Journal of Complexity
NEW PAPER 슬롯은 최신성과 독창성을 강조하는데, 2026‑11‑04 발표된 이 논문은 하이퍼그래프와 입자 시스템을 결합한 새로운 분석 틀을 제시한다.
논문 요약
k‑XOR SAT 만족 인스턴스에 대해 유명 로컬 서치인 WalkSAT의 기대 실행 시간을 분석한다. 이를 위해 하이퍼그래프에서의 새로운 폭발적 입자 시스템(공동·소멸 랜덤워크, 투표 모델)을 정의하고, 드리프트 분석 기법으로 문제를 변환한다. 결과적으로 이중 하이퍼그래프의 구조적 파라미터인 ‘odd Cheeger drift’가 WalkSAT 실행 시간에 결정적인 영향을 미침을 밝혀냈다.
후속 연구설계에 활용하기
odd Cheeger drift를 조절한 하이퍼그래프 인스턴스를 생성해 WalkSAT 성능을 실험함으로써 알고리즘 효율성에 대한 변인 설계에 활용할 수 있다.
핵심어
하이퍼그래프WalkSAT드리프트 분석입자 시스템
실존 확인
이 논문은 OpenAlex에서 후보로 수집한 뒤, Crossref에 등록된 DOI와 제목 일치를 확인해 노출합니다.
SSRA가 문헌연구에서 인용 논문의 실재 여부를 검증하는 원칙과 같습니다.