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 learning the $t$ largest Fourier
characters of a given function $f \colon \{0,1\}^n \to \{0,1\}$ up to an
arbitrarily small error, wherein the verifier uses $\mathsf{poly}(t)$ random
examples. This improves upon the Interactive Goldreich-Levin protocol of
Goldwasser, Rothblum, Shafer, and Yehudayoff (ITCS 2021) whose sample
complexity is $\mathsf{poly}(t,n)$.
- For agnostically learning the class $\mathsf{AC}^0[2]$ under the uniform
distribution, we build on the work of Carmosino, Impagliazzo, Kabanets, and
Kolokolova (APPROX/RANDOM 2017) and design an interactive protocol, where given
a function $f \colon \{0,1\}^n \to \{0,1\}$, the verifier learns the closest
hypothesis up to $\mathsf{polylog}(n)$ multiplicative factor, using
quasi-polynomially many random examples. In contrast, this class has been
notoriously resistant even for constructing realisable learners (without a
prover) using random examples.
- For agnostically learning $k$-juntas under the uniform distribution, we
obtain an interactive protocol, where the verifier uses $O(2^k)$ random
examples to a given function $f \colon \{0,1\}^n \to \{0,1\}$. Crucially, the
sample complexity of the verifier is independent of $n$.
We also show that if we do not insist on doubly-efficient proof systems, then
the model becomes trivial. Specifically, we show a protocol for an arbitrary
class $\mathcal{C}$ of Boolean functions in the distribution-free setting,
where the verifier uses $O(1)$ labeled examples to learn $f$.

我们针对不均衡分布学习问题，构建了一种双效证明系统的交互式协议，该协议能够学习给定函数的最大傅立叶特征，学习类 AC^0 [2] 和 k-juntas。此外，我们还提供了一个用于布尔函数学习的新模型，样本复杂度与 n 无关。

关于交互证明学习的能力

On the Power of Interactive Proofs for Learning

We show how to efficiently simulate the sending of a message M to a receiver
who has partial information about the message, so that the expected number of
bits communicated in the simulation is close to the amount of additional
information that the message reveals to the receiver. This is a generalization
and strengthening of the Slepian-Wolf theorem, which shows how to carry out
such a simulation with low amortized communication in the case that M is a
deterministic function of X. A caveat is that our simulation is interactive.
As a consequence, we prove that the internal information cost (namely the
information revealed to the parties) involved in computing any relation or
function using a two party interactive protocol is exactly equal to the
amortized communication complexity of computing independent copies of the same
relation or function. We also show that the only way to prove a strong direct
sum theorem for randomized communication complexity is by solving a particular
variant of the pointer jumping problem that we define. Our work implies that a
strong direct sum theorem for communication complexity holds if and only if
efficient compression of communication protocols is possible.

本篇研究介绍了在接收方仅知晓信息部分的情况下，如何高效地模拟传递信息，使得所需传递的信息量逼近信息透露给接收方的额外信息量，这是 Slepian-Wolf 定理的一般化和加强。其中，作者证明了二进制交互协议的内部信息成本（即向各方透露的信息量）与计算相同关系或函数的独立副本的摊销通信复杂度相等，并证明了随机通信复杂度需要满足特定的指针跳跃问题变体才能证明强直和定理，该研究意味着只有当通信协议能有效压缩时，通信结论的强直和定理才成立。

信息等价于分摊通信

Information Equals Amortized Communication

We present a protocol which allows a client to have a server carry out a
quantum computation for her such that the client's inputs, outputs and
computation remain perfectly private, and where she does not require any
quantum computational power or memory. The client only needs to be able to
prepare single qubits randomly chosen from a finite set and send them to the
server, who has the balance of the required quantum computational resources.
Our protocol is interactive: after the initial preparation of quantum states,
the client and server use two-way classical communication which enables the
client to drive the computation, giving single-qubit measurement instructions
to the server, depending on previous measurement outcomes. Our protocol works
for inputs and outputs that are either classical or quantum. We give an
authentication protocol that allows the client to detect an interfering server;
our scheme can also be made fault-tolerant.
We also generalize our result to the setting of a purely classical client who
communicates classically with two non-communicating entangled servers, in order
to perform a blind quantum computation. By incorporating the authentication
protocol, we show that any problem in BQP has an entangled two-prover
interactive proof with a purely classical verifier.
Our protocol is the first universal scheme which detects a cheating server,
as well as the first protocol which does not require any quantum computation
whatsoever on the client's side. The novelty of our approach is in using the
unique features of measurement-based quantum computing which allows us to
clearly distinguish between the quantum and classical aspects of a quantum
computation.

提出了一种交互协议，使客户端的输入、输出和计算完全保密，并且不需要任何量子计算能力或记忆，可用于经典或量子输入 / 输出；引入身份验证协议，使其可以检测到干扰服务器。此外，作者进一步将其推广到全经典客户端，以在不泄露私密信息的情况下完成盲量子计算。