More on average case vs approximation complexity

DOI10.1007/S00037-011-0029-XMaRDI QIDQ430823zbMATH OpenOpenAlexFDO

Authors 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

hardness of approximationcryptographic primitives

Mathematics Subject Classification ID

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

Recommendations

• The hardness of approximate optima in lattices, codes, and systems of linear equations
• scientific article; zbMATH DE number 1559544
• On the hardness of approximating max-satisfy
• scientific article; zbMATH DE number 5081744
• On the hardness of approximating balanced homogenous 3-Lin

Cites work

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

Cited in

(17)

• On the complexity of random satisfiability problems with planted solutions
• Expander-Based Cryptography Meets Natural Proofs
• Deterministic Approximation Algorithms for the Nearest Codeword Problem
• Homomorphic evaluation requires depth
• An iterative correction method for practically LPN solving
• Expander-based cryptography meets natural proofs
• Immunizing backdoored PRGs
• Anonymous IBE, leakage resilience and circular security from new assumptions
• Special issue in memory of Misha Alekhnovich. Foreword
• Correlated pseudorandomness from expand-accumulate codes
• Constructing concrete hard instances of the maximum independent set problem
• Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
• On matrix rigidity and locally self-correctable codes
• Homomorphic encryption
• New Algorithms for Learning in Presence of Errors
• The Complexity of Public-Key Cryptography
• Public-Key Cryptographic Primitives Provably as Secure as Subset Sum

Describes a project that uses

Uses Software

• McEliece

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

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