Anand Louis

AAAI Conference 2026 Conference Paper

Group Fair Matchings Using Convex Cost Functions

• Atasi Panda
• Harsh Sharma
• Anand Louis
• Prajakta Nimbhorkar

We consider the problem of assigning items to platforms where each item has a utility associated with each of the platforms to which it can be assigned. Each platform has a soft constraint over the total number of items it serves, modeled via a convex cost function. Additionally, items are partitioned into groups, and each platform also incurs group-specific convex cost over the number of items from each group that can be assigned to the platform. These costs promote group fairness by penalizing imbalances, yielding a soft variation of fairness notions introduced in prior work, such as Restricted Dominance and Minority protection. Restricted Dominance enforces upper bounds on group representation, while Minority protection enforces lower bounds. Our approach replaces such hard constraints with cost-based penalties, allowing more flexible trade-offs. Our model also captures Nash Social Welfare kind of objective. The cost of an assignment is the sum of the values of all the cost functions across all the groups and platforms. The objective is to find an assignment that minimizes the cost while achieving a total utility that is at least a user-specified threshold. The main challenge lies in balancing the overall platform cost with group-specific costs, both governed by convex functions, while meeting the utility constraint. We present an efficient polynomial-time approximation algorithm, supported by theoretical guarantees and experimental evaluation. Our algorithm is based on techniques involving linear programming and network flows. We also provide an exact algorithm for a special case with uniform utilities and establish the hardness of the general problem when the groups can intersect arbitrarily. This work has applications in cloud computing, logistics, resource-constrained machine learning deployment, federated learning, and network design, where resources must be allocated across platforms with diverse cost structures and diminishing returns.

IJCAI Conference 2024 Conference Paper

Individual Fairness under Group Fairness Constraints 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 ordering over platforms. Each platform enforces group fairness by limiting the number of items per group that can be assigned to it. There could be multiple optimal solutions that satisfy the group fairness constraints, but this alone ignores item preferences. Our approach explores a `best of both worlds fairness' solution to get a randomized matching, which is ex-ante individually fair and ex-post group-fair. Thus, we seek a `probabilistic individually fair' distribution over `group-fair' matchings where each item has a `high' probability of matching to one of its top choices. This distribution is also ex-ante group-fair. Users can customize fairness constraints to suit their requirements. Our first result is a polynomial-time algorithm that computes a distribution over `group-fair' matchings such that the individual fairness constraints are approximately satisfied and the expected size of a matching is close to OPT. We empirically test this on real-world datasets. We present two additional polynomial-time bi-criteria approximation algorithms that users can choose from to balance group fairness and individual fairness trade-offs. For disjoint groups, we provide an exact polynomial-time algorithm adaptable to additional lower `group fairness' bounds. Extending our model, we encompass `maxmin group fairness, ' amplifying underrepresented groups, and `mindom group fairness, ' reducing the representation of dominant groups. '

SODA Conference 2024 Conference Paper

New Approximation Bounds for Small-Set Vertex Expansion

• Suprovat Ghoshal
• Anand Louis

The vertex expansion of graph is a fundamental graph parameter. Given a graph G = ( V, E) and a parameter δ ∈ (0, 1/2], its δ-SSVE is defined as where ∂ V ( S ) is the vertex boundary of a set S. The SSVE problem, in addition to being of independent interest as a natural graph partitioning problem, is also of interest due to its connections to the S trong U- nique G ames problem [16]. We give a randomized algorithm running in time, which outputs a set S of size Θ(δ n ), having vertex expansion at most where d is the largest vertex degree of the graph, and φ * is the optimal δ-SSVE. The previous best known guarantees for this were the bi-criteria bounds of and due to Louis-Makarychev [TOC’16]. Our algorithm uses the basic SDP relaxation of the problem augmented with poly(1/δ) rounds of the Lasserre/SoS hierarchy. Our rounding algorithm is a combination of rounding algorithms of [37, 7]. A key component of our analysis is novel Gaussian rounding lemma for hyperedges which might be of independent interest.

ECAI Conference 2023 Conference Paper

Online Algorithms for Matchings with Proportional Fairness Constraints and Diversity Constraints

• Anand Louis
• Meghana Nasre
• Prajakta Nimbhorkar
• Govind S. Sankar

