16 papers
Can LLMs be Used to Simplify Algorithms? Simpler Algorithms for Vertex Coloring and Edge Connectivity
Antoine El-Hayek, Monika Henzinger, Da Wei Zheng
Having simple algorithms is important for the practical adoption of new algorithms. However, simplifying existing algorithms is a field that does not usually receive a lot of atten…
Edit-Neighboring Data Streams and Privacy under Continual Observation
Joel Daniel Andersson, Anamay Chaturvedi, Monika Henzinger +1
Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the…
Incremental Approximate Maximum Flow via Residual Graph Sparsification
Gramoz Goranci, Monika Henzinger, Harald Räcke +1
We give an algorithm that, with high probability, maintains a -approximate - maximum flow in undirected, uncapacitated -vertex graphs undergoing edge insertion…
Near-Optimal Generalized Private Testing
Anamay Chaturvedi, Monika Henzinger, Jalaj Upadhyay
In differential privacy (DP), the generalized private testing problem was introduced by Liu and Talwar (STOC 2019). Given a dataset and a sequence of black-box…
Expander Hierarchies for Normalized Cuts on Graphs
Kathrin Hanauer, Monika Henzinger, Robin Münk +2
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their…
Concurrent Composition for Differentially Private Continual Mechanisms
Monika Henzinger, Roodabeh Safavi, Salil Vadhan
Many intended uses of differential privacy involve a that is set up to run continuously over a long period of time, making more statistical releases…