The Journey from NP to TFNP Hardness
From MaRDI portal
Publication:4638115
DOI10.4230/LIPIcs.ITCS.2017.60zbMath1402.68067OpenAlexW2771768632MaRDI QIDQ4638115
Moni Naor, Pavel Hubáček, Eylon Yogev
Publication date: 3 May 2018
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8162/pdf/LIPIcs-ITCS-2017-60.pdf/
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
TFNP: An Update ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Statistically sender-private OT from LPN and derandomization ⋮ Incremental delay enumeration: space and time ⋮ Can PPAD hardness be based on standard cryptographic assumptions? ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Bit commitment using pseudorandomness
- On total functions, existence theorems and computational complexity
- Integer factoring and modular square roots
- BPP and the polynomial hierarchy
- How easy is local search?
- On the theory of average case complexity
- On the complexity of the parity argument and other inefficient proofs of existence
- Hardness vs randomness
- Structure vs. hardness through the obfuscation lens
- Does the polynomial hierarchy collapse if onto functions are invertible?
- Lower bounds for non-black-box zero knowledge
- On Constructing One-Way Permutations from Indistinguishability Obfuscation
- Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits
- Universal Constructions and Robust Combiners for Indistinguishability Obfuscation and Witness Encryption
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- The Dual BKR Inequality and Rudich's Conjecture
- Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
- Settling the complexity of computing two-player Nash equilibria
- Relativized cryptography
- The complexity of promise problems with applications to public-key cryptography
- The Complexity of Decision Versus Search
- Designing programs that check their work
- Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
- Search Problems in the Decision Tree Model
- The Complexity of Computing a Nash Equilibrium
- How to use indistinguishability obfuscation
- A Note on Perfect Correctness by Derandomization
- Advances in Cryptology - EUROCRYPT 2004
- Computational Complexity
- Pseudorandomness when the odds are against you
- Derandomization in Cryptography
- Zaps and Their Applications
- One-Way Functions and (Im)perfect Obfuscation
- Computational Complexity
- Can PPAD hardness be based on standard cryptographic assumptions?
