Proving hard-core predicates using list decoding
Explore this paper's citation graph
- Type
- article
- Published
- 2003-10-11
- Cited by
- 122
- References
- 22
- OpenAlex
- https://openalex.org/W2152263739
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:603413
Keywords
Decoding methods, Code word, Computer science, Predicate (mathematical logic), Algorithm
References
- All Bits ax+b mod p are Hard (Extended Abstract)
- Randomized Interpolation and Approximation of Sparse Polynomials
- On the cryptographic security of single RSA bits
- A method for obtaining digital signatures and public-key cryptosystems
- Stronger Security Proofs for RSA and Rabin Bits
- A hard-core predicate for all one-way functions
- Foundations of Cryptography: Basic Tools
- Learning decision trees using the Fourier spectrum
- The Discrete Logarithm Hides O(log n) Bits
- Theory and application of trapdoor functions
- A Simple Unpredictable Pseudo-Random Number Generator
- List decoding: algorithms and applications
- RSA and Rabin Functions: Certain Parts are as Hard as the Whole
- Why and how to establish a private code on a public network
- How to generate cryptographically strong sequences of pseudo random bits
- The security of individual RSA bits
- Probabilistic Encryption
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Learning Decision Trees Using the Fourier Spectrum
- Theory and application of trapdoor functions
Cited by
- Deterministic Sparse Fourier Approximation via Fooling Arithmetic Progressions.
- On the computational power of quantum computers
- Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
- Simple and practical algorithm for sparse Fourier transform
- A Fourier-Analytic Approach to Reed–Muller Decoding
- Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms
- Adaptive sub-linear Fourier algorithms
- Decodability of group homomorphisms beyond the johnson bound
- Learning noisy characters, multiplication codes, and cryptographic hardcore predicates
- Simulating Special but Natural Quantum Circuits
- List decoding of noisy Reed-Muller-like codes
- Introduction to Modern Cryptography, Second Edition
- Rapidly computing sparse Legendre expansions via sparse Fourier transforms
- A Combinatorial Aliasing-Based Sparse Fourier Transform
- Input-adaptive parallel sparse fast fourier transform for stream processing
- Improved sparse fourier approximation results: faster implementations and stronger guarantees
- Recent Developments in the Sparse Fourier Transform: A compressed Fourier transform for big data
- Improved time bounds for near-optimal sparse Fourier representations
- Explicit small sets with ε-discrepancy on Bohr sets
- Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
Related papers
- Simplification for Turbo product code decoding algorithm
- An Improved A^ Decoding Algorithm With List Decoding
- New decoding algorithm for a class of simple iterated codes–its application to decoding algorithm for reed‐muller codes
- A Low-Complexity Ordered Statistics Decoding Algorithm for Short Polar Codes
- List Decoding of Generalized Reed-Solomon Codes by Using a Modified Extended Key Equation Algorithm
- A Cascadable Pragmatic Block Decoding Algorithm Exploiting Channel Measurement Information
- A new step-by-step complete decoding algorithm for binary cyclic codes
- A new adaptive two-stage maximum-likelihood decoding algorithm for linear block codes
- Improved Segmented SC-Flip Decoding of Polar Codes Based on Gaussian Approximation