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…
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…