203 citations · 288 across the 21 of their papers we have counts for
31 papers
Optimizing Group-Fair Plackett-Luce Ranking Models for Relevance and Ex-Post Fairness
Sruthi Gorantla, Eshaan Bhansali, Amit Deshpande +1
In learning-to-rank (LTR), optimizing only the relevance (or the expected ranking utility) can cause representational harm to certain categories of items. Moreover, if there is imp…
Sampling Individually-Fair Rankings that are Always Group Fair
Sruthi Gorantla, Anay Mehrotra, Amit Deshpande +1
Rankings on online platforms help their end-users find the relevant information -- people, news, media, and products -- quickly. Fair ranking tasks, which ask to rank a set of item…
Socially Fair Center-based and Linear Subspace Clustering
Sruthi Gorantla, Kishen N. Gowda, Amit Deshpande +1
Center-based clustering (e.g., -means, -medians) and clustering using linear subspaces are two most popular techniques to partition real-world data into smaller clusters. How…
Online Algorithms for Matchings with Proportional Fairness Constraints and Diversity Constraints
Anand Louis, Meghana Nasre, Prajakta Nimbhorkar +1
Matching problems with group-fairness constraints and diversity constraints have numerous applications such as in allocation problems, committee selection, school choice, etc. More…
Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All
Atasi Panda, Anand Louis, Prajakta Nimbhorkar
We study the probabilistic assignment of items to platforms that satisfies both group and individual fairness constraints. Each item belongs to specific groups and has a preference…
Approximating CSPs with Outliers
Suprovat Ghoshal, Anand Louis
Constraint satisfaction problems (CSPs) are ubiquitous in theoretical computer science. We study the problem of StrongCSPs, i.e. instances where a large induced sub-instance has a…
Exact recovery algorithm for Planted Bipartite Graph in Semi-random Graphs
Akash Kumar, Anand Louis, Rameesh Paul
The problem of finding the largest induced balanced bipartite subgraph in a given graph is NP-hard. This problem is closely related to the problem of finding the smallest Odd Cycle…
Sampling Ex-Post Group-Fair Rankings
Sruthi Gorantla, Amit Deshpande, Anand Louis
Randomized rankings have been of recent interest to achieve ex-ante fairer exposure and better robustness than deterministic rankings. We propose a set of natural axioms for random…
Matchings with Group Fairness Constraints: Online and Offline Algorithms
Govind S. Sankar, Anand Louis, Meghana Nasre +1
We consider the problem of assigning items to platforms in the presence of group fairness constraints. In the input, each item belongs to certain categories, called classes in this…
Independent Sets in Semi-random Hypergraphs
Yash Khanna, Anand Louis, Rameesh Paul
A set of vertices in a hypergraph is called an independent set if no hyperedge is completely contained inside the set. Given a hypergraph, computing its largest size independent se…
On the Problem of Underranking in Group-Fair Ranking
Sruthi Gorantla, Amit Deshpande, Anand Louis
Search and recommendation systems, such as search engines, recruiting tools, online marketplaces, news, and social media, output ranked lists of content, products, and sometimes, p…
Robust Identifiability in Linear Structural Equation Models of Causal Inference
Karthik Abinav Sankararaman, Anand Louis, Navin Goyal
In this work, we consider the problem of robust parameter estimation from observational data in the context of linear structural equation models (LSEMs). LSEMs are a popular and we…
Group Fairness for Knapsack Problems
Deval Patel, Arindam Khan, Anand Louis
We study the knapsack problem with group fairness constraints. The input of the problem consists of a knapsack of bounded capacity and a set of items, each item belongs to a partic…
Approximation Algorithms and Hardness for Strong Unique Games
Suprovat Ghoshal, Anand Louis
The UNIQUE GAMES problem is a central problem in algorithms and complexity theory. Given an instance of UNIQUE GAMES, the STRONG UNIQUE GAMES problem asks to find the largest subse…
Planted Models for the Densest -Subgraph Problem
Yash Khanna, Anand Louis
Given an undirected graph , the Densest -subgraph problem (DkS) asks to compute a set of cardinality such that the weight of…
& Maximum Variance Embedding: Measuring and Optimizing Connectivity of A Graph Metric
Majid Farhadi, Anand Louis, Mohit Singh +1
Bobkov, Houdré, and the last author [2000] introduced a Poincaré-type functional parameter, , of a graph and related it to connectivity of the graph via Cheeger-type ineq…
Planted Models for -way Edge and Vertex Expansion
Anand Louis, Rakesh Venkat
Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a…
Approximation Algorithms for Partially Colorable Graphs
Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury
Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For and $k \in \m…
Stability of Linear Structural Equation Models of Causal Inference
Karthik Abinav Sankararaman, Anand Louis, Navin Goyal
We consider the numerical stability of the parameter recovery problem in Linear Structural Equation Model ($\LSEM$) of causal inference. A long line of work starting from Wright (1…
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
Naganand Yadati, Madhav Nimishakavi, Prateek Yadav +3
In many real-world network datasets such as co-authorship, co-citation, email communication, etc., relationships are complex and go beyond pairwise. Hypergraphs provide a flexible…
Semi-Random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
Anand Louis, Rakesh Venkat
The problem of computing the vertex expansion of a graph is an NP-hard problem. The current best worst-case approximation guarantees for computing the vertex expansion of a graph a…
On Euclidean -Means Clustering with -Center Proximity
Amit Deshpande, Anand Louis, Apoorv Vikram Singh
-means clustering is NP-hard in the worst case but previous work has shown efficient algorithms assuming the optimal -means clusters are \emph{stable} under additive or multi…
Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
T-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang +1
The celebrated Cheeger's Inequality establishes a bound on the edge expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on…
Accelerated Newton Iteration: Roots of Black Box Polynomials and Matrix Eigenvalues
Anand Louis, Santosh S. Vempala
We study the problem of computing the largest root of a real rooted polynomial to within error given only black box access to it, i.e., for any $x \in {\mathb…