Variants of Pseudo-deterministic Algorithms and Duality in TFNP
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
We introduce a new notion of ``faux-deterministic'' algorithms for search problems in query complexity. Roughly, for a search problem $\\cS$, a faux-deterministic algorithm is a probability distribution $\\mathcal{A}$ over deterministic algorithms $A\\in \\mathcal{A}$ such that no computationally bounded adversary making black-box queries to a sampled algorithm $A\\sim \\mathcal{A}$ can find an input $x$ on which $A$ fails to solve $\\cS$ ($(x, A(x))\\notin \\cS$). Faux-deterministic algorithms are a relaxation of \\emph{pseudo-deterministic} algorithms, which are randomized algorithms with the guarantee that for any given input $x$, the algorithm outputs a unique output $y_x$ with high probability. Pseudo-deterministic algorithms are statistically indistinguishable from deterministic algorithms, while faux-deterministic algorithms relax this statistical indistinguishability to computational indistinguishability. \nWe prove that in the query model, every verifiable search problem that has a randomized algorithm also has a faux-deterministic algorithm. By considering the pseudo-deterministic lower bound of Goldwasser et al. \\cite{goldwasser_et_al:LIPIcs.CCC.2021.36}, we immediately prove an exponential gap between pseudo-deterministic and faux-deterministic complexities in query complexity. We additionally show that our faux-deterministic algorithm is also secure against quantum adversaries that can make black-box queries in superposition. \nWe highlight two reasons to study faux-deterministic algorithms. First, for practical purposes, one can use a faux-deterministic algorithm instead of pseudo-deterministic algorithms in most cases where the latter is required. Second, since efficient faux-deterministic algorithms exist even when pseudo-deterministic ones do not, their existence demonstrates a barrier to proving pseudo-deterministic lower bounds: Lower bounds on pseudo-determinism must distinguish pseudo-determinism from faux-determinism. \nFinally, changing our perspective to the adversaries' viewpoint, we introduce a notion of ``dual problem'' $\\cS^{*}$ for search problems $\\cS$. In the dual problem $\\cS^*$, the input is an algorithm $A$ purporting to solve $\\cS$, and our goal is to find an adverse input $x$ on which $A$ fails to solve $\\cS$. We discuss several properties in the query and Turing machine model that show the new problem $\\cS^*$ is analogous to a dual for $\\cS$.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.000 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.001 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it