Theorem 5.8 — exact queue with explicit privacy dependence
OpenDOPriorityQueue.Construction.Supplement.theorem_5_8Fix and a polynomial priority exponent . For every admissible , and , use the public inputs and . Set , and
Admissibility means . There is one finite online RAM program for these fixed exponents which starts empty, returns exact stable queue answers on every random execution, terminates on every tape, and is -differentially oblivious under replacement of one complete operation. Priorities lie in ; payloads are opaque. For every fixed history of actual length ,
The probe and space bounds hold on every execution, including temporary workspace. Work charges all client instructions, probes, initialization and public-input delivery. A zero-call history does no setup. Word length is a fixed positive affine multiple of , hence .
The positive constants, word-size factors and resource threshold depend only on the two fixed exponents and fixed primitives, never on , history or coins. Resource estimates hold beyond that uniform threshold; exactness and privacy cover every admissible horizon. This companion theorem supplies varying privacy dependence beyond the retained fixed-privacy headline. It does not assume that dependence as an implementation field.
Differences from the source:
- encoding: a polynomial bound on integer priorities → the integers 1 through floor(T^c), with arbitrary fixed c>0; reason: every polynomially bounded universe is contained in such a universe after choosing a fixed larger exponent
- encoding: uniform asymptotic work, probes and space; w=Theta(log T) → positive constants, positive affine word-length factors and one resource threshold chosen before T, epsilon and delta; reason: records uniform asymptotics; exactness and privacy still hold at every admissible T>2
- encoding: public integer privacy inputs and charged word-RAM initialization → existing finite RAM with inputs in registers 5 and 6, a two-word first-invocation delivery charge, and execution-derived costs and footprints; reason: a concrete calling convention; fixed instruction factors are absorbed uniformly
- encoding: internal randomness and measurable events of finite call traces → normalized sums of terminal random-word cylinder masses and all sets of discrete call-grouped traces; reason: equivalent discrete probability semantics with no omitted mass or integrability default
- reading: a queue for each public T and varying privacy parameters → one finite program and fixed word factors serve all admissible T, epsilon and delta using only public integers; reason: Appendix C computes parameters at runtime and states privacy-independent constants
import Definitions.Def_DOPriorityQueue_Construction_Supplement_Parameterized set_option autoImplicit false
namespace DOPriorityQueue.Construction.Supplement
/-- Guo--Hong--Li, STOC 2027 submission #538, p. 27, Theorem 5.8;
implementation and uniformity conventions from Appendix C, pp. 37--38. -/
theorem theorem_5_8 (cpriv c : ℝ) (hpriv : 1 ≤ cpriv) (hc : 0 < c) :
ParameterizedTarget cpriv c := by sorry
end DOPriorityQueue.Construction.Supplement