More on average case vs approximation complexity

DOI10.1007/s00037-011-0029-xzbMath1242.68109OpenAlexW3162278033MaRDI QIDQ430823

Michael Alekhnovich

Publication date: 26 June 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-011-0029-x

zbMATH Keywords

cryptographic primitiveshardness of approximation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity of proofs (03F20)

Related Items (14)

Expander-based cryptography meets natural proofs ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Anonymous IBE, leakage resilience and circular security from new assumptions ⋮ Correlated pseudorandomness from expand-accumulate codes ⋮ Special issue in memory of Misha Alekhnovich. Foreword ⋮ On matrix rigidity and locally self-correctable codes ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ New Algorithms for Learning in Presence of Errors ⋮ Homomorphic Evaluation Requires Depth ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ Public-Key Cryptographic Primitives Provably as Secure as Subset Sum ⋮ The Complexity of Public-Key Cryptography ⋮ Homomorphic Encryption

Uses Software

• McEliece

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A remark on matrix rigidity
• A note on matrix rigidity
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Probabilistic encryption
• Dual vectors and lower bounds for the nearest lattice point problem
• Improved lower bounds on the rigidity of Hadamard matrices
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Proof verification and the hardness of approximation problems
• Relations between average case complexity and approximation complexity
• Probabilistic checking of proofs
• Pseudorandom Generators in Propositional Proof Complexity
• Foundations of Cryptography
• Some optimal inapproximability results
• Natural proofs
• On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes

This page was built for publication: More on average case vs approximation complexity