Pseudo-deterministic PRG-XOR Isolation: A Rigorous Framework for Unique-SAT

OSF Preprints (OSF Preprints) 2026 Preprint Open access

Read full text
Authors: Uthit Lakkaew
DOI: 10.17605/osf.io/7ktvm
Cited by: 0

Abstract

A pseudo-deterministic framework for isolating satisfying assignments of Boolean formulas using sparse XOR constraints generated by a pseudo-random generator (PRG). Combines k-sparse PRG-XOR matrices with a deterministic Pseudo-deterministic Stability Test (PST) to ensure high-probability full-rank matrices and negligible constraint removal, providing reproducible XOR-based isolation without unconditional derandomization.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Constraint Satisfaction and Optimization Advanced Graph Theory Research

Publication details

Journal / source
OSF Preprints (OSF Preprints)
Publication date
1 January 2026
Document type
Preprint