Matching problems with group-fairness constraints and diversity constraints have numerous applications such as in allocation problems, committee selection, school choice, etc. Moreover, online matching problems have lots of applications in ad allocations and other e-commerce problems like product recommendation in digital marketing. We study two problems involving assigning items to platforms, where items belong to various groups depending on their attributes; the set of items are available offline and the platforms arrive online. In the first problem, we study online matchings with proportional fairness constraints. Here, each platform on arrival should either be assigned a set of items in which the fraction of items from each group is within specified bounds or be assigned no items; the goal is to assign items to platforms in order to maximize the number of items assigned to platforms. In the second problem, we study online matchings with diversity constraints, i. e. for each platform, absolute lower bounds are specified for each group. Each platform on arrival should either be assigned a set of items that satisfy these bounds or be assigned no items; the goal is to maximize the set of platforms that get matched. We study approximation algorithms and hardness results for these problems. The technical core of our proofs is a new connection between these problems and the problem of matchings in hypergraphs. Our experimental evaluation shows the performance of our algorithms on real-world and synthetic datasets exceeds our theoretical guarantees.

IJCAI Conference 2023 Conference Paper

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 randomized group-fair rankings and prove that there exists a unique distribution D that satisfies our axioms and is supported only over ex-post group-fair rankings, i. e. , rankings that satisfy given lower and upper bounds on group-wise representation in the top-k ranks. Our problem formulation works even when there is implicit bias, incomplete relevance information, or only ordinal ranking is available instead of relevance scores or utility values. We propose two algorithms to sample a random group-fair ranking from the distribution D mentioned above. Our first dynamic programming-based algorithm samples ex-post group-fair rankings uniformly at random in time O(k^2 ell), where "ell" is the number of groups. Our second random walk-based algorithm samples ex-post group-fair rankings from a distribution epsilon-close to D in total variation distance and has expected running time O*(k^2 ell^2), when there is a sufficient gap between the given upper and lower bounds on the group-wise representation. The former does exact sampling, but the latter runs significantly faster on real-world data sets for larger values of k. We give empirical evidence that our algorithms compare favorably against recent baselines for fairness and ranking utility on real-world data sets.

UAI Conference 2022 Conference Paper

Robust identifiability in linear structural equation models of causal inference

• Karthik Abinav Sankararaman
• Anand Louis
• Navin Goyal

We consider the problem of robust parameter estimation from observational data in the context of linear structural equation models (LSEMs). Under various conditions on LSEMs and the model parameters the prior work provides efficient algorithms to recover the parameters. However, these results are often about generic identifiability. In practice, generic identifiability is not sufficient and we need robust identifiability: small changes in the observational data should not affect the parameters by a huge amount. Robust identifiability has received far less attention and remains poorly understood. Sankararaman et al. (2019) recently provided a set of sufficient conditions on parameters under which robust identifiability is feasible. However, a limitation of their work is that their results only apply to a small sub-class of LSEMs, called “bow-free paths. ” In this work, we show that for any “bow-free model”, in all but $\frac{1}{\poly(n)}$-measure of instances robust identifiability holds. Moreover, whenever an instance is robustly identifiable, the algorithm proposed in Foygel et al. , (2012) can be used to recover the parameters in a robust fashion. In contrast, for generic identifiability Foygel et al. , (2012) proved that with measure $1$, instances are generically identifiable. Thus, we show that robust identifiability is a strictly harder problem than generic identifiability. Finally, we validate our results on both simulated and real-world datasets.

SODA Conference 2021 Conference Paper

Approximation Algorithms and Hardness for Strong Unique Games

• Suprovat Ghoshal
• Anand Louis

The U nique G ames problem is a central problem in algorithms and complexity theory. Given an instance of U nique G ames, the S trong U nique G ames problem asks to find the largest subset of vertices, such that the U nique G ames instance induced on them is completely satisfiable. In this work, we give new algorithmic and hardness results for the S trong U nique G ames problem. Given an instance with label set size k where a set of 1 – ∊ fraction of the vertices induce an instance that is completely satisfiable, our first algorithm produces a set of fraction of the vertices such that the U nique G ames induced on them is completely satisfiable. In the same setting, our second algorithm produces a set of (here d is the largest vertex degree of the graph) fraction of the vertices such that the U nique G ames induced on them is completely satisfiable. The technical core of our results is a new connection between S trong U nique G ames and small-set vertex-expansion in graphs. Complementing this, assuming the Unique Games conjecture, we prove that there exists an absolute constant C such that it is NP-hard to compute a set of size larger than such that all the constraints induced on this set are satisfied. Given an undirected graph G ( V, E ) the O dd cycle transversal problem, asks to delete the least fraction of vertices to make the induced graph on the remaining vertices bipartite. As a corollary to our main algorithmic results, we obtain an algorithm that outputs a set S such the graph induced on V \ S is bipartite, and (here d is the largest vertex degree and ∊ is the optimal fraction of vertices that need to be deleted). Assuming the Unique Games conjecture, we prove a matching (up to constant factors) hardness.

