More on Average Case vs Approximation Complexity

No abstract is available for this paper.

• Publication year

  2003

• Venue

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

• Publication date

  2003-10-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00037-011-0029-x
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Some 3CNF properties are hard to test

  2003cited by this paper
• A spectral technique for random satisfiable 3CNF formulas

  2003influential reference
• Resolution lower bounds for the weak pigeon hole principle

  2002influential reference
• Some optimal inapproximability results

  2001cited by this paper
• On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes

  2001cited by this paper
• Pseudorandom generators in propositional proof complexity

  2000cited by this paper
• Probabilistic checking of proofs: a new characterization of NP

  1998cited by this paper
• Improved lower bounds on the rigidity of Hadamard matrices

  1998cited by this paper
• On the limits of non-approximability of lattice problems

  1998cited by this paper
• A Remark on Matrix Rigidity

  1997cited by this paper
• A public-key cryptosystem with worst-case/average-case equivalence

  1997cited by this paper
• Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity

  1995cited by this paper
• Natural proofs

  1994cited by this paper
• A note on matrix rigidity

  1993cited by this paper
• The hardness of approximate optima in lattices, codes, and systems of linear equations

  1993cited by this paper
• Proof verification and hardness of approximation problems

  1992cited by this paper
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice

  1990cited by this paper
• Small-bias probability spaces: efficient constructions and applications

  1990cited by this paper
• Clock-controlled shift registers: a review

  1989cited by this paper
• Dual vectors and lower bounds for the nearest lattice point problem

  1988cited by this paper
• Probabilistic Encryption

  1984cited by this paper
• On the Complexity of Derivation in Propositional Calculus

  1983cited by this paper
• A public key cryptosystem based on algebraic coding theory

  1978cited by this paper
• Graph-Theoretic Arguments in Low-Level Complexity

  1977cited by this paper

• Fuzzy Private Set Union via Oblivious Key Homomorphic Encryption Retrieval

  2026cites this paper
• An updatable encryption scheme for blockchain oracle based on post-quantum cryptography

  2026cites this paper
• Quantum security analysis of Wave

  2026cites this paper
• Limitations of the decoding-to-LPN reduction via code smoothing

  2025cites this paper
• Decoding Balanced Linear Codes With Preprocessing

  2025cites this paper
• Hardness of Problems with Hints in Code-Based Cryptography and Applications to Traitor Tracing

  2025cites this paper
• Unfolding Post-Quantum Cryptosystems: CRYSTALS-Dilithium, McEliece, BIKE, and HQC

  2025cites this paper
• Superposition Attacks Against LPN-Based Authentication Protocols

  2025cites this paper
• Key Recovery from Side-Channel Power Analysis Attacks on Non-SIMD HQC Decryption

  2025cites this paper
• Trapdoor Hash Functions and PIR from Low-Noise LPN

  2025cites this paper
• Better Codes for the HQC Cryptosystem

  2025cites this paper
• Fast Pseudorandom Correlation Functions from Sparse LPN

  2025cites this paper
