Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
From MaRDI portal
Publication:5479385
DOI10.1007/11538462zbMath1142.68399OpenAlexW2649657569MaRDI QIDQ5479385
Publication date: 7 July 2006
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11538462
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Number-theoretic algorithms; complexity (11Y16) Density, gaps, topology (11B05)
Related Items (37)
On solving LPN using BKW and variants, Implementation and analysis ⋮ Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN ⋮ Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes ⋮ Cryptography from Learning Parity with Noise ⋮ Quantum machine learning: a classical perspective ⋮ Asymptotically efficient lattice-based digital signatures ⋮ Quantum learning Boolean linear functions w.r.t. product distributions ⋮ Pseudorandom correlation functions from variable-density LPN, revisited ⋮ On the asymptotic complexity of solving LWE ⋮ Optimization of $$\mathsf {LPN}$$ Solving Algorithms ⋮ A non-heuristic approach to time-space tradeoffs and optimizations for BKW ⋮ Correlated pseudorandomness from expand-accumulate codes ⋮ Correlated pseudorandomness from the hardness of quasi-abelian decoding ⋮ Expand-convolute codes for pseudorandom correlation generators from LPN ⋮ Improved classical and quantum algorithms for subset-sum ⋮ The extended \(k\)-tree algorithm ⋮ BKW meets Fourier new algorithms for LPN with sparse parities ⋮ Improved combinatorial algorithms for the inhomogeneous short integer solution problem ⋮ An Improved Multi-set Algorithm for the Dense Subset Sum Problem ⋮ Agnostic Learning from Tolerant Natural Proofs ⋮ CPA/CCA2-secure PKE with squared-exponential DFR from low-noise LPN ⋮ Solving systems of linear Boolean equations with noisy right-hand sides over the reals ⋮ Improved Algorithms for the Approximate k-List Problem in Euclidean Norm ⋮ Some Recent Results on Local Testing of Sparse Linear Codes ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ An improved algorithm for learning sparse parities in the presence of noise ⋮ Parallel and concurrent security of the HB and \(HB^{+}\) protocols ⋮ Cryptanalysis of a hash function, and the modular subset sum problem ⋮ Breaking the circuit size barrier for secure computation under quasi-polynomial LPN ⋮ Algebraic and Correlation Attacks against Linearly Filtered Non Linear Feedback Shift Registers ⋮ Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN ⋮ Cryptography with constant input locality ⋮ Public-Key Cryptographic Primitives Provably as Secure as Subset Sum ⋮ The Complexity of Public-Key Cryptography ⋮ Pseudorandom Functions: Three Decades Later ⋮ Constructing Carmichael numbers through improved subset-product algorithms ⋮ Towards efficient LPN-based symmetric encryption
This page was built for publication: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
