Ravi Sundaram

ICML Conference 2025 Conference Paper

Optimal Fair Learning Robust to Adversarial Distribution Shift

• Sushant Agarwal
• Amit Deshpande 0001
• Rajmohan Rajaraman
• Ravi Sundaram

Previous work in fair machine learning has characterised the Fair Bayes Optimal Classifier (BOC) on a given distribution for both deterministic and randomized classifiers. We study the robustness of the Fair BOC to adversarial noise in the data distribution. Kearns & Li (1988) implies that the accuracy of the deterministic BOC without any fairness constraints is robust (Lipschitz) to malicious noise in the data distribution. We demonstrate that their robustness guarantee breaks down when we add fairness constraints. Hence, we consider the randomized Fair BOC, and our central result is that its accuracy is robust to malicious noise in the data distribution. Our robustness result applies to various fairness constraints—Demographic Parity, Equal Opportunity, Predictive Equality. Beyond robustness, we demonstrate that randomization leads to better accuracy and efficiency. We show that the randomized Fair BOC is nearly-deterministic, and gives randomized predictions on at most one data point, hence availing numerous benefits of randomness, while using very little of it.

AAAI Conference 2025 Conference Paper

Sample Complexity of Linear Regression Models for Opinion Formation in Networks

• Haolin Liu
• Rajmohan Rajaraman
• Ravi Sundaram
• Anil Kumar Vullikanti
• Omer Wasim
• Haifeng Xu

Consider public health officials aiming to spread awareness about a new vaccine in a community interconnected by a social network. How can they distribute information with minimal resources, so as to avoid polarization and ensure community-wide convergence of opinion? To tackle such challenges, we initiate the study of sample complexity of opinion formation in networks. Our framework is built on the recognized opinion formation game, where we regard each agent’s opinion as a data-derived model, unlike previous works that treat opinions as data-independent scalars. The opinion model for every agent is initially learned from its local samples and evolves game-theoretically as all agents communicate with neighbors and revise their models towards an equilibrium. Our focus is on the sample complexity needed to ensure that the opinions converge to an equilibrium such that every agent’s final model has low generalization error. Our paper has two main technical results. First, we present a novel polynomial time optimization framework to quantify the total sample complexity for arbitrary networks, when the underlying learning problem is (generalized) linear regression. Second, we leverage this optimization to study the network gain which measures the improvement of sample complexity when learning over a network compared to that in isolation. Towards this end, we derive network gain bounds for various network classes including cliques, star graphs, and random regular graphs. Additionally, our framework provides a method to study sample distribution within the network, suggesting that it is sufficient to allocate samples inversely to the degree. Empirical results on both synthetic and real-world networks strongly support our theoretical findings.

JMLR Journal 2023 Journal Article

PAC-learning for Strategic Classification

• Ravi Sundaram
• Anil Vullikanti
• Haifeng Xu
• Fan Yao

The study of strategic or adversarial manipulation of testing data to fool a classifier has attracted much recent attention. Most previous works have focused on two extreme situations where any testing data point either is completely adversarial or always equally prefers the positive label. In this paper, we generalize both of these through a unified framework by considering strategic agents with heterogenous preferences, and introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. SVC provably generalizes the recent concept of adversarial VC-dimension (AVC) introduced by Cullina et al. (2018). We instantiate our framework for the fundamental strategic linear classification problem. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) its computational tractability by pinning down the complexity of the empirical risk minimization problem. Interestingly, the SVC of linear classifiers is always upper bounded by its standard VC-dimension. This characterization also strictly generalizes the AVC bound for linear classifiers in (Cullina et al., 2018). Finally, we briefly investigate the power of randomization in our strategic classification setup. We show that randomization may strictly increase the accuracy in general, but will not help in the special case of adversarial classification with zero-manipulation-cost. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

ICML Conference 2021 Conference Paper

PAC-Learning for Strategic Classification

• Ravi Sundaram
• V. S. Anil Kumar 0001
• Haifeng Xu
• Fan Yao 0002

The study of strategic or adversarial manipulation of testing data to fool a classifier has attracted much recent attention. Most previous works have focused on two extreme situations where any testing data point either is completely adversarial or always equally prefers the positive label. In this paper, we generalize both of these through a unified framework for strategic classification and introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. SVC provably generalizes the recent concept of adversarial VC-dimension (AVC) introduced by Cullina et al. (2018). We instantiate our framework for the fundamental strategic linear classification problem. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) it’s computational tractability by pinning down the complexity of the empirical risk minimization problem. Interestingly, the SVC of linear classifiers is always upper bounded by its standard VC-dimension. This characterization also strictly generalizes the AVC bound for linear classifiers in (Cullina et al. , 2018).

TCS Journal 2021 Journal Article

Realization problems on reachability sequences

• Matthew Dippel
• Ravi Sundaram
• Akshar Varma

