More on average case vs approximation complexity
From MaRDI portal
Complexity of proofs (03F20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Approximation algorithms (68W25) Cryptography (94A60)
Recommendations
Cites work
- A note on matrix rigidity
- A remark on matrix rigidity
- Dual vectors and lower bounds for the nearest lattice point problem
- Foundations of Cryptography
- 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?)
- 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
(21)- Anonymous IBE, leakage resilience and circular security from new assumptions
- Expander-based cryptography meets natural proofs
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
- Homomorphic evaluation requires depth
- New Algorithms for Learning in Presence of Errors
- Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
- Deterministic Approximation Algorithms for the Nearest Codeword Problem
- Special issue in memory of Misha Alekhnovich. Foreword
- On the complexity of random satisfiability problems with planted solutions
- The Complexity of Public-Key Cryptography
- Homomorphic encryption
- Expander-Based Cryptography Meets Natural Proofs
- Constructing concrete hard instances of the maximum independent set problem
- Correlated pseudorandomness from expand-accumulate codes
- On matrix rigidity and locally self-correctable codes
- An iterative correction method for practically LPN solving
- Immunizing backdoored PRGs
- Indistinguishability obfuscation from bilinear maps and LPN variants
- A novel PQ-KEM based on coding theory
- The strongish planted clique hypothesis and its consequences
- Public-key encryption from the MinRank problem
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)
