33 citations · 43 across the 5 of their papers we have counts for
4 papers · 1 filter
Lower Bounds for Semi-adaptive Data Structures via Corruption
Pavel Dvořák, Bruno Loff
In a dynamic data structure problem we wish to maintain an encoding of some data in memory, in such a way that we may efficiently carry out a sequence of queries and updates to the…
Simulation Theorems via Pseudorandom Properties
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff +1
We generalize the deterministic simulation theorem of Raz and McKenzie [RM99], to any gadget which satisfies certain hitting property. We prove that inner-product and gap-Hamming s…
Reductions to the set of random strings: The resource-bounded case
Eric Allender, Harry Buhrman, Luke Friedman +1
This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we s…
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.…