The classical Erdös-Gallai theorem (1960) kicked off the study of graph realizability by characterizing degree sequences. We extend this line of research by investigating realizability of directed acyclic graphs (DAGs) given a sequence of tuples each containing multiple node properties including the degree, reachability value (number of nodes reachable from a given node), depth and height of a node. The most interesting problems are when the sequences contain both a local constraint via degree values and a global constraint via reachability values. We show that, without degree constraints, DAG reachability realization is solvable in linear time, whereas it is strongly NP-complete given upper bounds on in-degree or out-degree. After defining a suitable notion of bicriteria approximation based on consistency, we give two approximation algorithms achieving O ( log ⁡ n ) -reachability consistency and O ( log ⁡ n ) -degree consistency; the first, randomized, uses LP (Linear Program) rounding, while the second, deterministic, employs a k-set packing heuristic. We end with some future directions of research and a set of conjectures that we hope will motivate further study of realizability with reachability constraints.

SODA Conference 2016 Conference Paper

Markovian Hitters and the Complexity of Blind Rendezvous

• Sixia Chen
• Matthew Dippel
• Alexander Russell
• Abhishek Samanta
• Ravi Sundaram

We define and construct a novel pseudorandom tool, the Markovian hitter. Given an input sequence of n independent random bits, a Markovian hitter produces a sequence of pseudorandom samples in {0, 1} k, in an online fashion, that hits any subset W ⊂ {0, 1} k of size ∊2 k with probability ≈ 1 – 2 –( n – k )∊. This is comparable to the behavior of truly random samples or classical pseudorandom hitting sets. A Markovian hitter has an additional “Markovian” property of interest: each pseudorandom sample is a function of only the O ( k ) most recent bits of the input sequence (of random bits). Such Markovian properties are useful in distributed online settings. In particular, we apply Markovian hitters to obtain a new algorithm for the well-studied blind rendezvous problem for cognitive radios. This is the problem faced by two parties equipped with radios that can access channels in potentially different subsets, S 1 and S 2, of a universe of n channels. Their challenge is to discover each other (by tuning their radios to the same channel at the same time) as quickly as possible. In prior work [3] it was shown that deterministic schedules have a lower bound for rendezvous time of Ω(| S 1 | · | S 2 |). We beat this quadratic barrier by utilizing a public source of randomness in conjunction with a Markovian hitter to achieve rendezvous in expected time We counterbalance this result by establishing two lower bounds on expected rendezvous time: an bound for the setting with public randomness, and an Ω(| S 1 | · | S 2 |) bound in the setting with private randomness but no public randomness, which is a strengthening of the result for deterministic schedules.

AAAI Conference 2015 Conference Paper

SmartShift: Expanded Load Shifting Incentive Mechanism for Risk-Averse Consumers

• Bochao Shen
• Balakrishnan Narayanaswamy
• Ravi Sundaram

Peak demand for electricity continues to surge around the world. The supply-demand imbalance manifests itself in many forms, from rolling brownouts in California to power cuts in India. It is often suggested that exposing consumers to real-time pricing, will incentivize them to change their usage and mitigate the problem - akin to increasing tolls at peak commute times. We show that risk-averse consumers of electricity react to price fluctuations by scaling back on their total demand, not just their peak demand, leading to the unintended consequence of an overall decrease in production/consumption and reduced economic efficiency. We propose a new scheme that allows homes to move their demands from peak hours in exchange for greater electricity consumption in non-peak hours - akin to how airlines incentivize a passenger to move from an over-booked flight in exchange for, say, two tickets in the future. We present a formal framework for the incentive model that is applicable to different forms of the electricity market. We show that our scheme not only enables increased consumption and consumer social welfare but also allows the distribution company to increase profits. This is achieved by allowing load to be shifted while insulating consumers from real-time price fluctuations. This win-win is important if these methods are to be embraced in practice.

UAI Conference 2014 Conference Paper

Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints

• Daniel J. Rosenkrantz
• Madhav V. Marathe
• Ravi Sundaram
• V. S. Anil Kumar 0001

We present new polynomial time algorithms for inference problems in Bayesian networks (BNs) when restricted to instances that satisfy the following two conditions: they have bounded treewidth and the conditional probability table (CPT) at each node is specified concisely using an r-symmetric function for some constant r. Our polynomial time algorithms work directly on the unmoralized graph. Our results significantly extend known results regarding inference problems on treewidth bounded BNs to a larger class of problem instances. We also show that relaxing either of the conditions used by our algorithms leads to computational intractability.

FOCS Conference 2009 Conference Paper

Reducibility among Fractional Stability Problems

• Shiva Kintali
• Laura J. Poplawski
• Rajmohan Rajaraman
• Ravi Sundaram
• Shang-Hua Teng

