4 citations · 17 across the 23 of their papers we have counts for
4 papers · 1 filter
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for -Product Spaces
Tom Gur, Noam Lifshitz, Siqi Liu
We prove hypercontractive inequalities on high dimensional expanders. As in the settings of the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities…
Sublinear quantum algorithms for estimating von Neumann entropy
Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian
Entropy is a fundamental property of both classical and quantum systems, spanning myriad theoretical and practical applications in physics and computer science. We study the proble…
Derandomization of Cell Sampling
Alexander Golovnev, Tom Gur, Igor Shinkar
Since 1989, the best known lower bound on static data structures was Siegel's classical cell sampling lower bound. Siegel showed an explicit problem with inputs and possibl…
Quantum Proofs of Proximity
Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik +1
We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that…