A quick post on Chen’s algorithm
Update (April 19): Yilei Chen announced the discovery of a bug in the algorithm, which he does not know how to fix. This was independently discovered by Hongxun Wu and Thomas Vidick. At present, the paper does not provide a polynomial-time algorithm for solving LWE. If you’re a normal person — that is, a person who doesn’t obsessively follow the latest cryptography news — you probably missed last
The Simple Beauty of XOR Floating Point Compression
I recently implemented a small program to visualize the inner workings of a scheme that compresses floating point timeseries by XORing subsequent values. The resulting visualizations are quite neat and made it much easier for me to understand this beautiful algorithm than any of the explanations that I had previously encountered. Hacker News (280 points, 68 comments) The algorithm The algorithm1Th
Introducing Sunlight, a CT implementation built for scalability, ease of operation, and reduced cost
Introducing Sunlight, a CT implementation built for scalability, ease of operation, and reduced cost Let’s Encrypt is proud to introduce Sunlight, a new implementation of a Certificate Transparency log that we built from the ground up with modern Web PKI opportunities and constraints in mind. In partnership with Filippo Valsorda, who led the design and implementation, we incorporated feedback from
Ristretto Group - Develop with pleasure!
最近、よく見かけるRistrettoについて調べてみた↓ https://ristretto.group/ Ristrettoが解決すること Ristrettoは、楕円曲線の内、曲線上の有効な点の総数（位数）が素数ではない楕円曲線から、位数が素数となる群を構築する抽象化レイヤーを提供するための手法。 位数が素数だと何が嬉しいのか？ 楕円曲線暗号の安全性は、楕円曲線上の離散対数問題（ECDLP）の困難さに基づいており、この難易度は曲線の計算に使用する群の位数が素数である場合に最大になる。 単位元を除く群内のすべての点が生成元になり得る。 群の演算（点の加算や、スカラー乗算）が比較的単純になる。 安全な楕円曲線のパラメーターを選択するのが比較的単純になる。 部分群（サブグループ）が存在しないので、t小さな部分群を利用した攻撃を回避できる。 最後の部分群を利用した攻撃について、暗号通貨で有名なの
Kalman Filter Explained Simply - The Kalman Filter
Most tutorials for the Kalman Filter are difficult to understand because they require advanced math skills to understand how the Kalman Filter is derived. If you have tried to read Rudolf E Kalman’s 1960 Kalman Filter paper, you know how confusing this concept can be. But do you need to understand how to derive the Kalman Filter in order to use it? No. If you want to design and implement a Kalman
マルチエージェント経路計画の紹介
グラフ上の複数エージェントに対し, 互いに衝突のない経路を計算する問題は マルチエージェント経路計画 (Multi-Agent Path Finding; MAPF) と呼ばれる. MAPF はロボット群による倉庫内での荷物搬送など, 多数の魅力的な応用があり, 2010年代前半から人工知能・ロボティクス分野で盛んに研究が行われている.1 本記事は日本語のチュートリアルを提供する. お断り: 正確な話をすることが目的ではないので, 多少の不備には目を瞑ってほしい. 問題定義# まずは, どのような問題が対象か, はっきりさせておこう. 文献によってバリエーションがあるのだが, 基本的なフォームは次の通り. MAPF 問題はグラフ $G=(V, E)$, エージェントのチーム $A= \lbrace 1, 2, \ldots, n\rbrace $, 各エージェント $i \in A$ に対
The design and implementation of a lock-free ring-buffer with contiguous reservations
The design and implementation of a lock-free ring-buffer with contiguous reservations Building a lock free continuous ring buffer This is the story of how Andrea Lattuada (PhD student at ETH Zurich) and James Munns (from Ferrous Systems) designed and implemented (two versions!) of an high-perf lock-free ring-buffer for cross-thread communication. If any of those words look scary to you, don't fret
Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping
While Transformers have enabled tremendous progress in various application settings, such architectures still trail behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks. This is accomplished by training an encoder-decoder Transformer model to predict the search dynamics of the $A^*$ se
Huffman Codes – How Do They Work?
Tomorrow, you (a corporate spy!) will be in the office across the street and I want to signal to you what I’ve been doing throughout the day. I will do so by putting up post-it notes on a window. I have three colours of post-its: 🟥, 🟨 and 🟩.11 If a lot of people have problem with their fonts not rendering these unicode characters as coloured squares, let me know. We have just three colours, so
Zig's HashMap - Part 1
Like most hash map implementations, Zig's std.HashMap relies on 2 functions, hash(key: K) u64 and eql(key_a: K, key_b: K) bool. The hash function takes a key and returns an unsigned 64 bit integer, known as the hash code. The same key always returns the same hash code. The hash function can produce the same hash code for two different keys which is one reason we also need eql: to determine if two
Collision Detection
COLLISION DETECTION Jeff Thompson The collision of objects underlies most game experiences and user-interfaces. Baseball bats collide with balls, zombies bump into walls, and Mario lands on platforms and stomps turtles. Even something as simple as clicking a button (a rectangle) with your mouse (a point) is a collision. This book explains the algorithms behind those collisions using basic shapes l
Dynamic Programming is not Black Magic - Quentin Santos
This year’s Advent of Code has been brutal (compare the stats of 2023 with that of 2022, especially day 1 part 1 vs. day 1 part 2). It included a problem to solve with dynamic programming as soon as day 12, which discouraged some people I know. This specific problem was particularly gnarly for Advent of Code, with multiple special cases to take into account, making it basically intractable if you
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Solving the minimum cut problem for undirected graphs
Knuth–Morris–Pratt illustrated | Journal of Functional Programming | Cambridge Core
A Square-Root Kalman Filter Using Only QR Decompositions
A math puzzle and a better algorithm for top-k | Quickwit
code-reading/algorithm/ristretto255 at master · koba-e964/code-reading
Prolly Trees
The Hunt for the Missing Data Type
Understanding Mesh Allocator