Result page:
**1**
2
3
4
5

1

A new approach to computing maximum flows using electrical flows

Yin Tat Lee,
Satish Rao,
Nikhil Srivastava

June 2013
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of computing

**Publisher:** ACM

**Bibliometrics**:

Citation Count: 6

Downloads (6 Weeks): 6, Downloads (12 Months): 53, Downloads (Overall): 336

Full text available:

PDF

We give an algorithm which computes a (1-ε)-approximately maximum st-flow in an undirected uncapacitated graph in time O(1/ε√m/F⋅ m log 2 n) where F is the flow value. By trading this off against the Karger-Levine algorithm for undirected graphs which takes ~O(m+nF) time, we obtain a running time of ~O(m ...

**Keywords**:
electrical flow, maximum flow, nesterov, minimum cut

2

Query strategies for evading convex-inducing classifiers

May 2012
The Journal of Machine Learning Research: Volume 13, 3/1/2012

**Publisher:** JMLR.org

**Bibliometrics**:

Citation Count: 15

Downloads (6 Weeks): 1, Downloads (12 Months): 7, Downloads (Overall): 66

Full text available:

PDF

Classifiers are often used to detect miscreant activities. We study how an adversary can systematically query a classifier to elicit information that allows the attacker to evade detection while incurring a near-minimal cost of modifying their intended malfeasance. We generalize the theory of Lowd and Meek (2005) to the family ...

**Keywords**:
reverse engineering, query algorithms, evasion, adversarial learning

Also published in:

January 2012
The Journal of Machine Learning Research: Volume 13 Issue 1, January 2012

3

Quartets MaxCut: A Divide and Conquer Quartets Algorithm

Sagi Snir,
Satish Rao

October 2010
IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB): Volume 7 Issue 4, October 2010

**Publisher:** IEEE Computer Society Press

**Bibliometrics**:

Citation Count: 12

Downloads (6 Weeks): 1, Downloads (12 Months): 10, Downloads (Overall): 124

Full text available:

PDF

Accurate phylogenetic reconstruction methods are currently limited to a maximum of few dozens of taxa. Supertree methods construct a large tree over a large set of taxa, from a set of small trees over overlapping subsets of the complete taxa set. Hence, in order to construct the tree of life ...

**Keywords**:
Phylogenetic reconstruction, quartets, MaxCut, supertree.

4

ℓ22 Spreading Metrics for Vertex Ordering Problems

April 2010
Algorithmica: Volume 56 Issue 4, April 2010

**Publisher:** Springer-Verlag New York, Inc.

