4 citations · 17 across the 23 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
quant-ph2020★ 1 cited
Quantum learning algorithms imply circuit lower bounds
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur +2
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let be a class of polynomial-size concepts…
cs.CC2020
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
Marcel Dall'Agnol, Tom Gur, Oded Lachish
We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the struct…