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.DS2024
Setting Targets is All You Need:Improved Order Competitive Ratio for Online Selection
Liyan Chen, Nuozhou Sun, Zhihao Gavin Tang
There is a rising interest for studying the online benchmark as an alternative of the classical offline benchmark in online stochastic settings. Ezra, Feldman, Gravin, and Tang (SO…