9.7k citations · 18.6k across the 63 of their papers we have counts for
5 papers · 2 filters
Approximating Hereditary Discrepancy via Small Width Ellipsoids
Aleksandar Nikolov, Kunal Talwar
The Discrepancy of a hypergraph is the minimum attainable value, over two-colorings of its vertices, of the maximum absolute imbalance of any hyperedge. The Hereditary Discrepancy…
Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
Ittai Abraham, Cyril Gavoille, Anupam Gupta +2
We prove that any graph excluding as a minor has can be partitioned into clusters of diameter at most while removing at most fraction of the edges. This improves…
Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations
Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar
Consider a database of people, each represented by a bit-string of length corresponding to the setting of binary attributes. A -way marginal query is specified by a…
Random Rates for 0-Extension and Low-Diameter Decompositions
Anupam Gupta, Kunal Talwar
Consider the problem of partitioning an arbitrary metric space into pieces of diameter at most Δ, such every pair of points is separated with relatively low probability. We propose…
Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results
Anupam Gupta, Kunal Talwar, David Witmer
We give a 2-approximation algorithm for Non-Uniform Sparsest Cut that runs in time , where is the treewidth of the graph. This improves on the previous -appr…