16 papers
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…
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…