4 citations · 4 across the 4 of their papers we have counts for
4 papers
On the Power of Interactive Proofs for Learning
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh +3
We continue the study of doubly-efficient proof systems for verifying agnostic PAC learning, for which we obtain the following results. - We construct an interactive protocol for l…
Perfect Zero-Knowledge PCPs for #P
Tom Gur, Jack O'Connor, Nicholas Spooner
We construct perfect zero-knowledge probabilistically checkable proofs (PZK-PCPs) for every language in #P. This is the first construction of a PZK-PCP for any language outside BPP…
Provable Advantage in Quantum PAC Learning
Wilfred Salmon, Sergii Strelchuk, Tom Gur
We revisit the problem of characterising the complexity of Quantum PAC learning, as introduced by Bshouty and Jackson [SIAM J. Comput. 1998, 28, 1136-1153]. Several quantum advanta…
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…