• A Minrank-based Encryption Scheme \`a la Alekhnovich-Regev

  2025influential citation
• Trapdoor one-way functions from tensors

  2025cites this paper
• Designing QC-MDPC Public Key Encryption Schemes with Niederreiter's Construction and a Bit Flipping Decoder with Bounded DFR

  2025cites this paper
• Simon's Period Finding on a Quantum Annealer

  2025cites this paper
• Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders

  2025influential citation
• Post-Quantum Homomorphic Encryption: A Case for Code-Based Alternatives

  2025cites this paper
• Improving Algorithmic Efficiency using Cryptography

  2025cites this paper
• Encrypted Matrix-Vector Products from Secret Dual Codes

  2025cites this paper
• Secret-Key PIR from Random Linear Codes

  2025cites this paper
• Somewhat homomorphic encryption based on random codes

  2025influential citation
• Improved Search-to-Decision Reduction for Random Local Functions

  2025cites this paper
• Public-Key Encryption from the MinRank Problem

  2025cites this paper
• A New Approach to Large Party Beaver-Style MPC with Small Computational Overhead

  2025cites this paper
• Post-quantum PKE from Unstructured Noisy Linear Algebraic Assumptions: Beyond LWE and Alekhnovich's LPN

  2025influential citation
• Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems With Smaller Sizes

  2025cites this paper
• Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions

  2025cites this paper
• BitGC Made (More) Efficient

  2025cites this paper
• On the security of two IKKR-type code-based cryptosystems

  2025cites this paper
• AGB 2.0: Refined Algebraic Attack against Regular Syndrome Decoding for PCG Applications

  2025cites this paper
• Practical Secure Delegated Linear Algebra with Trapdoored Matrices

  2025influential citation
• HQC Beyond the Standard: Ciphertext Compression and Refined DFR Analysis

  2025cites this paper
• Quantum commitments from structured one-way quantum state generators, and more

  2025cites this paper
• Indistinguishability Obfuscation from Ring Key-Homomorphic Weak PRFs

  2025cites this paper
• Lossy Cryptography from Code-Based Assumptions Dense-Sparse LPN: A New Subexponentially Hard LPN Variant in SZK

  2025cites this paper
• Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography

  2024cites this paper
• Black-Box Non-Interactive Zero Knowledge from Vector Trapdoor Hash

  2024cites this paper
• The Learning Stabilizers with Noise problem

  2024cites this paper
• Batched Distributed Point Function from Sparse LPN and Homomorphic Secret Sharing

  2024cites this paper
• Indistinguishability Obfuscation from Well-Founded Assumptions

  2024cites this paper
• More Basis Reduction for Linear Codes: Backward Reduction, BKZ, Slide Reduction, and More

  2024cites this paper
• Quartic quantum speedups for planted inference

  2024cites this paper
• Simon’s Algorithm in the NISQ Cloud

  2024cites this paper
• On Stronger Computational Separations Between Multimodal and Unimodal Machine Learning

  2024cites this paper
• An iterative correction method for practically LPN solving

  2024cites this paper
• Smoothing Linear Codes by Rényi Divergence and Applications to Security Reduction

  2024cites this paper
• PERK: compact signature scheme based on a new variant of the permuted kernel problem

  2024cites this paper
• Non-interactive Zero-Knowledge from LPN and MQ

  2024cites this paper
• Structured-Seed Local Pseudorandom Generators and their Applications

  2024cites this paper
• On White-Box Learning and Public-Key Encryption

  2024cites this paper
• Garbled Circuits with 1 Bit per Gate

  2024cites this paper
• A provably masked implementation of BIKE Key Encapsulation Mechanism

  2024cites this paper
• Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems

  2024cites this paper
• Reduce and Prange: Revisiting Prange's Information Set Decoding for LPN and RSD

  2024cites this paper
• A Systematic Study of Sparse LWE

  2024cites this paper
• New constructions of pseudorandom codes

  2024cites this paper
• On Learning Parities with Dependent Noise

  2024cites this paper
• Algorithms for Sparse LPN and LSPN Against Low-noise (extended abstract)

  2024influential citation
• MinRank Gabidulin encryption scheme on matrix codes

  2024cites this paper
• Pseudorandomness of Decoding, Revisited: Adapting OHCP to Code-Based Cryptography

  2023cites this paper
• Combinatorially Homomorphic Encryption

  2023cites this paper
• Practically Solving LPN in High Noise Regimes Faster Using Neural Networks

  2023cites this paper
• Efficient Laconic Cryptography from Learning With Errors

  2023cites this paper
• Injective Rank Metric Trapdoor Functions with Homogeneous Errors

  2023cites this paper
• Actively Secure Arithmetic Computation and VOLE with Constant Computational Overhead

  2023cites this paper
• Immunizing Backdoored PRGs

  2023cites this paper
• A Mathematical Model for Curriculum Learning

  2023cites this paper
• Learning Hidden Markov Models Using Conditional Samples

  2023influential citation
• Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

  2023cites this paper
• Code-based Cryptography: Lecture Notes

  2023cites this paper
• Computational Wiretap Coding from Indistinguishability Obfuscation

  2023cites this paper
• Multi-party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN

  2023influential citation
• Derandomization with Minimal Memory Footprint

  2023cites this paper
• Expand-Convolute Codes for Pseudorandom Correlation Generators from LPN

  2023cites this paper
• Key-Agreement with Perfect Completeness from Random Oracles

  2023cites this paper
• Building Hard Problems by Combining Easy Ones

  2023cites this paper
• Oblivious Transfer with Constant Computational Overhead

  2023influential citation
• Theoretical Limits of Provable Security Against Model Extraction by Efficient Observational Defenses

  2023cites this paper
• Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding

  2023cites this paper
• Deploying hybrid quantum-secured infrastructure for applications: When quantum and post-quantum can work together

  2023cites this paper
• Non-interactive Secure Computation of Inner-Product from LPN and LWE

  2022cites this paper
• On The Pseudorandomness of the Decoding Problem via the Oracle Comparison Problem

  2022cites this paper
• Worst and Average Case Hardness of Decoding via Smoothing Bounds

  2022cites this paper
• The Limits of Provable Security Against Model Extraction

  2022cites this paper
• Correlated Pseudorandomness from Expand-Accumulate Codes

  2022cites this paper
• Towards Automating Cryptographic Hardware Implementations: a Case Study of HQC

  2022cites this paper
• On the non-universality of deep learning: quantifying the cost of symmetry

  2022cites this paper
• Skew‐cyclic codes based public‐key cryptosystem approach

  2022cites this paper
• RQC Revisited and More Cryptanalysis for Rank-Based Cryptography

  2022cites this paper
• A gapless code-based hash proof system based on RQC and its applications

  2022influential citation
• Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit

  2022cites this paper
• Public-Key Encryption from Homogeneous CLWE

  2022cites this paper
• Smoothing Codes and Lattices: Systematic Study and New Bounds

  2022cites this paper
• Washington University Open Scholarship Washington University Open Scholarship

  2022cites this paper
• Secure encryption from cyclic codes

  2022cites this paper
• Statistically Sender-Private OT from LPN and Derandomization

  2022cites this paper
• The Hardness of LPN over Any Integer Ring and Field for PCG Applications

  2022cites this paper
• On Codes and Learning With Errors over Function Fields

  2022cites this paper
• Moz Z 2 k arella: Efficient Vector-OLE and Zero-Knowledge Proofs Over Z 2 k

  2022cites this paper