Sieving in practice: The Generalized Sieve Kernel (G6K)

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=g4fGalYrvAI


Duration: 1:09:11
694 views
9

Elena Kirshanova (I.Kant Baltic Federal University)
Lattices: Algorithms, Complexity, and Cryptography
Seminar, May 5, 2020
https://simons.berkeley.edu/events/sieving-practice-generalized-sieve-kernel-g6k

In this talk I will explain the way sieving algorithms are implemented in the Generalized Sieve Kernel(G6K) -- an open-source implementation of the currently fastest sieve in practice. I will talk about the Nguen-Vidick sieve algorithm, tuple sieve, and the way these algorithms can be sped up with locality-sensitive hashing, as well about several tricks that allowed to improve the performance of the implementation.

Based on joint work with Martin R. Albrecht, Leo Ducas, Gottfried Herold, Eamonn W. Postlethwaite, Marc Stevens



Other Videos By Simons Institute for the Theory of Computing


2020-07-20Perspectives on Digital Contact Tracing
2020-07-15Advances in Boolean Function Analysis — On the Fourier-Entropy Influence Conjecture
2020-07-15Advances in Boolean Function Analysis — On the Fourier-Entropy Influence Conjecture
2020-06-29Berkeley in the 80s, Episode 2: Manuel Blum
2020-06-25Computational and Statistical Tools to Control a Pandemic | Theoretically Speaking Series
2020-05-14Quantum Random Walks
2020-05-14Position-based Quantum Cryptography
2020-05-14Indistinguishability Obfuscation from Simple-to-State Hard Problems
2020-05-14Quantum Linear Algebra With Near-Optimal Complexities
2020-05-12Candidate iO from Homomorphic Encryption Schemes
2020-05-12Sieving in practice: The Generalized Sieve Kernel (G6K)
2020-05-10WIT: Women in Theory (of Computer Science) — I Will Survive!
2020-05-08Panel Discussion
2020-05-08Co-Design of Almost Universal Quantum Computers
2020-05-08Quantum Computing With Stabilized Cat Qubits
2020-05-07Obstacles to State Preparation and Variational Optimization from Symmetry Protection
2020-05-07Divide-And-Conquer Hybrid Methods for Smaller Quantum Computers
2020-05-07Classical Algorithms for Quantum Mean Values
2020-05-06Designing Hamiltonians for Quantum Adiabatic Optimization
2020-05-06Characterizing and Operating Noisy Quantum Computers
2020-05-06The Power of Random Quantum Circuits


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing