More on Average Case vs Approximation Complexity

By Michael Alekhnovich. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., 2003

345 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/c43ed43caf10d5bb8457e77553a4cfc7587f3dbd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

Complexity theoretic limitations on learning halfspaces (2015, background): “This problem has been extensively studied, and assumptions about its intractability were used to prove hardness of approximation results [1], establish public-key cryptography [1, 6], and statistical-computational tradeoffs [12].”
Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique (2004, methodology): “Assuming this hypothesis, Feige shows that Graph Min-Bisection, Densest Subgraph and Bipartite Clique have no PTAS (Alekhnovich [1] later shows these re-”
New Algorithms for Learning in Presence of Errors (2011, background): “Such difficulties might lead one to think that our " reduction to gaussian elimination with polynomial coefficients " is too restricted as a computational model and it is unable to solve the LPN problem.”
On lattices, learning with errors, random linear codes, and cryptography (2005, background): “[6] M. Alekhnovich.”
Learning Polynomials with Neural Networks (2014, background): “For example, in the boolean case (where x is distributed over the boolean cube), this is at least as hard as ”learning parity with noise” and ”learning juntas” – problems that we suspect do not admit any efficient algorithms and are even used as cryptographic primitives [1, 15, 13, 4].”
Decoding Random Binary Linear Codes in 2n/20: How 1+1=0 Improves Information Set Decoding (2012, background): “Also closely related to random linear codes is the learning parity with noise (LPN) problem that is frequently used in cryptography [1, 13, 16].”
On lattices, learning with errors, random linear codes, and cryptography (2009, background): “See Alekhnovich’s paper [7] for some related work.”
Computational Limitations in Robust Classification and Win-Win Results (2019, result): “Proof This proof is identical to the proof of security of Aleknovich’s public key encryption scheme Alekhnovich (2003). Observe that D0, D1 are completely specified by the matrix H.”
Efficient Pseudorandom Correlation Generators: Silent OT Extension and More (2019, methodology): “For example, when D samples a sparse, low-weight vector e over F2, and the linear map is a random matrixH, then distinguishing (H, e·H) from random is as hard as the problem of decoding a random binary linear code, which corresponds to the standard LPN assumption [12, 2].”
Better Key Sizes (and Attacks) for LWE-Based Encryption (2011, methodology): “The smaller keys come from a different style of security proof, which is very similar to the proofs for the coding-based cryptosystem of Alekhnovich [ 6 ] and the subset sum-based cryptosystem of Lyubashevsky, Palacio, and Segev [21].”
Homomorphic Encryption (2017, background): “Although Brakerski’s result does not rule out basing homomorphic encryption on LPN, it does say that the decryption procedure of that scheme must be at least “somewhat complicated”, rather than the simple inner product of some LPN-based (non homomorphic) schemes such as [1].”
Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems (2009, methodology): “This construction is based on a plausible, yet non-standard, assumption of Alekhnovich [3].”