Bibliographic record
Abstract
We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as well as an advice string, and outputs a Boolean function on a smaller number of bits which has greater hardness when measured in terms of input length. A hardness extractor takes in a Boolean function as input, as well as an advice string, and outputs a Boolean function defined on a smaller number of bits which has close to maximum hardness. We prove several positive and negative results about these objects. First, we observe that hardness-based pseudo-random generators can be used to extract deterministic hardness from non-deterministic hardness. We derive several consequences of this observation. Among other results, we show that if E/O(n) has exponential non-deterministic hardness, then E/O{n) has deterministic hardness 2/sup n//n, which is close to the maximum possible. We demonstrate a rare downward closure result: E with sub-exponential advice is contained in non-uniform space 2/sup /spl delta/n/ for all /spl delta/ > 0 if and only if there is k > 0 such that P with quadratic advice can be approximated in non-uniform space n/sup k/. Next, we consider limitations on natural models of hardness condensing and extraction. We show lower bounds on the advice length required for hardness condensing in a very general model of relativizing condensers. We show that non-trivial black-box extraction of deterministic hardness from deterministic hardness is essentially impossible. Finally, we prove positive results on hardness condensing in certain special cases. We show how to condense hardness from a biased function without advice using a hashing technique. We also give a hardness condenser without advice from average-case hardness to worst-case hardness. Our technique uses a connection between hardness condensing and explicit constructions of covering codes.
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.010 | 0.057 |
| Meta-epidemiology (narrow) | 0.002 | 0.002 |
| Meta-epidemiology (broad) | 0.002 | 0.004 |
| Bibliometrics | 0.002 | 0.002 |
| Science and technology studies | 0.003 | 0.013 |
| Scholarly communication | 0.007 | 0.025 |
| Open science | 0.005 | 0.012 |
| Research integrity | 0.004 | 0.015 |
| Insufficient payload (model declined to judge) | 0.026 | 0.004 |
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".