33 citations · 43 across the 5 of their papers we have counts for
9 papers
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
Sepehr Assadi, Prantar Ghosh, Bruno Loff +2
The following question arises naturally in the study of graph streaming algorithms: "Is there any graph problem which is "not too hard", in that it can be solved efficiently with t…
State preparation by shallow circuits using feed forward
Harry Buhrman, Marten Folkertsma, Bruno Loff +1
In order to achieve fault-tolerant quantum computation, we need to repeat the following sequence of four steps: First, perform 1 or 2 qubit quantum gates (in parallel if possible).…
Memory Compression with Quantum Random-Access Gates
Harry Buhrman, Bruno Loff, Subhasree Patro +1
In the classical RAM, we have the following useful property. If we have an algorithm that uses memory cells throughout its execution, and in addition is sparse, in the sense th…
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks
Harry Buhrman, Bruno Loff, Subhasree Patro +1
Many computational problems are subject to a quantum speed-up: one might find that a problem having an O(n^3)-time or O(n^2)-time classic algorithm can be solved by a known O(n^1.5…
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…
The computational power of parsing expression grammars
Bruno Loff, Nelma Moreira, Rogério Reis
We study the computational power of parsing expression grammars (PEGs). We begin by constructing PEGs with unexpected behaviour, and surprising new examples of languages with PEGs,…
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.…