John Dunagan

IJCAI Conference 2011 Conference Paper

Active Graph Reachability Reduction for Network Security and Software Engineering

• Alice X. Zheng
• John Dunagan
• Ashish Kapoor

Motivated by applications from computer network security and software engineering, we study the problem of reducing reachability on a graph with unknown edge costs. When the costs are known, reachability reduction can be solved using a linear relaxation of sparsest cut. Problems arise, however, when edge costs are unknown. In this case, blindly applying sparsest cut with incorrect edge costs can result in suboptimal or infeasible solutions. Instead, we propose to solve the problem via edge classification using feedback on individual edges. We show that this approach outperforms competing approaches in accuracy and efficiency on our target applications.

STOC Conference 2007 Conference Paper

Iteratively constructing preconditioners via the conjugate gradient method

• John Dunagan
• Nicholas J. A. Harvey

We consider the problem of solving a symmetric, positive definite system of linear equations.The most well-known and widely-used method for solving such systemsis the preconditioned Conjugate Gradient method.The performance of this method depends crucially on knowing a good preconditioner matrix.We show that the Conjugate Gradient method itself canproduce good preconditioners as a by-product. These preconditioners allow us to derive new asymptotic bounds on the timeto solve multiple related linear systems.

STOC Conference 2004 Conference Paper

A simple polynomial-time rescaling algorithm for solving linear programs

• John Dunagan
• Santosh S. Vempala

The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function. ). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm with periodic rescaling runs in polynomial-time. The resulting algorithm for linear programming has an elementary description and analysis.

SODA Conference 2002 Conference Paper

Smoothed analysis of the perceptron algorithm for linear programming

• Avrim Blum
• John Dunagan

STOC Conference 2001 Conference Paper

Optimal outlier removal in high-dimensional

• John Dunagan
• Santosh S. Vempala

We study the problem of finding an outlier-free subset of a set of points (or a probability distribution) in n -dimensional Euclidean space. A point x is defined to be a β-outlier if there exists some direction w in which its squared distance from the mean along w is greater than β times the average squared distance from the mean along w [1]. Our main theorem is that for any ε>0, there exists a (1-ε) fraction of the original distribution that has no O (\frac{ n }{ε}( b +log \frac{ n }{ε))-outliers, improving on the previous bound of O(n ^7 b /ε). This bound is shown to be nearly the best possible. The theorem is constructive, and results in a \frac{1}{1-ε} approximation to the following optimization problem: given a distribution μ (i.e. the ability to sample from it), and a parameter ε>0, find the minimum β for which there exists a subset of probability at least (1-ε) with no β-outliers.