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"”.

  1. 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 …

    waterloo Repository record for On the Black-Box Impossibility of Hardness in TFNP from One-Way Functions (opens in a new tab)

  2. Quantum Pseudorandom Primitives Beyond Pseudorandom States

    … zero-knowledge arguments, showing limitations of black-box reductions under classical-query quantum adversaries.

    portland-state Repository record for Quantum Pseudorandom Primitives Beyond Pseudorandom States (opens in a new tab)

  3. 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 …

    waterloo Repository record for Mechanism Design For Covering Problems (opens in a new tab)