In this paper, we construct new t-server Private Information Retrieval (PIR) schemes with communication complexity subpolynomial in the previously best known, for all but finitely many t. Our results are
based on combining derivatives (in the spirit of Woodruff-Yekhanin) with the Matching Vector
based PIRs of Yekhanin and Efremenko. Previously ... more >>>

We show that the complexity class of exponential-time Arthur Merlin with sub-exponential advice ($AMEXP_{/2^{n^{\varepsilon}}}$) requires circuit complexity at least $2^n/n$. Previously, the best known such near-maximum lower bounds were for symmetric exponential time by Chen, Hirahara, and Ren (STOC'24) and Li (STOC'24), or randomized exponential time with MCSP oracle and ... more >>>

In a recent work, Cormode, Dall'Agnol, Gur and Hickey (CCC, 2024) introduced the model of Zero-Knowledge Streaming Interactive Proofs (zkSIPs).
Loosely speaking, such proof-systems enable a prover to convince astreaming verifier that the input $x$, to which it has read-once streaming access, satisfies some property, in such a way that ... more >>>