Improved Lower Bounds for Privacy under Continual Release
Bardiya Aryanfard, Monika Henzinger, David Saulpic, A. R. Sricharan
Incremental graph problems are surprisingly hard to solve accurately, fully dynamic ones are basically impossible.
Publications
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, Leqi Zhu
Use parallel composition of AboveThresholds to get better results for high-dimensional low-sensitivity queries.
Incremental Approximate Maximum Flow via Residual Graph Sparsification
Gramoz Goranci, Monika Henzinger, Harald Räcke, A. R. Sricharan
Sparsify the residual graph while maintaining the property “Presence of Augmenting Paths” whp., all under edge insertions.
Differentially Private Continual Release of Histograms and Related Queries
Monika Henzinger, Teresa Anna Steiner, A. R. Sricharan
Combining SVT and a histogram mechanism needs special conditions.
Connected Equitable Cake Division via Sperner’s Lemma
Umang Bhaskar, A. R. Sricharan, Rohit Vaish
Easier Equitable Cake Cutting, simpler than Envy-Freeness.
Private Counting of Distinct Elements in the Turnstile Model and Extensions
Monika Henzinger, Teresa Anna Steiner, A. R. Sricharan
Wait until the answer changes by a bit, then recompute.
Electrical Flows for Polylogarithmic Competitive Oblivious Routing
Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, A. R. Sricharan
A few electrical routings suffice to get polylogarithmic congestion.
Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs
Monika Henzinger, Ami Paz, A. R. Sricharan
Some dynamic problems are hard even on low-degree graphs, expanders, and power-law graphs.
On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
Umang Bhaskar, A. R. Sricharan, Rohit Vaish
Monotone chore division using top-trading envy cycle elimination (normal envy cycle doesn’t work).
Completely Mixed Bimatrix Games
T. Parthasarathy, Vasudha Sharma, A. R. Sricharan
Conditions for a few bimatrix games to have completely mixed strategies.