Average-case fine-grained hardness

DOI10.1145/3055399.3055466zbMath1369.68214OpenAlexW2625217561MaRDI QIDQ4977996

Prashant Nalini Vasudevan, Marshall Ball, Alon Rosen, Manuel Sabin

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3055399.3055466

zbMATH Keywords

cryptographyaverage-case complexityfine-grained complexityworst-case to average-case reductionproofs of workheuristic falsifiability

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Fine-grained secure computation ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ Proofs of Work from worst-case assumptions ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Unnamed Item ⋮ Fine-grained non-interactive key-exchange: constructions and lower bounds ⋮ Unnamed Item ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Foundations of Homomorphic Secret Sharing ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ New techniques for zero-knowledge: leveraging inefficient provers to reduce assumptions, interaction, and trust

This page was built for publication: Average-case fine-grained hardness