1.2k citations · 3.7k across the 62 of their papers we have counts for
6 papers · 1 filter
Derandomizing from Random Strings
Harry Buhrman, Lance Fortnow, Michal Koucký +1
In this paper we show that BPP is truth-table reducible to the set of Kolmogorov random strings R_K. It was previously known that PSPACE, and hence BPP is Turing-reducible to R_K.…
Multiplayer XOR games and quantum communication complexity with clique-wise entanglement
Jop Briet, Harry Buhrman, Troy Lee +1
XOR games are a simple computational model with connections to many areas of complexity theory. Perhaps the earliest use of XOR games was in the study of quantum correlations. XOR…
The first peptides: the evolutionary transition between prebiotic amino acids and early proteins
Peter van der Gulik, Serge Massar, Dimitri Gilis +2
The issues we attempt to tackle here are what the first peptides did look like when they emerged on the primitive earth, and what simple catalytic activities they fulfilled. We con…
Some mathematical refinements concerning error minimization in the genetic code
Harry Buhrman, Peter T. S. van der Gulik, Steven M. Kelk +2
The genetic code has been shown to be very error robust compared to randomly selected codes, but to be significantly less error robust than a certain code found by a heuristic algo…
Arbitrarily little knowledge can give a quantum advantage for nonlocal tasks
Jonathan Allcock, Harry Buhrman, Noah Linden
It has previously been shown that quantum nonlocality offers no benefit over classical correlations for performing a distributed task known as nonlocal computation. This is where s…
A generalized Grothendieck inequality and entanglement in XOR games
Jop Briët, Harry Buhrman, Ben Toner
Suppose Alice and Bob make local two-outcome measurements on a shared entangled state. For any d, we show that there are correlations that can only be reproduced if the local dimen…