Fetching the paper…
Reading the bibliography…
We consider sparse variants of the classical Learning Parities with random Noise (LPN) problem.
A hard-core predicate for all one-way functions
O. Goldreich and L. Levin · 1989
Earlier work this paper cites.
Cryptographic primitives based on hard learning problems
Avrim Blum, Merrick Furst, Michael Kearns, and Richard J. Lipton · 1994
Earlier work this paper cites.
Proving hard-core predicates using list decoding
Adi Akavia, Shafi Goldwasser, and Samuel Safra · 2003
Earlier work this paper cites.
More on average case vs approximation complexity
Michael Alekhnovich · 2003
Earlier work this paper cites.
Noise-tolerant learning, the parity problem, and the statistical query model
Avrim Blum, Adam Kalai, and Hal Wasserman · 2003
Earlier work this paper cites.
The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem
Vadim Lyubashevsky · 2005
Earlier work this paper cites.
Witnesses for non-satisfiability of dense random 3CNF formulas
Uriel Feige, Jeong Han Kim, and Eran Ofek · 2006
Earlier work this paper cites.
Attribute-efficient and non-adaptive learning of parities and dnf expressions
Vitaly Feldman · 2007
Earlier work this paper cites.
Small Linear Dependencies for Binary Vectors of Low Weight , pages 283–307
Uriel Feige · 2008
Earlier work this paper cites.
Fast cryptographic primitives and circular-secure encryption based on hard learning problems
Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai · 2009
Earlier work this paper cites.
On agnostic learning of parities, monomials, and halfspaces
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami · 2009
Earlier work this paper cites.
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2009
Earlier work this paper cites.
Public-key cryptography from different assumptions
Benny Applebaum, Boaz Barak, and Avi Wigderson · 2010
Earlier work this paper cites.
Robustness of the learning with errors assumption
Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan · 2010
Earlier work this paper cites.
New algorithms for learning in presence of errors
Sanjeev Arora and Rong Ge · 2011
Earlier work this paper cites.
On noise-tolerant learning of sparse parities and related problems
Elena Grigorescu, Lev Reyzin, and Santosh Vempala · 2011
Earlier work this paper cites.
Decoding random binary linear codes in 2n/20: how 1 + 1 = 0 improves information set decoding
Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer · 2012
Earlier work this paper cites.
IND-CCA secure cryptography based on a variant of the LPN problem
Nico Döttling, Jörn Müller-Quade, and Anderson C. A. Nascimento · 2012
Earlier work this paper cites.
Nearly optimal sparse fourier transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price · 2012
Earlier work this paper cites.
Cryptography from learning parity with noise
Krzysztof Pietrzak · 2012
Cited alongside, same era.
Pseudorandom generators with long stretch and low locality from random local one-way functions
Benny Applebaum · 2013
Cited alongside, same era.
Rounding sum-of-squares relaxations
Boaz Barak, Jonathan A. Kelner, and David Steurer · 2014
Cited alongside, same era.
Simple chosen-ciphertext security from low-noise LPN
Eike Kiltz, Daniel Masny, and Krzysztof Pietrzak · 2014
Cited alongside, same era.
How to refute a random csp
Sarah R. Allen, Ryan ODonnell, and David Witmer · 2015
Cited alongside, same era.
Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
Gregory Valiant · 2015
Cited alongside, same era.
Collision resistant hashing from sub-exponential learning parity with noise
Yu Yu, Jiang Zhang, Jian Weng, Chun Guo, and Xiangxue Li · 2019
Later among the works it cites.
Reconstruction under outliers for fourier-sparse functions
Xue Chen and Anindya De · 2020
Later among the works it cites.
Silver: Silent vole and oblivious transfer from hardness of decoding structured LDPC codes
Geoffroy Couteau, Peter Rindal, and Srinivasan Raghuraman · 2021
Later among the works it cites.
BKW meets fourier new algorithms for LPN with sparse parities
Dana Dachman-Soled, Huijing Gong, Hunter Kippen, and Aria Shahverdi · 2021
Later among the works it cites.
Indistinguishability obfuscation from well-founded assumptions
Aayush Jain, Huijia Lin, and Amit Sahai · 2021
Later among the works it cites.
An improved algorithm for learning sparse parities in the presence of noise
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cryptographic hardness of random local functions
Benny Applebaum · 2016
Cited alongside, same era.
Secure arithmetic computation with constant computational overhead
Benny Applebaum, Ivan Damgård, Yuval Ishai, Michael Nielsen, and Lior Zichron · 2017
Cited alongside, same era.
Exponential bounds for the hypergeometric distribution
Evan Greene and Jon A Wellner · 2017
Cited alongside, same era.
Time-space hardness of learning sparse parities
Gillat Kol, Ran Raz, and Avishay Tal · 2017
Cited alongside, same era.
Strongly refuting random CSPs below the spectral threshold
Prasad Raghavendra, Satish Rao, and Tselil Schramm · 2017
Cited alongside, same era.
On the complexity of random satisfiability problems with planted solutions
Vitaly Feldman, Will Perkins, and Santosh Vempala · 2018
Cited alongside, same era.
Di Yan, Yu Yu, Hanlin Liu, Shuoyao Zhao, and Jiang Zhang · 2021
Later among the works it cites.
Noisy tensor completion via the sum-of-squares hierarchy
Boaz Barak and Ankur Moitra · 2022
Later among the works it cites.
Correlated pseudorandomness from expand-accumulate codes
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, and Peter Scholl · 2022
Later among the works it cites.
Algorithms and certificates for boolean CSP refutation: Smoothed is no harder than random
Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar · 2022
Later among the works it cites.
Indistinguishability obfuscation from LPN over F p F_{p} , DLIN, and PRGs in N C 0 NC_{0}
Aayush Jain, Huijia Lin, and Amit Sahai · 2022
Later among the works it cites.
Multi-party homomorphic secret sharing and sublinear mpc from sparse LPN
Quang Dao, Yuval Ishai, Aayush Jain, and Huijia Lin · 2023
Later among the works it cites.
A simple and sharper proof of the hypergraph moore bound
Jun-Ting Hsieh, Pravesh K. Kothari, and Sidhanth Mohanty · 2023
Later among the works it cites.
Expand-convolute codes for pseudorandom correlation generators from lpn
Srinivasan Raghuraman, Peter Rindal, and Titouan Tanguy · 2023
Later among the works it cites.
Approximating the Number of Relevant Variables in a Parity Implies Proper Learning
Nader H. Bshouty and George Haddad · 2024
Closest in time.
Lossy cryptography from code-based assumptions
Quang Dao and Aayush Jain · 2024
Closest in time.
On learning parities with dependent noise
Noah Golowich, Ankur Moitra, and Dhruv Rohatgi · 2024
Closest in time.
Indistinguishability obfuscation from bilinear maps and lpn variants
Seyoon Ragavan, Neekon Vafa, and Vinod Vaikuntanathan · 2024
Closest in time.
New bounds for matrix multiplication: from alpha to omega
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou · 2024
Closest in time.