12 citations · 12 across the 1 of their papers we have counts for
Showing 2025Show all
2 papers · 1 filter
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…
math.CO2025
Refuting Perfect Matchings in Spectral Expanders is Hard
Ari Biswas, Rajko Nenadov
This work studies the complexity of refuting the existence of a perfect matching in spectral expanders with an odd number of vertices, in the Polynomial Calculus (PC) and Sum of Sq…