CS Events

PhD Defense Approximation Algorithms under Informational and Structural Constraints: Robustness, Fairness and Privacy
Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close Friday, June 12, 2026, 09:00am - 11:00pm

Speaker: Prathamesh Dharangutte

Bio

Location : CoRE 301

Committee: 

Professor Jie Gao (advisor)

Assistant Professor Sumegha Garg 

Assistant Professor Jalaj Upadhyay 

Assistant Professor Sandeep Silwal (external committee member)

Event Type: PhD Defense

Abstract: The classical theory of approximation algorithms assumes exact and complete access to the input, with solution quality as the main requirement on the output. Both premises fail in many algorithmic problems in the modern world: input access is often expensive, noisy, or evolving (\emph{informational} constraints), and outputs may be required to satisfy properties beyond approximation guarantees (\emph{structural} constraints). This thesis studies the design of approximation algorithms in such settings, treating informational and structural constraints as formal design parameters. The contributions cover three families of problems, each engaging a distinct combination of constraints.\emph{Informational.} In the weak-strong oracle model for metric optimization, we give a $(1+\eps)$-coreset for $(k,z)$-clustering and lower bounds and tight algorithm for metric MST. In the fully dynamic setting, we give an $O(1)$-approximation for correlation clustering in $O(\polylog n)$ amortized update time against an adaptive adversary. \emph{Structural.} We formalize districting as the packing of compact $c$-balanced subgraphs and characterize its hardness and approximability across various graph classes. On planar and minor-free graphs we obtain an $O(\log n)$-approximation via a new structural primitive, \emph{scattering separator}. \emph{Both.} For differentially private release, we design input perturbation mechanisms whose outputs natively satisfy structural requirements; integer-valued, invariant-preserving histograms and consistent, transparent range queries without relying on post-processing. For private combinatorial optimization, we characterize the privacy-utility tradeoff for Max-CSP under constraint-level differential privacy, with tight bounds for triangle-free bounded-degree CSPs and for Max-$k$XOR with odd $k$.

Organization: 

Contact  Professor Jie Gao

Zoom Link: https://rutgers.zoom.us/my/ptd39?pwd=eDZKbW9ydXZXRVVKZFo2TVIxTTYvQT09
Meeting passcode: 770335