1 citations · 2 across the 3 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2022★ 1 cited
Lattice Problems Beyond Polynomial Time
Divesh Aggarwal, Huck Bennett, Zvika Brakerski +6
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-…
cs.CC2020
On the Hardness of Average-case k-SUM
Zvika Brakerski, Noah Stephens-Davidowitz, Vinod Vaikuntanathan
In this work, we show the first worst-case to average-case reduction for the classical -SUM problem. A -SUM instance is a collection of integers, and the goal of the -…