4 papers
Parity and Pattern Detection in Permutation Streams
Mark Braverman, Or Zamir
Consider a permutation of whose values arrive one at a time. We resolve two questions about the space needed to decide natural properties of such input: First, computing the…
Practical Secure Delegated Linear Algebra with Trapdoored Matrices
Mark Braverman, Stephen Newman
Most heavy computation occurs on servers owned by a second party. This reduces data privacy, resulting in interest in data-oblivious computation, which typically severely degrades…
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…
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…