Average-case fine-grained hardness

DOI10.1145/3055399.3055466MaRDI QIDQ4977996zbMATH OpenOpenAlexFDO

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

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

average-case complexitycryptographyfine-grained complexityheuristic falsifiabilityproofs of workworst-case to average-case reduction

Mathematics Subject Classification ID

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

Recommendations

• On building fine-grained one-way functions from strong average-case hardness
• Proofs of Work from worst-case assumptions
• On basing one-way functions on NP-hardness
• scientific article; zbMATH DE number 5081744
• scientific article; zbMATH DE number 512870

Cited in

(23)

• Fine-grained secure computation
• Proofs of Work from worst-case assumptions
• New techniques for zero-knowledge: leveraging inefficient provers to reduce assumptions, interaction, and trust
• On building fine-grained one-way functions from strong average-case hardness
• Public-key cryptography in the fine-grained setting
• Simple doubly-efficient interactive proof systems for locally-characterizable sets
• Foundations of homomorphic secret sharing
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• Worst-Case to Average-Case Reductions for Subclasses of P
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Fine-grained non-interactive key-exchange: constructions and lower bounds
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• Hardness self-amplification: simplified, optimized, and unified
• Towards permissionless consensus in the standard model via fine-grained complexity
• Fine-grained non-interactive key exchange, revisited
• \(k\)-SUM in the sparse regime: complexity and applications
• On sequential functions and fine-grained cryptography
• On building fine-grained one-way functions from strong average-case hardness
• Fine-grained complexity in a world without cryptography
• The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
• The planted orthogonal vectors problem
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
• Worst-case and average-case hardness of hypercycle and database problems

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

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