Fast n-fold Boolean convolution via additive combinatorics
From MaRDI portal
Fast \(n\)-fold Boolean convolution via additive combinatorics
Cites work
- A faster pseudopolynomial time algorithm for subset sum
- A near-linear pseudopolynomial time algorithm for subset sum
- A simple near-linear pseudopolynomial time randomized algorithm for subset sum
- A subquadratic approximation scheme for partition
- Additive combinatorics
- An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
- Clustered Integer 3SUM via Additive Combinatorics
- Dense subset sum may be the hardest
- Deterministic Length Reduction: Fast Convolution in Sparse Data and Applications
- Essentially optimal sparse polynomial multiplication
- Fast and simple modular subset sum
- Fast modular subset sum using linear sketching
- Faster space-efficient algorithms for subset sum and k-sum
- Modular subset sum, dynamic strings, and zero-sum sets
- Nearly Optimal Sparse Polynomial Multiplication
- On the complexity of multivariate blockwise polynomial multiplication
- On the relationship between histogram indexing and block-mass indexing
- Output-sensitive algorithms for sumset and sparse polynomial multiplication
- Parallel sparse polynomial multiplication using heaps
- Pattern matching for spatial point sets
- SETH-based lower bounds for subset sum and bicriteria path
- Sparse nonnegative convolution is equivalent to dense nonnegative convolution
- Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
- Verifying candidate matches in sparse and wildcard matching
- What can (and can't) we do with sparse polynomials?
This page was built for publication: Fast \(n\)-fold Boolean convolution via additive combinatorics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241138)
