Joint Theory Lunch Seminar / Speaking Skills Talk - Noah Singer September 10, 2025 12:00pm — 1:00pm Location: In Person - Gates Hillman 8102 Speaker: NOAH SINGER , Ph.D. StudentComputer Science DepartmentCarnegie Mellon University https://noahsinger.org/ A quadratic classical speedup for planted kXOR A recent work of Schmidhuber et al. (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted kXOR problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant k. Thus for such k, the quantum advantage of Schmidhuber et al. becomes only quadratic.Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.Presented as part of the Theory Lunch SeminarPresented in Partial Fulfillment of the CSD Speaking Skills Requirement For More Information: matthewstewart@cmu.edu Add event to Google Add event to iCal
