scientific article; zbMATH DE number 7768374

DOI10.4230/LIPICS.APPROX/RANDOM.2021.29MaRDI QIDQ6090904zbMATH OpenFDO

Authors Zvika Brakerski, Noah Stephens-Davidowitz, Vinod Vaikuntanathan

Publication date 20 November 2023

Full work available at URL https://arxiv.org/abs/2010.08821

zbMATH Keywords

\(k\)-SUMaverage-case hardnessfine-grained complexity

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cited in

(6)

• On the hardness of finding subsets with equal average
• Average-case lower bounds for the plurality problem
• Lattice problems beyond polynomial time
• On Wagner's k-tree algorithm over integers
• Fine-grained complexity in a world without cryptography
• Fine-grained cryptanalysis: tight conditional bounds for dense \(k\)-SUM and \(k\)-XOR

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090904)