Doctoral Thesis Oral Defense - Madhusudan Reddy Pittu

— 12:30pm

Location:
In Person and Virtual - ET - Traffic21 Classroom, Gates Hillman 6501 and Zoom

Speaker:
MADHUSUDHAN REDDY PITTU , Ph.D. Candidate, Ph.D. Program in Algorithms, Combinatorics and Optimization, Computer Science Department, Carnegie Mellon University
https://mathrulestheworld.github.io/

Fairness, Diversity, Explainability, and Robustness for Algorithmic Decision-Making

This thesis investigates foundational algorithmic challenges that arise when embedding fairness, diversity, explainability, and robustness into computational decision-making. As machine learning systems, resource allocation mechanisms, and data analysis pipelines increasingly influence critical decisions, it is essential that these systems uphold not only efficiency and accuracy but also ethical and structural guarantees. However, enforcing these principles introduces complex trade-offs and computational difficulties.

We address five core problems that capture different facets of algorithmic decision-making under structural and informational constraints: (1) determinant maximization under matroid constraints, modeling the selection of diverse and representative subsets; (2) approximation of the weighted Nash Social Welfare objective, a fairness-centric formulation in indivisible resource allocation; (3) constrained subspace approximation, which enforces group-level representation in data summarization; (4) explainable clustering, which trades off interpretability and clustering quality using decision trees with axis-aligned threshold cuts; and (5) combinatorial optimization using comparison oracles, which enables robust decision-making in uncertain or preference-driven environments.

Each of these problems introduces structural constraints that challenge conventional algorithmic techniques. We develop new frameworks that combine combinatorial methods, convex and non-convex relaxations, convex geometry, and probabilistic methods. The resulting algorithms offer improved approximation guarantees, shed light on key trade-offs between fairness, interpretability, and performance, and support the development of more equitable, interpretable, diverse, and reliable algorithmic systems. These contributions have broad implications in machine learning, economics, data summarization, and human-in-the-loop decision-making.

Thesis Committee
David P. Woodruff (Co-Chair)
Anupam Gupta (Co-chair)
Prasad Tetali
Mohit Singh (Georgia Institute of Technology)

For More Information:
matthewstewart@cmu.edu

Add event to Google
Add event to iCal