Improved lower bounds for privacy under continual release @ PODS 2026
Extend fully dynamic lower bounds to the incremental setting with an incremental erasure of queries. Fully dynamic multiplicative error lower bounds by extending one way marginals.
Near-optimal differentially private graph algorithms via the multidimensional abovethreshold mechanism @ ESA 2025
Use parallel composition of AboveThresholds to get better results for high-dimensional low-sensitivity queries.
Incremental approximate maximum flow via residual graph sparsification @ ICALP 2025
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 @ AISTATS 2025
Combining SVT and a histogram mechanism needs special conditions.
Connected equitable cake division via sperner’s lemma @ Inf. Proc. Lett. 2025
Easier Equitable Cake Cutting, simpler than Envy-Freeness.
Private counting of distinct elements in the turnstile model and extensions @ RANDOM 2024
Wait until the answer changes by a bit, then recompute.
Electrical flows for polylogarithmic competitive oblivious routing @ ITCS 2024
A few electrical routings suffice to get polylogarithmic congestion.
Fine-grained complexity lower bounds for families of dynamic graphs @ ESA 2022
Some dynamic problems are hard even on low-degree graphs, expanders, and power-law graphs.
Completely mixed bimatrix games @ Proceedings - Mathematical Sciences 2020
Conditions for a few bimatrix games to have completely mixed strategies.