4 citations · 4 across the 4 of their papers we have counts for
3 papers · 1 filter
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…
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…