50 citations · 56 across the 9 of their papers we have counts for
4 papers · 1 filter
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
A well-known result of Banaszczyk in discrepancy theory concerns the prefix discrepancy problem (also known as the signed series problem): given a sequence of unit vectors in $…
Online Discrepancy Minimization for Stochastic Arrivals
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
In the stochastic online vector balancing problem, vectors chosen independently from an arbitrary distribution in arrive one-by-one and must be…
Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla +1
We consider an online vector balancing question where vectors, chosen from an arbitrary distribution over , arrive one-by-one and must be immediately given a si…
Edge Estimation with Independent Set Oracles
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy +2
We study the task of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have ap…