Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 3 of 3 for “"Black-Box Reductions"”.
-
On the Black-Box Impossibility of Hardness in TFNP from One-Way Functions
… providing evidence for this difficulty through blackbox impossibility. Existing barriers rule out either restricted constructions of TFNP problems or restricted classes of reductions. In particular, [RSS16] rules out constructions whose instances have a bounded number of solutions, while …
-
Quantum Pseudorandom Primitives Beyond Pseudorandom States
… zero-knowledge arguments, showing limitations of black-box reductions under classical-query quantum adversaries.
-
Mechanism Design For Covering Problems
… cover. For multi-dimensional UFL, we give a black-box method to transform any Lagrangian-multiplier-preserving ρ-approximation algorithm for UFL into a truthful-in-expectation, ρ-approximation mechanism. This yields the first result for multi-dimensional UFL, namely a truthful-in-expectation …