\(k\)-SUM in the sparse regime: complexity and applications
From MaRDI portal
Publication:6648210
DOI10.1007/978-3-031-68379-4_10MaRDI QIDQ6648210
Shweta Agrawal, [[Person:6107249|Author name not available (Why is that?)]], Akhil Vanukuri, Sagnik Saha, Prashant Nalini Vasudevan
Publication date: 4 December 2024
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimal detection of sparse principal components in high dimension
- The extended \(k\)-tree algorithm
- Explicit construction of linear sized tolerant networks
- Preprocessing chains for fast dihedral rotations is hard or even impossible.
- Hiding cliques for cryptographic security
- Proofs of Work from worst-case assumptions
- LPN decoded
- On a class of \(O(n^ 2)\) problems in computational geometry
- An algorithmic framework for the generalized birthday problem
- On building fine-grained one-way functions from strong average-case hardness
- Public-key cryptography in the fine-grained setting
- Low-memory attacks against two-round Even-Mansour using the 3-XOR problem
- Subquadratic algorithms for 3SUM
- Refinements of the k-tree Algorithm for the Generalized Birthday Problem
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN
- Public-key cryptography from different assumptions
- Towards polynomial lower bounds for dynamic problems
- Improved Generic Algorithms for Hard Knapsacks
- Better Key Sizes (and Attacks) for LWE-Based Encryption
- Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
- Solving low-density subset sum problems
- Large Cliques Elude the Metropolis Process
- Computing Partitions with Applications to the Knapsack Problem
- A Pseudorandom Generator from any One-way Function
- Threesomes, Degenerates, and Love Triangles
- Higher Lower Bounds from the 3SUM Conjecture
- A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
- POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
- More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems
- Average-case fine-grained hardness
- A subquadratic algorithm for 3XOR
- Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
- Data structures meet cryptography: 3SUM with preprocessing
- Leftover Hash Lemma, Revisited
- SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
- Exact Weight Subgraphs and the k-Sum Conjecture
- On lattices, learning with errors, random linear codes, and cryptography
- Noise-tolerant learning, the parity problem, and the statistical query model
- Lower bounds for linear degeneracy testing
- Parallel and concurrent security of the HB and \(HB^{+}\) protocols
- A simple near-linear pseudopolynomial time randomized algorithm for subset sum
This page was built for publication: \(k\)-SUM in the sparse regime: complexity and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6648210)