AAMAS Conference 2021 Conference Paper

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 particular category and has an associated weight and value. The goal of this problem is to select a subset of items such that all categories are fairly represented, the total weight of the selected items does not exceed the capacity of the knapsack, and the total value is maximized. We study the fairness parameters such as the bounds on the total value of items from each category, the total weight of items from each category, and the total number of items from each category. We give approximation algorithms for these problems. We also give experimental validation for the efficiency of our algorithms. These fairness notions could also be extended to the min-knapsack problem. The fair knapsack problems encompass various important problems, such as participatory budgeting, fair budget allocation, and advertising.

IJCAI Conference 2021 Conference Paper

Matchings with Group Fairness Constraints: Online and Offline Algorithms

• Govind S. Sankar
• Anand Louis
• Meghana Nasre
• Prajakta Nimbhorkar

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 paper. Each platform specifies the group fairness constraints through an upper bound on the number of items it can serve from each class. Additionally, each platform also has an upper bound on the total number of items it can serve. The goal is to assign items to platforms so as to maximize the number of items assigned while satisfying the upper bounds of each class. This problem models several important real-world problems like ad-auctions, scheduling, resource allocations, school choice etc. We show that if the classes are arbitrary, then the problem is NP-hard and has a strong inapproximability. We consider the problem in both online and offline settings under natural restrictions on the classes. Under these restrictions, the problem continues to remain NP-hard but admits approximation algorithms with small approximation factors. We also implement some of the algorithms. Our experiments show that the algorithms work well in practice both in terms of efficiency and the number of items that get assigned to some platform.

ICML Conference 2021 Conference Paper

On the Problem of Underranking in Group-Fair Ranking

• Sruthi Gorantla
• Amit Deshpande
• Anand Louis

Bias in ranking systems, especially among the top ranks, can worsen social and economic inequalities, polarize opinions, and reinforce stereotypes. On the other hand, a bias correction for minority groups can cause more harm if perceived as favoring group-fair outcomes over meritocracy. Most group-fair ranking algorithms post-process a given ranking and output a group-fair ranking. In this paper, we formulate the problem of underranking in group-fair rankings based on how close the group-fair rank of each item is to its original rank, and prove a lower bound on the trade-off achievable for simultaneous underranking and group fairness in ranking. We give a fair ranking algorithm that takes any given ranking and outputs another ranking with simultaneous underranking and group fairness guarantees comparable to the lower bound we prove. Our experimental results confirm the theoretical trade-off between underranking and group fairness, and also show that our algorithm achieves the best of both when compared to the state-of-the-art baselines.

NeurIPS Conference 2019 Conference Paper

HyperGCN: A New Method For Training Graph Convolutional Networks on Hypergraphs

• Naganand Yadati
• Madhav Nimishakavi
• Prateek Yadav
• Vikram Nitin
• Anand Louis
• Partha Talukdar

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 and natural modeling tool to model such complex relationships. The obvious existence of such complex relationships in many real-world networks naturaly motivates the problem of learning with hypergraphs. A popular learning paradigm is hypergraph-based semi-supervised learning (SSL) where the goal is to assign labels to initially unlabeled vertices in a hypergraph. Motivated by the fact that a graph convolutional network (GCN) has been effective for graph-based SSL, we propose HyperGCN, a novel GCN for SSL on attributed hypergraphs. Additionally, we show how HyperGCN can be used as a learning-based approach for combinatorial optimisation on NP-hard hypergraph problems. We demonstrate HyperGCN's effectiveness through detailed experimentation on real-world hypergraphs. We have made HyperGCN's source code available to foster reproducible research.

UAI Conference 2019 Conference Paper

Stability of Linear Structural Equation Models of Causal Inference

• Karthik Abinav Sankararaman
• Anand Louis
• Navin Goyal

We consider numerical stability of the parameter recovery problem in Linear Structural Equation Model (LSEM) of causal inference. Numerical stability is essential for the recovered parameters to be reliable. A long line of work starting from Wright (1920) has focused on understanding which sub-classes of LSEM allow for efficient parameter recovery. Despite decades of study, this question is not yet fully resolved. The goal of the present paper is complementary to this line of work: we want to understand the stability of the recovery problem in the cases when efficient recovery is possible. Numerical stability of Pearl’s notion of causality was first studied in Schulman and Srivastava (2016) using the concept of condition number where they provide ill-conditioned examples. In this work, we provide a condition number analysis for the LSEM. First we prove that under a sufficient condition, for a certain sub-class of LSEM that are bow-free (Brito and Pearl (2002)), parameter recovery is numerically stable. We further prove that randomly chosen input parameters for this family satisfy the condition with a substantial probability. Hence for this family, on a large subset of parameter space, recovery is stable. Next we construct an example of LSEM on four vertices with unbounded condition number. We then corroborate our theoretical findings via simulations as well as real-world experiments for a sociology application. Finally, we provide a general heuristic for estimating the condition number of any LSEM instance.