We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of $O(\sqrt{\log n}\log\log n)$ , $O(\sqrt{\log n}\log\log n)$ , and $O(\sqrt{\log T}\log\log T)$ , respectively, the last running in time polynomial in T (T being the sum ...

**Keywords**:
Approximation algorithm, Minimum storage-time product, Minimum linear arrangement, Semidefinite programming, Vertex ordering problem, Minimum containing interval graph

5

Eigenvalue bounds, spectral partitioning, and metrical deformations via flows

Punyashloka Biswal,
James R. Lee,
Satish Rao

March 2010
Journal of the ACM (JACM): Volume 57 Issue 3, March 2010

**Publisher:** ACM

**Bibliometrics**:

Citation Count: 9

Downloads (6 Weeks): 3, Downloads (12 Months): 33, Downloads (Overall): 601

Full text available:

PDF

We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric into Euclidean space to recover a bound on the Rayleigh quotient. Using this, we show that every ...

**Keywords**:
network flows, spectral graph theory, Metric embeddings

6

*ℓ* _{2}^{2} Spreading Metrics for Vertex Ordering Problems

January 2010
Algorithmica: Volume 56 Issue 4, April 2010

**Publisher:** Springer-Verlag New York, Inc.

We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement , Minimum Containing Interval Graph , and Minimum Storage-Time Product , achieving approximation factors of $O(\sqrt{\log n}\log\log n)$, $O(\sqrt{\log n}\log\log n)$, and $O(\sqrt{\log T}\log\log T)$, respectively, the last running in time polynomial in T ( T being the ...

**Keywords**:
Semidefinite programming, Vertex ordering problem, Minimum containing interval graph, Approximation algorithm, Minimum storage-time product, Minimum linear arrangement

7

Edge Disjoint Paths in Moderately Connected Graphs

Satish Rao,
Shuheng Zhou

January 2010
SIAM Journal on Computing: Volume 39 Issue 5, January 2010

**Publisher:** Society for Industrial and Applied Mathematics

We study the edge disjoint paths (EDP) problem in undirected graphs: Given a graph $G$ with $n$ nodes and a set $\mathcal{T}$ of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a variety of classic NP-complete problems, for ...

**Keywords**:
polylogarithmic approximation, edge disjoint paths, random sampling in cuts

8

Edge Disjoint Paths in Moderately Connected Graphs

Satish Rao,
Shuheng Zhou

January 2010
SIAM Journal on Computing: Volume 39 Issue 5, January 2010

**Publisher:** Society for Industrial and Applied Mathematics

We study the edge disjoint paths (EDP) problem in undirected graphs: Given a graph $G$ with $n$ nodes and a set $\mathcal{T}$ of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a variety of classic NP-complete problems, for ...

**Keywords**:
edge disjoint paths, random sampling in cuts, polylogarithmic approximation

9

ANTIDOTE: understanding and defending against poisoning of anomaly detectors

November 2009
IMC '09: Proceedings of the 9th ACM SIGCOMM conference on Internet measurement

**Publisher:** ACM

**Bibliometrics**:

Citation Count: 32

Downloads (6 Weeks): 11, Downloads (12 Months): 60, Downloads (Overall): 612

Full text available:

PDF

Statistical machine learning techniques have recently garnered increased popularity as a means to improve network design and security. For intrusion detection, such methods build a model for normal behavior from training data and detect attacks as deviations from that model. This process invites adversaries to manipulate the training data so ...

**Keywords**:
network traffic analysis, adversarial learning, principal components analysis, robust statistics

10

Stealthy poisoning attacks on PCA-based anomaly detectors

October 2009
ACM SIGMETRICS Performance Evaluation Review: Volume 37 Issue 2, September 2009

**Publisher:** ACM

**Bibliometrics**:

Citation Count: 4

Downloads (6 Weeks): 6, Downloads (12 Months): 28, Downloads (Overall): 177

Full text available:

PDF

We consider systems that use PCA-based detectors obtained from a comprehensive view of the network's traffic to identify anomalies in backbone networks. To assess these detectors' susceptibility to adversaries wishing to evade detection, we present and evaluate short-term and long-term data poisoning schemes that trade-off between poisoning duration and the ...

**Keywords**:
adversarial learning, principal components analysis, network traffic analysis

11

A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids

October 2009
Theoretical Computer Science: Volume 410 Issue 44, October, 2009

**Publisher:** Elsevier Science Publishers Ltd.

In the minimum-degree minimum spanning tree (MDMST) problem, we are given a graph G, and the goal is to find a minimum spanning tree (MST) T, such that the maximum degree of T is as small as possible. This problem is NP-hard and generalizes the Hamiltonian path problem. We give ...

**Keywords**:
Approximation algorithms, Push-relabel, Degree-bounded network design, Spanning trees

12

Graph partitioning using single commodity flows

July 2009
Journal of the ACM (JACM): Volume 56 Issue 4, June 2009

**Publisher:** ACM

**Bibliometrics**:

Citation Count: 21

Downloads (6 Weeks): 12, Downloads (12 Months): 64, Downloads (Overall): 1,043

Full text available:

PDF

We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O (log 2 n ) factor in Õ( m + n 3/2 ) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time Õ( m ...

**Keywords**:
spectral method, sparse cut, Edge-separator, single commodity max-flow

13

What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs

May 2009
Algorithmica: Volume 55 Issue 1, May 2009

**Publisher:** Springer-Verlag New York, Inc.

Given a graph and degree upper bounds on vertices, the BDMST problem requires us to find a minimum cost spanning tree respecting the given degree bounds. This problem generalizes the Travelling Salesman Path Problem (TSPP), even in unweighted graphs, and so we expect that it is necessary to relax the ...

**Keywords**:
Combinatorial optimization, Matching, Minimum spanning trees, Approximation algorithms

14

Expander flows, geometric embeddings and graph partitioning

Sanjeev Arora,
Satish Rao,
Umesh Vazirani

April 2009
Journal of the ACM (JACM): Volume 56 Issue 2, April 2009

**Publisher:** ACM

**Bibliometrics**:

Citation Count: 81

Downloads (6 Weeks): 22, Downloads (12 Months): 157, Downloads (Overall): 2,139

Full text available:

PDF

We give a O (&sqrt;log n )-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves the O (log n )-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem ...

**Keywords**:
Graph partitioning, graph separators, semidefinite programs, expanders, expansion, multicommodity flows

15

Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows

Punyashloka Biswal,
James R. Lee,
Satish Rao

October 2008
FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science

**Publisher:** IEEE Computer Society

We present a new methodfor upper bounding the second eigenvalue of theLaplacian of graphs.Our approach uses multi-commodity flows to deform the geometry of the graph;we embed the resulting metric into Euclidean spaceto recover a bound on the Rayleigh quotient.Using this, we show that every $n$-vertexgraphof genus $g$ and maximum degree ...

16

Geometry, flows, and graph-partitioning algorithms

Sanjeev Arora,
Satish Rao,
Umesh Vazirani

October 2008
Communications of the ACM: Volume 51 Issue 10, October 2008

**Publisher:** ACM

**Bibliometrics**:

Citation Count: 6

Downloads (6 Weeks): 12, Downloads (12 Months): 66, Downloads (Overall): 1,341

Full text available:

Html

PDF

17

The *k*-traveling repairmen problem

Jittat Fakcharoenphol,
Chris Harrelson,
Satish Rao

November 2007
ACM Transactions on Algorithms (TALG): Volume 3 Issue 4, November 2007

**Publisher:** ACM

**Bibliometrics**:

Citation Count: 8

Downloads (6 Weeks): 12, Downloads (12 Months): 54, Downloads (Overall): 858

Full text available:

PDF

We consider the k -traveling repairmen problem, also known as the minimum latency problem, to multiple repairmen. We give a polynomial-time 8.497α-approximation algorithm for this generalization, where α denotes the best achievable approximation factor for the problem of finding the least-cost rooted tree spanning i vertices of a metric. For ...

**Keywords**:
vehicle routing, Traveling salesman

18

A Nearly Linear-Time Approximation Scheme for the Euclidean $k$-Median Problem

Stavros G. Kolliopoulos,
Satish Rao

June 2007
SIAM Journal on Computing: Volume 37 Issue 3, June 2007

**Publisher:** Society for Industrial and Applied Mathematics

This paper provides a randomized approximation scheme for the $k$-median problem when the input points lie in the $d$-dimensional Euclidean space. The worst-case running time is $O(2^{O((\log(1/\epsilon) / \varepsilon)^{d-1})} n \log^{d+6} n ),$ which is nearly linear for any fixed $\varepsilon$ and $d$. Moreover, our method provides the first polynomial-time ...

**Keywords**:
$k$-median, Euclidean space, approximation algorithms, approximation schemes, facility location, linear time

19

An efficient and accurate graph-based approach to detect population substructure

April 2007
RECOMB'07: Proceedings of the 11th annual international conference on Research in computational molecular biology

**Publisher:** Springer-Verlag

Currently, large-scale projects are underway to perform whole genome disease association studies. Such studies involve the genotyping of hundreds of thousands of SNP markers. One of the main obstacles in performing such studies is that the underlying population substructure could artificially inflate the p -values, thereby generating a lot of ...

20

A rigorous analysis of population stratification with limited data

January 2007
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

**Publisher:** Society for Industrial and Applied Mathematics

**Bibliometrics**:

Citation Count: 4

Downloads (6 Weeks): 2, Downloads (12 Months): 5, Downloads (Overall): 178

Full text available:

PDF

Finding the genetic factors of complex diseases such as cancer, currently a major effort of the international community, will potentially lead to better treatment of these diseases. One of the major difficulties in these studies, is the fact that the genetic components of an individual not only depend on the ...