BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Interactive proofs for verifying (quantum) learning and testing - 
 Matthias Caro (Warwick)
DTSTART:20250116T140000Z
DTEND:20250116T150000Z
UID:TALK224716@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:We consider the problem of testing and learning from data in t
 he presence of resource constraints\, such as limited memory or weak data 
 access\, which place limitations on the efficiency and feasibility of test
 ing or learning. In particular\, we ask the following question: Could a re
 source-constrained learner/tester use interaction with a resource-unconstr
 ained but untrusted party to solve a learning or testing problem more effi
 ciently than they could without such an interaction? In this work\, we ans
 wer this question both abstractly and for concrete problems\, in two compl
 ementary ways: For a wide variety of scenarios\, we prove that a resource-
 constrained learner cannot gain any advantage through classical interactio
 n with an untrusted prover. As a special case\, we show that for the vast 
 majority of problems in which quantum memory is a meaningful resource\, a 
 memory-constrained quantum algorithm cannot overcome its limitations via c
 lassical communication with a memory-unconstrained quantum prover. In cont
 rast\, when quantum communication is allowed\, we construct a variety of i
 nteractive proof protocols\, for specific learning and testing problems\, 
 which allow memory-constrained quantum verifiers to gain significant advan
 tages through delegation to untrusted provers. These results highlight bot
 h the limitations and potential of delegating learning and testing problem
 s to resource-rich but untrusted third parties.
LOCATION:Computer Laboratory\, William Gates Building\, Room FW26.
END:VEVENT
END:VCALENDAR