FOCS Conference 2016 Conference Paper

Accelerated Newton Iteration for Roots of Black Box Polynomials

• Anand Louis
• Santosh S. Vempala

We study the problem of computing the largest root of a real rooted polynomial p(x) to within error 'z' given only black box access to it, i. e. , for any x, the algorithm can query an oracle for the value of p(x), but the algorithm is not allowed access to the coefficients of p(x). A folklore result for this problem is that the largest root of a polynomial can be computed in O(n log (1/z)) polynomial queries using the Newton iteration. We give a simple algorithm that queries the oracle at only O(log n log(1/z)) points, where n is the degree of the polynomial. Our algorithm is based on a novel approach for accelerating the Newton method by using higher derivatives.

STOC Conference 2015 Conference Paper

Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

• Anand Louis

The celebrated Cheeger's Inequality [AM85,a86] establishes a bound on the expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on studying the eigenvalues and eigenvectors of the adjacency matrix (and other related matrices) of graphs. It has remained open to define a suitable spectral model for hypergraphs whose spectra can be used to estimate various combinatorial properties of the hypergraph. In this paper we introduce a new hypergraph Laplacian operator generalizing the Laplacian matrix of graphs. Our operator can be viewed as the gradient operator applied to a certain natural quadratic form for hypergraphs. We show that various hypergraph parameters (for e.g. expansion, diameter, etc) can be bounded using this operator's eigenvalues. We study the heat diffusion process associated with this Laplacian operator, and bound its parameters in terms of its spectra. All our results are generalizations of the corresponding results for graphs. We show that there can be no linear operator for hypergraphs whose spectra captures hypergraph expansion in a Cheeger-like manner. Our Laplacian operator is non-linear, and thus computing its eigenvalues exactly is intractable. For any k, we give a polynomial time algorithm to compute an approximation to the kth smallest eigenvalue of the operator. We show that this approximation factor is optimal under the SSE hypothesis (introduced by [RS10]) for constant values of k. Finally, using the factor preserving reduction from vertex expansion in graphs to hypergraph expansion, we show that all our results for hypergraphs extend to vertex expansion in graphs.

SODA Conference 2014 Conference Paper

Approximation Algorithm for Sparsest k -Partitioning

• Anand Louis
• Konstantin Makarychev

Given a graph G, the sparsest-cut problem asks to find the set of vertices S which has the least expansion defined as where w is the total edge weight of a subset. Here we study the natural generalization of this problem: given an integer k, compute a k -partition { P 1, …, P k } of the vertex set so as to minimize Our main result is a polynomial time bi-criteria approximation algorithm which outputs a (1 – ∊ ) k -partition of the vertex set such that each piece has expansion at most times OPT. We also study balanced versions of this problem.

FOCS Conference 2013 Conference Paper

The Complexity of Approximating Vertex Expansion

• Anand Louis
• Prasad Raghavendra
• Santosh S. Vempala

We study the complexity of approximating the vertex expansion of graphs G = (V, E), defined as Φ V def = minSCV n. |N(S)|/(|S||V\S). We give a simple polynomialtime algorithm for finding a subset with vertex expansion O(√(Φ V log d)) where d is the maximum degree of the graph. Our main result is an asymptotically matching lower bound: under the Small Set Expansion (SSE) hypothesis, it is hard to find a subset with expansion less than C(√(Φ V log d)) for an absolute constant C. In particular, this implies for all constant ε > 0, it is SSE-hard to distinguish whether the vertex expansion <; ε or at least an absolute constant. The analogous threshold for edge expansion is √Φ with no dependence on the degree (Here Φ denotes the optimal edge expansion). Thus our results suggest that vertex expansion is harder to approximate than edge expansion. In particular, while Cheeger's algorithm can certify constant edge expansion, it is SSE-hard to certify constant vertex expansion in graphs.

STOC Conference 2012 Conference Paper

Many sparse cuts via higher eigenvalues

• Anand Louis
• Prasad Raghavendra
• Prasad Tetali
• Santosh S. Vempala