3 papers
cs.CR2026
Differentially Private Hierarchical Heavy Hitters
Ari Biswas, Graham Cormode, Yaron Kanza +2
The task of finding _Hierarchical_ Heavy Hitters (HHH) was introduced by Cormode et al. [VLDB 2003] as a generalisation of the heavy hitter problem. While finding HHH in data strea…
math.CO2026
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…
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…