More on average case vs approximation complexity
DOI10.1007/S00037-011-0029-XzbMATH Open1242.68109OpenAlexW3162278033MaRDI QIDQ430823FDOQ430823
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
Recommendations
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)
Cites Work
- Probabilistic encryption
- Relations between average case complexity and approximation complexity
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some optimal inapproximability results
- Foundations of Cryptography
- A remark on matrix rigidity
- A note on matrix rigidity
- Improved lower bounds on the rigidity of Hadamard matrices
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- Natural proofs
- Pseudorandom Generators in Propositional Proof Complexity
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
- Dual vectors and lower bounds for the nearest lattice point problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes
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
- An iterative correction method for practically LPN solving
- Homomorphic evaluation requires depth
- Immunizing backdoored PRGs
- Expander-based cryptography meets natural proofs
- Anonymous IBE, leakage resilience and circular security from new assumptions
- Correlated pseudorandomness from expand-accumulate codes
- Special issue in memory of Misha Alekhnovich. Foreword
- 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
Uses Software
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)
