Variants of Pseudo-deterministic Algorithms and Duality in TFNP
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.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.011 | 0.048 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.002 | 0.004 |
| Bibliometrics | 0.002 | 0.003 |
| Science and technology studies | 0.002 | 0.007 |
| Scholarly communication | 0.008 | 0.017 |
| Open science | 0.006 | 0.009 |
| Research integrity | 0.004 | 0.012 |
| Insufficient payload (model declined to judge) | 0.008 | 0.002 |
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 itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".