2 papers
cs.CC2025
Interactive Proofs For Distribution Testing With Conditional Oracles
Ari Biswas, Mark Bun, Clément Canonne +1
We revisit the framework of interactive proofs for distribution testing, first introduced by Chiesa and Gur (ITCS 2018), which has recently experienced a surge in interest, accompa…
cs.DS2025
Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them
Clément L. Canonne, Yun Li, Seeun William Umboh
Local Computation Algorithms (LCA), as introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a type of ultra-efficient algorithms which, given access to a (large) input for a…