4 papers
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…
Diverse Committees with Incomplete or Inaccurate Approval Ballots
Feline Lindeboom, Martijn Brehm, Davide Grossi +1
We study diversity in approval-based committee elections with incomplete or inaccurate information. We define diversity according to the Maximum Coverage problem, which is known to…
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…
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…