2 papers
cs.CC2026
QMA Lower Bounds for Batch Verification via Approximate Degree
Mark Bun, Mandar Juvekar, Samuel King
We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify copies of a Boolean function depen…
cs.DS2026
Online Orthogonal Vectors Revisited
Karthik Gajulapalli, Alexander Golovnev, Samuel King +1
We prove new upper and lower bounds for the Online Orthogonal Vectors Problem (). In this problem, a preprocessing algorithm receives vectors $x_1,\ldo…