@conference {12435,
	title = {Blurring-invariant Riemannian metrics for comparing signals and images},
	booktitle = {2011 IEEE International Conference on Computer Vision (ICCV)},
	year = {2011},
	month = {2011/11/06/13},
	pages = {1770 - 1775},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We propose a novel Riemannian framework for comparing signals and images in a manner that is invariant to their levels of blur. This framework uses a log-Fourier representation of signals/images in which the set of all possible Gaussian blurs of a signal, i.e. its orbits under semigroup action of Gaussian blur functions, is a straight line. Using a set of Riemannian metrics under which the group actions are by isometries, the orbits are compared via distances between orbits. We demonstrate this framework using a number of experimental results involving 1D signals and 2D images.},
	keywords = {blurring-invariant Riemannian metrics, Estimation, Fourier transforms, Gaussian blur function, Gaussian processes, image representation, log-Fourier representation, measurement, Orbits, Polynomials, signal representation, Space vehicles, vectors},
	isbn = {978-1-4577-1101-5},
	doi = {10.1109/ICCV.2011.6126442},
	author = {Zhengwu Zhang and Klassen, E. and Srivastava, A. and Turaga,P. and Chellapa, Rama}
}
@conference {13383,
	title = {Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems},
	booktitle = {2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)},
	year = {2011},
	month = {2011/10/22/25},
	pages = {797 - 806},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input dataset are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, and minimum weight matchings over probabilistic graphs, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of risk averse or risk-prone behaviors, and instead we consider a more general objective which is to maximize the expected utility of the solution for some given utility function, rather than the expected weight (expected weight becomes a special case). We show that we can obtain a polynomial time approximation algorithm with additive error ϵ for any ϵ >; 0, if there is a pseudopolynomial time algorithm for the exact version of the problem (This is true for the problems mentioned above) and the maximum value of the utility function is bounded by a constant. Our result generalizes several prior results on stochastic shortest path, stochastic spanning tree, and stochastic knapsack. Our algorithm for utility maximization makes use of the separability of exponential utility and a technique to decompose a general utility function into exponential utility functions, which may be useful in other stochastic optimization problems.},
	keywords = {Approximation algorithms, Approximation methods, combinatorial problems, Fourier series, knapsack problems, optimisation, OPTIMIZATION, polynomial approximation, polynomial time approximation algorithm, Polynomials, Random variables, stochastic combinatorial optimization, stochastic knapsack, stochastic shortest path, stochastic spanning tree, vectors},
	isbn = {978-1-4577-1843-4},
	doi = {10.1109/FOCS.2011.33},
	author = {Li,Jian and Deshpande, Amol}
}
@conference {17633,
	title = {New Constructive Aspects of the Lovasz Local Lemma},
	booktitle = {2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
	year = {2010},
	month = {2010/10/23/26},
	pages = {397 - 406},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {The Lov{\textquoteright}{a}sz Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of {\textquoteleft}{\textquoteleft}bad{\textquoteright}{\textquoteright} events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser \& Tardos. We show that the output distribution of the Moser-Tardos algorithm well-approximates the emph{conditional LLL-distribution} {\textendash} the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and non-constructive results. We also show that when an LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized {\textquoteleft}{\textquoteleft}core{\textquoteright}{\textquoteright} subset of bad events leads to a desired outcome with high probability. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making an LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. In all these applications the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known. As a second type of application we consider settings beyond the critical dependency threshold of the LLL: - - avoiding all bad events is impossible in these cases. As the first (even non-constructive) result of this kind, we show that by sampling from the LLL-distribution of a selected smaller core, we can avoid a fraction of bad events that is higher than the expectation. MAX $k$-SAT is an example of this.},
	keywords = {acyclic edge coloring, Algorithm design and analysis, Approximation algorithms, Approximation methods, computational complexity, Computer science, constant factor approximation algorithm, graph colouring, Linearity, Lovasz Local Lemma, MAX k-SAT, Monte Carlo Algorithm, Monte Carlo methods, Moser-Tardos algorithm, nonrepetitive graph coloring, output distribution, polynomial sized core subset, Polynomials, Probabilistc Method, probabilistic analysis, probabilistic logic, probability, Ramsey type graph, Sampling methods, Santa Claus Problem},
	isbn = {978-1-4244-8525-3},
	doi = {10.1109/FOCS.2010.45},
	author = {Haeupler,B. and Saha,B. and Srinivasan, Aravind}
}
@conference {13385,
	title = {Minimizing Communication Cost in Distributed Multi-query Processing},
	booktitle = {IEEE 25th International Conference on Data Engineering, 2009. ICDE {\textquoteright}09},
	year = {2009},
	month = {2009/04/29/March},
	pages = {772 - 783},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Increasing prevalence of large-scale distributed monitoring and computing environments such as sensor networks, scientific federations, Grids etc., has led to a renewed interest in the area of distributed query processing and optimization. In this paper we address a general, distributed multi-query processing problem motivated by the need to minimize the communication cost in these environments. Specifically we address the problem of optimally sharing data movement across the communication edges in a distributed communication network given a set of overlapping queries and query plans for them (specifying the operations to be executed). Most of the problem variations of our general problem can be shown to be NP-Hard by a reduction from the Steiner tree problem. However, we show that the problem can be solved optimally if the communication network is a tree, and present a novel algorithm for finding an optimal data movement plan. For general communication networks, we present efficient approximation algorithms for several variations of the problem. Finally, we present an experimental study over synthetic datasets showing both the need for exploiting the sharing of data movement and the effectiveness of our algorithms at finding such plans.},
	keywords = {Approximation algorithms, Communication networks, Computer science, Cost function, Data engineering, distributed communication network, distributed databases, distributed multi-query processing, grid computing, Large-scale systems, NP-hard, optimisation, Polynomials, Publish-subscribe, publish-subscribe systems, Query optimization, Query processing, sensor networks, Steiner tree problem, Tree graphs, trees (mathematics)},
	isbn = {978-1-4244-3422-0},
	doi = {10.1109/ICDE.2009.85},
	author = {Li,Jian and Deshpande, Amol and Khuller, Samir}
}
@conference {13389,
	title = {Network-Aware Join Processing in Global-Scale Database Federations},
	booktitle = {IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008},
	year = {2008},
	month = {2008/04/07/12},
	pages = {586 - 595},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We introduce join scheduling algorithms that employ a balanced network utilization metric to optimize the use of all network paths in a global-scale database federation. This metric allows algorithms to exploit excess capacity in the network, while avoiding narrow, long-haul paths. We give a two- approximate, polynomial-time algorithm for serial (left-deep) join schedules. We also present extensions to this algorithm that explore parallel schedules, reduce resource usage, and define tradeoffs between computation and network utilization. We evaluate these techniques within the SkyQuery federation of Astronomy databases using spatial-join queries submitted by SkyQuery{\textquoteright}s users. Experiments show that our algorithms realize near-optimal network utilization with minor computational overhead.},
	keywords = {Astronomy, Computer networks, Concurrent computing, global-scale database federations, join scheduling algorithms, network utilization, network-aware join processing, parallel schedules, polynomial-time algorithm, Polynomials, Processor scheduling, Query processing, reduce resource usage, Scheduling algorithm, Spatial databases, spatial-join queries, Telecommunication traffic, Throughput},
	isbn = {978-1-4244-1836-7},
	doi = {10.1109/ICDE.2008.4497467},
	author = {Xiaodan Wang and Burns,R. and Terzis,A. and Deshpande, Amol}
}
@conference {13367,
	title = {Exploiting Correlated Attributes in Acquisitional Query Processing},
	booktitle = {21st International Conference on Data Engineering, 2005. ICDE 2005. Proceedings},
	year = {2005},
	month = {2005/04/05/08},
	pages = {143 - 154},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Sensor networks and other distributed information systems (such as the Web) must frequently access data that has a high per-attribute acquisition cost, in terms of energy, latency, or computational resources. When executing queries that contain several predicates over such expensive attributes, we observe that it can be beneficial to use correlations to automatically introduce low-cost attributes whose observation will allow the query processor to better estimate the selectivity of these expensive predicates. In particular, we show how to build conditional plans that branch into one or more sub-plans, each with a different ordering for the expensive query predicates, based on the runtime observation of low-cost attributes. We frame the problem of constructing the optimal conditional plan for a given user query and set of candidate low-cost attributes as an optimization problem. We describe an exponential time algorithm for finding such optimal plans, and describe a polynomial-time heuristic for identifying conditional plans that perform well in practice. We also show how to compactly model conditional probability distributions needed to identify correlations and build these plans. We evaluate our algorithms against several real-world sensor-network data sets, showing several-times performance increases for a variety of queries versus traditional optimization techniques.},
	keywords = {acquisitional query processing, Computer networks, Costs, data acquisition, Delay, Distributed computing, distributed information system, Distributed information systems, distributed processing, exponential time algorithm, optimization techniques, polynomial-time heuristic, Polynomials, probability, Query processing, real-time systems, real-world sensor-network, Runtime, Sensor phenomena and characterization, Sensor systems},
	isbn = {0-7695-2285-8},
	doi = {10.1109/ICDE.2005.63},
	author = {Deshpande, Amol and Guestrin,C. and Wei Hong and Madden,S.}
}
@conference {18323,
	title = {Tracking rigid motion using a compact-structure constraint},
	booktitle = {Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on},
	volume = {1},
	year = {1999},
	month = {1999///},
	pages = {198 -205 vol.1 - 198 -205 vol.1},
	abstract = {An approach for tracking the motion of a rigid object using parameterized flow models and a compact-structure constraint is proposed. While polynomial parameterized flow models have been shown to be effective in tracking the rigid motion of planar objects, these models are inappropriate for tracking moving objects that change appearance revealing their 3D structure. We extend these models by adding a structure-compactness constraint that accounts for image motion that deviates from a planar structure. The constraint is based on the assumption that object structure variations are limited with respect to planar object projection onto the image plane and therefore can be expressed as a direct constraint on the image motion. The performance of the algorithm is demonstrated on several long image sequences of rigidly moving objects},
	keywords = {compact-structure constraint, image motion, Image sequences, Motion estimation, parameterized flow models, polynomial parameterized flow models, Polynomials, rigid motion tracking, rigid object, rigidly moving objects, structure-compactness constraint, tracking},
	doi = {10.1109/ICCV.1999.791218},
	author = {Yacoob,Yaser and Davis, Larry S.}
}
@conference {17609,
	title = {Improved bounds and algorithms for hypergraph two-coloring},
	booktitle = {39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings},
	year = {1998},
	month = {1998/11/08/11},
	pages = {684 - 693},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We show that for all large n, every n-uniform hypergraph with at most 0.7√(n/lnn){\texttimes}2n edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC1 versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n1/3-0(1){\texttimes}2n due to Beck (1978). We further generalize this to a {\textquotedblleft}local{\textquotedblright} version, improving on one of the first applications of the Lovasz Local Lemma},
	keywords = {algorithms, Application software, Approximation algorithms, bounds, computational geometry, Computer science, Contracts, Erbium, graph colouring, History, hypergraph two-coloring, Lab-on-a-chip, MATHEMATICS, n-uniform hypergraph, Parallel algorithms, Polynomials, probability},
	isbn = {0-8186-9172-7},
	doi = {10.1109/SFCS.1998.743519},
	author = {Radhakrishnan,J. and Srinivasan, Aravind}
}
@conference {14621,
	title = {Hardness of flip-cut problems from optical mapping [DNA molecules application]},
	booktitle = {Compression and Complexity of Sequences 1997. Proceedings},
	year = {1997},
	month = {1997/06/11/13},
	pages = {275 - 284},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Optical mapping is a new technology for constructing restriction maps. Associated computational problems include aligning multiple partial restriction maps into a single {\textquotedblleft}consensus{\textquotedblright} restriction map, and determining the correct orientation of each molecule, which was formalized as the exclusive binary flip cut (EBFC) problem by Muthukrishnan and Parida (see Proc. of the First ACM Conference on Computational Molecular Biology (RECOMB), Santa Fe, p.209-19, 1997). Here, the authors prove that the EBFC problem, as well as a number of its variants, are NP-complete. They also identify another problem formalized as binary shift cut (BSC) problem motivated by the fact that there might be missing fragments at the beginnings and/or the ends of the molecules, and prove it to be NP-complete. Therefore, they do not have efficient, that is, polynomial time solutions unless P=NP},
	keywords = {binary shift cut, Biochemistry, Bioinformatics, biological techniques, Biology, biomedical optical imaging, combinatorial mathematics, combinatorial problem, computational complexity, computational problems, DNA, DNA molecule, exclusive binary flip cut, flip-cut problem hardness, Genetic engineering, Genomics, MATHEMATICS, molecular biology, molecular biophysics, molecule orientation, multiple partial restriction maps, NP-complete problem, optical mapping, polynomial time solutions, Polynomials, sequences},
	isbn = {0-8186-8132-2},
	doi = {10.1109/SEQUEN.1997.666922},
	author = {Dancik,V. and Hannenhalli, Sridhar and Muthukrishnan,S.}
}
@conference {17577,
	title = {Computing with very weak random sources},
	booktitle = {, 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings},
	year = {1994},
	month = {1994/11/20/22},
	pages = {264 - 275},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {For any fixed ε>0, we show how to simulate RP algorithms in time nO(log n) using the output of a δ-source with min-entropy R(ε). Such a weak random source is asked once for R(ε) bits; it outputs an R-bit string such that any string has probability at most 2-R(ε). If ε>1-1/(k+1), our BPP simulations take time nO(log(k n)) (log(k) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy RΩ(1), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson},
	keywords = {Application software, BPP simulations, Chor-Goldreich sources, computational complexity, Computational modeling, Computer science, Computer simulation, cryptography, distributed algorithms, expander constructions, hardness, MATHEMATICS, min-entropy, Physics computing, Polynomials, probability, R-bit string, randomness-efficient Leftover Hash Lemma, RP algorithms simulation, Testing, time-space tradeoffs, very weak random sources},
	isbn = {0-8186-6580-7},
	doi = {10.1109/SFCS.1994.365688},
	author = {Srinivasan, Aravind and Zuckerman,D.}
}
@conference {14587,
	title = {Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs},
	booktitle = {, Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI {\textquoteright}92},
	year = {1992},
	month = {1992/05/28/30},
	pages = {42 - 45},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {The authors present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in O(n3) and O(n2) time respectively. Their algorithm for computing the matching polynomial generalizes an existing result from Lovasz, Plummer (1986) and the chromatic polynomial algorithm improves the result given by Hunt, Ravi, Stearn (1988) from O(n4) time},
	keywords = {chromatic polynomials, computational complexity, Computer science, graph colouring, graph theory, matching polynomial, Polynomials, series-parallel graphs, Terminology, Tree data structures, Tree graphs},
	isbn = {0-8186-2812-X},
	doi = {10.1109/ICCI.1992.227709},
	author = {Chandrasekharan,N. and Hannenhalli, Sridhar}
}
