3 papers
cs.AI2026
How to Avoid Debate: Scalable AI Safety via Doubly-Efficient Interactive Proofs
Liyan Chen, Yael Tauman Kalai, Zoe Xi
As AI models continue to develop powerful capabilities, it becomes critical that we are able to verify that their output is aligned with our intentions. A recent line of work focus…
cs.CC2026
Towards a Doubly Efficient IP=PSPACE
Liyan Chen, Matthew M. Hong, Yael Tauman Kalai +1
We show that every language in PSPACE decidable by a Turing machine in time admits a doubly efficient interactive proof system: the prover runs in time polynom…
cs.DS2022
Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings
Zoe Xi, William Kuszmaul
Dynamic Time Warping (DTW) is a widely used similarity measure for comparing strings that encode time series data, with applications to areas including bioinformatics, signature ve…