scientific article; zbMATH DE number 7650354

DOI10.4230/LIPICS.ITCS.2020.6MaRDI QIDQ5875699zbMATH OpenFDO

Authors Nir Bitansky, Idan Gerichter

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2020.6

zbMATH Keywords

cryptographyincremental computationlower boundsPLS

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Hardness of continuous local search: query complexity and cryptographic lower bounds
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• Cryptographic hardness of random local functions -- survey
• Cryptographic hardness of random local functions. Survey
• The locality of searchable symmetric encryption
• Local search and the local structure of NP-complete problems
• On the probe complexity of local computation algorithms
• Input locality and hardness amplification
• Input locality and hardness amplification

Cited in

(5)

• Input locality and hardness amplification
• Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
• Delegation with updatable unambiguous proofs and PPAD-hardness
• Non-interactive universal arguments
• One-way functions vs. TFNP: Simpler and improved

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875699)