Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Optimality of Frequency Moment Estimation
Mark Braverman, Or Zamir
Estimating the second frequency moment of a stream up to multiplicative error requires at most bits of space, due to a seminal resul…
cs.DS2024
New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
Mark Braverman, Mahsa Derakhshan, Tristan Pollner +2
We study the polynomial-time approximability of the optimal online stochastic bipartite matching algorithm, initiated by Papadimitriou et al. (EC'21). Here, nodes on one side of th…