3 papers
cs.CR2026
Fast Bounded-Independence Functions and Their Duals
Martijn Brehm, Yuval Ishai, Nicolas Resch
We continue the study of {\em fast} functions, computable by linear-size circuits, that share useful properties of random functions. Motivated by cryptographic applications, we gen…
cs.IT2025
Linear time encodable binary code achieving GV bound with linear time encodable dual achieving GV bound
Martijn Brehm, Nicolas Resch
We initiate the study of what we term ``fast good codes'' with ``fast good duals.'' Specifically, we consider the task of constructing a rate 1/2 binary linear code such that both…
quant-ph2024
Assessing fault-tolerant quantum advantage for -SAT with structure
Martijn Brehm, Jordi Weggemans
For many problems, quantum algorithms promise speedups over their classical counterparts. However, these results predominantly rely on asymptotic worst-case analysis, which overloo…