In a landmark paper, Papadimitriou introduced a number of syntactic subclasses of TFNP based on proof styles that (unlike TFNP) admit complete problems. A recent series of results has shown that finding Nash equilibria is complete for PPAD, a particularly notable subclass of TFNP. A major goal of this work is to expand the universe of known PPAD-complete problems. We resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be PPAD-complete, along with the domains of practical significance: Fractional Stable Paths Problem (FSPP) - Internet routing; Core of Balanced Games - Economics and Game theory; Scarf's Lemma - Combinatorics; Hypergraph Matching - Social Choice and Preference Systems; Fractional Bounded Budget Connection Games (FBBC) - Social networks; and Strong Fractional Kernel - Graph Theory. In fact, we show that no fully polynomial-time approximation schemes exist (unless PPAD is in FP). This paper is entirely a series of reductions that build in nontrivial ways on the framework established in previous work. In the course of deriving these reductions, we created two new concepts - preference games and personalized equilibria. The entire set of new reductions can be presented as a lattice with the above problems sandwiched between preference games (at the "easy" end) and personalized equilibria (at the "hard" end). Our completeness results extend to natural approximate versions of most of these problems. On a technical note, we wish to highlight our novel "continuous-to-discrete" reduction from exact personalized equilibria to approximate personalized equilibria using a linear program augmented with an exponential number of "min" constraints of a specific form. In addition to enhancing our repertoire of PPAD-complete problems, we expect the concepts and techniques in this paper to find future use in algorithmic game theory.

STOC Conference 2005 Conference Paper

Universal approximations for TSP, Steiner tree, and set cover

• Lujun Jia
• Guolong Lin
• Guevara Noubir
• Rajmohan Rajaraman
• Ravi Sundaram

STOC Conference 2004 Conference Paper

(Almost) tight bounds and existence theorems for confluent flows

• Jiangzhuo Chen
• Robert Kleinberg
• László Lovász 0001
• Rajmohan Rajaraman
• Ravi Sundaram
• Adrian Vetta

A flow is said to be confluent if at any node all the flow leaves along a single edge. Given a directed graph G with k sinks and non-negative demands on all the nodes of G , we consider the problem of determining a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized. Confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the Internet are confluent since Internet routing is destination based.We present near-tight approximation algorithms, hardness results, and existence theorems for confluent flows. The main result of this paper is a polynomial-time algorithm for determining a confluent flow with congestion at most 1 + ln( k ) in G , if G admits a splittable flow with congestion at most 1. We complement this result in two directions. First, we present a graph G that admits a splittable flow with congestion at most 1, yet no confluent flow with congestion smaller than H k , thus establishing tight upper and lower bounds to within an additive constant less than 1. Second, we show that it is NP-hard to approximate the congestion of an optimal confluent flow to within a factor of (lg k )/2, thus resolving the polynomial-time approximability to within a multiplicative constant. We also consider a demand maximization version of the problem. We show that if G admits a splittable flow of congestion at most 1, then a variant of the congestion minimization algorithm yields a confluent flow in G with congestion at most 1 that satisfies 1/3 fraction of total demand.We show that the gap between confluent flows and splittable flows is much smaller, if the underlying graph were k connected. In particular, we prove that k -connected graphs with k sinks admit confluent flows of congestion less than C + d max , where C is the congestion of the best splittable flow, and d max is the maximum demand of any node in G . The proof of this existence theorem is non-constructive and relies on topological techniques introduced in [16].

STOC Conference 2003 Conference Paper

Meet and merge: approximation algorithms for confluent flows

• Jiangzhuo Chen
• Rajmohan Rajaraman
• Ravi Sundaram

In this paper we investigate the problem ofdetermining confluent flows with minimum congestion. A flow of a given commodity is said to be confluent if at any node all the flow of the commodity departs along a single edge. Confluent flows appear in a variety of application areas ranging from wireless communications to evacuations; in fact, most flows in the Internet are confluent since Internet routing is destination based.We consider the single commodity confluent flow problem, in which we are given an n-node directed network G, a sink t and supplies at each node, and the goal is to find a confluent flow that routes all the supplies to the sink while minimizing the maximum edge congestion. Our main result is an approximation algorithm, based on randomized rounding, for the special case when all the supplies are uniform; the algorithm finds a confluent flow with edge congestion O(C 2 log 3 n) where C is the node congestion of an optimal splittable flow. This implies an Õ(√n) approximation algorithm for the problem. Our result relies on the analysis of a natural probabilistic process defined on directed acyclic graphs, that may be of independent interest.For tree networks, we present an optimal polynomial-time algorithm for a multi-sink generalization of the above confluent flow problem. We show that it is NP-hard to approximate the congestion of the optimal confluent flow for general networks to within a factor of 4/3. We also establish a lower bound on the gap between confluent and splittable flows, and consider multicommodity and fractional versions of confluent flow problems.

SODA Conference 1994 Conference Paper

Spanning Trees Short or Small

• R. Ravi 0001
• Ravi Sundaram
• Madhav V. Marathe
• Daniel J. Rosenkrantz
• S. S. Ravi

TCS Journal 1993 Journal Article

Optimal path cover problem on block graphs and bipartite permutation graphs

• R. Srikant
• Ravi Sundaram
• Karan Sher Singh
• C. Pandu Rangan

The optimal path cover problem is to find a minimum number of vertex disjoint paths which together cover all the vertices of the graph. In this paper, we present linear-time algorithms for the optimal path cover problem for the class of block graphs and bipartite permutation graphs.