2 citations · 3 across the 6 of their papers we have counts for
9 papers · 1 filter
Lower Bounds on Matrix Rigidity via a Quantum Argument
Ronald de Wolf
The rigidity of a matrix measures how many of its entries need to be changed in order to reduce its rank to some value. Good lower bounds on the rigidity of an explicit matrix woul…
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
Hartmut Klauck, Robert Spalek, Ronald de Wolf
A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overa…
Robust Polynomials and Quantum Algorithms
Harry Buhrman, Ilan Newman, Hein Roehrig +1
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We co…
Quantum Symmetrically-Private Information Retrieval
Iordanis Kerenidis, Ronald de Wolf
Private information retrieval systems (PIRs) allow a user to extract an item from a database that is replicated over k>=1 servers, while satisfying various privacy constraints. We…
Quantum Zero-Error Algorithms Cannot be Composed
Harry Buhrman, Ronald de Wolf
We exhibit two black-box problems, both of which have an efficient quantum algorithm with zero-error, yet whose composition does not have an efficient quantum algorithm with zero-e…
Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument
Iordanis Kerenidis, Ronald de Wolf
A locally decodable code encodes n-bit strings x in m-bit codewords C(x), in such a way that one can recover any bit x_i from a corrupted codeword by querying only a few bits of th…