My esteemed coauthors
Selected Publications

Adaptive Submodularity: Theory and Applications in Active Learning and
Stochastic Optimization.
Daniel Golovin and Andreas Krause. JAIR 2011.
Winner of the 2013 IJCAIJAIR Best Paper Prize [Toggle Abstract]We generalize the very useful notion of submodularity to the adaptive setting, where one must optimize over policies rather than sets. We obtain generalizations of classic results for maximum coverage and set cover in the adaptive setting, and use these to recover, strengthen, and generalize previous results in stochastic optimization and active learning.

An Online Algorithm for Maximizing Submodular Functions.
Matthew Streeter and Daniel Golovin. NIPS 2008. [Toggle Abstract]We present efficient online algorithms for generalizations of Maximum kCoverage and MinSum Set Cover. Our algorithms achieve asymptotically optimal approximation ratios in a natural regret model (assuming P != NP), and have many practical applications, for example learning to combine solvers for boolean satisfiability or integer programming which outperforms its component solvers. Indeed, our algorithm has been used to learn an awardwinning SAT solver, MetaProver 1.0.

NearOptimal Bayesian Active Learning with
Noisy Observations
Daniel Golovin, Andreas Krause, and Debajyoti Ray. NIPS 2010. [Toggle Abstract]We apply our adaptive submodularity framework to obtain a new greedy approximation algorithm for active learning with noisy observations. Our algorithm is the first to give approximation guarantees in the presence of noisy observations, and moreover we have guarantees for correlated noise models. We show that classic active learning algorithms have no such guarantees, and show in experiments that our algorithm significantly outperforms these classic algorithms in some settings.

A Revealed Preference Approach to Computational Complexity in Economics.
Federico Echenique, Daniel Golovin, and Adam Wierman. Working Paper, 2010. [Toggle Abstract]Market participants have limited computational resources, but what are the consequences of this for classic economic models? In the ongoing debate, many computer scientists and economists have strikingly different beliefs about this question. In this paper, we advance the dialog by providing a rigorous framework for posing such questions, in a manner which complements the traditional worstcase view of complexity. We provide initial results for the theory of the consumer, and show that, interestingly, computational constraints have no empirical consequences whatsoever for this fundamental economic theory. (See also Noam Nisan's take on the paper.)

Strongly HistoryIndependent Hashing with Applications.
Guy Blelloch and Daniel Golovin. FOCS 2007. [Toggle Abstract]We present the first strongly history independent (SHI) hash table that is fast, space efficient, and supports deletions. We also develop the first SHI perfect hash table, SHI ordered dictionaries, and SHI ordermaintenance data structure, and give a general technique for constructing efficient implementations of other SHI data structures on a RAM. Such data structures have canonical memory representation up to randomness, and thus provably store the minimal amount of information required of a correct implementation of their specifications. This allows for the construction of efficient systems for which we can remove information in a such a way that there is provably no trace it was ever there, among other applications.
Publications (reverse chronological order)
Papers I've published at Google can be found on my Google research page.
Submodular Function Maximization.
With Andreas Krause.
Book chapter in Tractability: Practical Approaches to Hard Problems (To appear) .
[Toggle Abstract]This is a survey on submodular function maximization that is to appear as a book chapter in Tractability: Practical Approaches to Hard Problems. (This draft is provided for personal use only, and may not be further distributed without written permission.)

Dynamic Resource Allocation in Conservation Planning.
With Andreas Krause and Beth Gardner and
Sarah J. Converse and Steve Morey. AAAI 2011. (Outstanding Paper Award)
[BibTeX]. [Toggle Abstract]We consider a challenging sequential optimization problem under uncertainty in computational sustainability: the problem of constructing an ecological reserve over time in order to protect particular species, in a dynamic environment where the annual budget available and the land available for acquisition may vary from year to year. In this paper, we develop an efficient algorithm for adaptively making recommendations for this dynamic conservation planning problem, and prove that it obtains nearoptimal performance. We further evaluate our approach on a detailed reserve design case study of conservation planning for three rare species in the Pacific Northwest of the United States.

Randomized Sensing in Adversarial Environments.
With Andreas Krause and Alex Roper.
IJCAI 2011.
[BibTeX]. [Toggle Abstract]How should we manage a sensor network to guard securitycritical infrastructure? In this paper we take a gametheoretic view, and present a principled solution to this and related problems. Specifically, we give the first algorithm for efficiently computing approximate maximin mixed strategies in a large class of games, and evaluate it on two realworld sensing problems.

Adaptive Submodularity: Theory and Applications in Active Learning and
Stochastic Optimization.
Daniel Golovin and Andreas Krause. JAIR 2011.
Winner of the 2013 IJCAIJAIR Best Paper Prize
There is also an earlier arXiv version and an even earlier COLT 2010 conference version. I recommend the JAIR version. [BibTeX], [video of a related invited talk], [Slides], Powerpoint slides
 Older PDF slides of my COLT talk
 Older Powerpoint slides of my COLT talk
We generalize the very useful notion of submodularity to the adaptive setting, where one must optimize over policies rather than sets. We obtain generalizations of classic results for maximum coverage and set cover in the adaptive setting, and use these to recover, strengthen, and generalize previous results in stochastic optimization and active learning.

Adaptive Submodular Optimization under Matroid Constraints.
With Andreas Krause. Preprint on arXiv.
[BibTeX]. [Toggle Abstract]We extend the adaptive submodularity framework further, to the problem of maximizing an adaptive monotone submodular function subject to one or more matroid constraints, or more generally to pindependence system constraints. We show the 1/(p+1) approximation guarantee of the greedy algorithm for the nonadaptive case generalizes with this same ratio to the adaptive case. We illustrate the usefulness of our result on a complex adaptive matchmaking application.

NearOptimal Bayesian Active Learning with
Noisy Observations.
With Debajyoti Ray and Andreas Krause.
NIPS 2010.
A longer version is available on arXiv.
[BibTeX],
[Poster],
[video of a related invited talk].
[Toggle Abstract]
We apply our adaptive submodularity framework to obtain a new greedy approximation algorithm for active learning with noisy observations. Our algorithm is the first to give approximation guarantees in the presence of noisy observations, and moreover we have guarantees for correlated noise models. We show that classic active learning algorithms have no such guarantees, and show in experiments that our algorithm significantly outperforms these classic algorithms in some settings.

A Revealed Preference Approach to Computational Complexity in Economics.
With Federico Echenique and Adam Wierman. Working Paper SSWP1333, 2010.
[Toggle Abstract]
Market participants have limited computational resources, but what are the consequences of this for classic economic models? In the ongoing debate, many computer scientists and economists have strikingly different beliefs about this question. In this paper, we advance the dialog by providing a rigorous framework for posing such questions, in a manner which complements the traditional worstcase view of complexity. We provide initial results for the theory of the consumer, and show that, interestingly, computational constraints have no empirical consequences whatsoever for this fundamental economic theory. (See also Noam Nisan's take on the paper.)

The BSkipList: A Simpler Uniquely Represented
Alternative to BTrees.
Working paper, 2010.
Available as a preprint on arXiv. [BibTeX]. [Toggle Abstract]This is a companion paper to the Btreaps paper describing a uniquely represented Btree analogue which has most of the performance guarantees of the Btreap, but is vastly simpler in design.

Online Distributed Sensor Selection.
With Matthew Faulkner and Andreas Krause.
IPSN 2010.
A more detailed technical report version is available on arXiv. [BibTeX]. [Toggle Abstract]A key problem in sensor networks is to decide which sensors to query when, in order to obtain the most useful information (e.g., for performing accurate prediction), subject to constraints (e.g., on power and bandwidth). In many applications the utility function is not known a priori, must be learned from data, and can even change over time. In this paper, we present an efficient, distributed algorithm for repeatedly selecting sensors online, and prove very strong theoretical noregret guarantees that apply whenever the (unknown) utility function is submodular.

Online Learning of Assignments.
With Matthew Streeter and Andreas Krause.
NIPS 2009 (A NIPS Spotlight Paper).
A more detailed technical report version is available on arXiv. [BibTeX]. [Toggle Abstract]We model various problems such as sponsored search ad selection as the problem of repeatedly selecting an assignment of items to positions to maximize a sequence of monotone submodular functions that arrive one by one. We present an efficient algorithm for this general problem which has strong theoretical guarantees in the noregret model, and empirically evaluate it on two realworld online optimization problems on the web.

BTreaps: A Uniquely Represented Alternative to BTrees.
ICALP 2009.
[BibTeX].
[Toggle Abstract]
This paper provides the first construction of an efficient uniquely represented data structure with the same performance guarantees as a Btree  thus demonstrating the possibility of efficient strongly historyindependent filesystems and databases. See also the companion paper on the BSkipList.

Simultaneous Source Location.
With Konstantin Andreev, Charles Garrod, Bruce Maggs, and Adam Meyerson.
TALG 2009.
[BibTeX].
[Toggle Abstract]
We consider the problem of selecting locations for sources of flow in a capacitated graph such that a given set of demands for flow can be satisfied simultaneously, with the goal of minimizing the number of locations chosen. We obtain interesting upper and lower bounds on the approximability of this problem and various special cases of it.

An Online Algorithm for Maximizing Submodular Functions.
With Matthew Streeter. NIPS 2008 (A NIPS Spotlight
Paper).
A more detailed
technical report version
is available as well.
[BibTeX].
[Toggle Abstract]
We present efficient online algorithms for generalizations of Maximum kCoverage and MinSum Set Cover. Our algorithms achieve asymptotically optimal approximation ratios in a natural regret model (assuming P != NP), and have many practical applications, for example learning to combine solvers for boolean satisfiability or integer programming which outperforms its component solvers. Indeed, my collaborator Matthew Streeter has used our algorithm to learn an awardwinning SAT solver, MetaProver 1.0.

AllNorms and AllL_pNorms Approximation
Algorithms.
With Anupam Gupta, Amit Kumar, and Kanat Tangwongsan. FSTTCS 2008.
A more detailed technical report version
is available as well.
[BibTeX].
[Toggle Abstract]
We examine approximation algorithms that simultaneously perform well on all norms, or on all L_p norms. We show that the greedy algorithm for set cover simultaneously O(p) approximates the L_p norm of the cover time vector for all values of p, and that no efficient algorithm can do better than O(p) for any fixed value of p. We also present algorithms and structural results for other problems such as kfacilitylocation, TSP, and average flowtime minimization.

My PhD thesis on
Uniquely Represented Data Structures with Applications to Privacy,
[Abstract,
BibTeX].
[Toggle Abstract]
My thesis work provides the theoretical foundation for efficient uniquely represented data structures. These data structures ensure that the memory layout of the data structure is a function of the logical state it is supposed to encode, rather than a function of the sequence of operations used to create it. Thus each logical state is encoded in a unique machine state. This opens up the possibility, for the first time, of efficient systems that store exactly the information that we ask them to store, and no more. Such systems would eliminate the potential for privacy and security violations enabled by the undesirable storage of extraneous information.

Uniquely Represented Data Structures for
Computational Geometry.
With Guy Blelloch and Virginia Vassilevska Williams. SWAT 2008.
A more detailed
technical report version
is available as well.
[BibTeX].
[Toggle Abstract]
We build on earlier results for Strongly HistoryIndependent Hashing, and develop uniquely represented data structures for several data structures used extensively in computational geometry. (I favor the phrase "uniquely represented" over "strongly history independent" because unique representation is a slightly stronger condition  unique representation implies stronghistory independence, but the converse is false in some models of computation.)

Strongly HistoryIndependent Hashing with Applications.
With Guy Blelloch. FOCS 2007.
[BibTeX],
[pdf slides],
[slides handout].
[Toggle Abstract]
We build upon the work found in our earlier tech report, and develop the first SHI perfect hash table, SHI ordered dictionaries, and a SHI ordermaintenance data structure. We also improve the SHI hash table by incorporating a recent result of Pagh, Pagh, and Ruzic to show that 5wise independence is good enough to yield expected constant time operations.
Strongly History Independent Hashing with Deletion. With Guy Blelloch. Tech Report CMUCS06156. [BibTeX]. [Toggle Abstract]We present the first strongly history independent (SHI) hash table that is fast, space efficient, and supports deletions. A hash table that supports deletions is SHI if it has a canonical memory representation up to randomness. Thus, the memory representation of a SHI hash table reveals exactly the information available through the hash table interface, and nothing more. We also give a general technique which yields the first efficient implementations of a host of SHI data structures on a RAM.

Combining Multiple Heuristics Online.
With Matthew Streeter and Stephen F. Smith.
AAAI 2007.
[BibTeX].
[Toggle Abstract]
Given several different heuristics for some difficult problem, each of which may take advantage of different instance features, can you construct a single solver that exploits the strengths of each? We investigate this problem, and present blackbox techniques for learning how to interleave the execution of multiple heuristics in order to improve averagecase running time when given a sequence of problems to solve.

Restart Schedules for Ensembles of Problem Instances.
With Matthew Streeter and Stephen F. Smith.
AAAI 2007.
[BibTeX].
[Toggle Abstract]
Given a randomized heuristic for some difficult problem, one can often significantly reduce the expected running time by periodically restarting the heuristic with a fresh random seed. We investigate the problem of selecting the best possible restart schedule for a set of instances, and then adapt the algorithms obtained to the online setting.

Combining Multiple Constraint Solvers: Results on the CPAI '06 Competition Data.
With Matthew Streeter and Stephen F. Smith.
Invited Paper, 2nd International CSP Solver Competition.
[BibTeX].
(Download the full proceedings [PDF]).
[Toggle Abstract]In this paper we experimentally evaluate algorithms from our paper "Combining Multiple Heuristics Online," and show that our approach yields notable improvements in practice.

Stochastic PackingMarket Planning.
EC 2007.
[BibTeX],
[pdf slides].
[Toggle Abstract]
Motivated by the problem of centralized market clearing in a market with probabilistic supply and demand, we introduce the Stochastic PackingMarket Planning problem (SPMP), which is a stochastic generalization of the Maximum kSet Packing problem. We provide an approximation algorithm for SPMP, and also give a linear programming based approximation for the expected weight of a maximum set packing in a random subhypergraph of a fixed hypergraph G, using techniques which may be of independent interest.

Quorum Placement in Networks: Minimizing Network Congestion.
With Anupam Gupta, Bruce M. Maggs, Florian Oprea, and Michael
K. Reiter. PODC 2006.
[BibTeX].
[Toggle Abstract]
Quorum systems provide a logical framework for maintaining data consistency under distributed accesses in a distributed system and have several applications. Implementing a quorum system requires one to map the quorum system onto the physical network that comprises the distributed system by assigning the logical elements of the quorum system to machines. We call this task quorum placement, and develop algorithms for placing quorum systems to minimize the induced network congestion.

Pay Today for a Rainy Day: Improved Approximation Algorithms for DemandRobust
MinCut and Shortest Path Problems.
With Vineet Goyal and R. Ravi. STACS 2006.
[BibTeX].
[Toggle Abstract]
Demandrobust versions of common optimization problems were recently introduced (Dhamdhere et al., FOCS 2005) motivated by worstcase considerations of twostage stochastic optimization models. We develop new techniques for demandrobust problems, and apply these techniques to demandrobust mincut (improving the approximation factor from O(log(n)) to (1+\sqrt{2})), demandrobust shortest path (improving the approximation factor from 16 to 7.1), and some generalizations of these problems.

Approximating the kMulticut Problem.
With Viswanath Nagarajan and Mohit Singh. SODA 2006.
[BibTeX].
[Toggle Abstract]
We study the kmulticut problem: Given an edge weighted undirected graph, a set of L pairs of vertices, and a target number k less than or equal to L, find the minimum cost set of edges whose removal disconnects at least k pairs. This generalizes the multicut problem, where k = L. We obtain an 8/3+epsilon factor approximation for tree instances, for arbitrarily small positive epsilon and an O(log^2(n) log log (n)) approximation on general graphs, as well as a bicriteria solution that separates at least (1epsilon)*k pairs at cost at most (2+epsilon)*OPT, where OPT is the optimal cost of separating k pairs.

MaxMin Fair Allocation of Indivisible Goods.
Tech Report CMUCS05144.
[BibTeX].
[Toggle Abstract]
We consider the problem of fairly allocating a set of m indivisible goods to n agents, given the agents' utilities for each good. Fair allocations in this context are those maximizing the minimum utility received by any agent. We give hardness results and polynomial time approximation algorithms for several variants of this problem. Our main result is a bicriteria approximation in the model with additive utilities, in which a (1 − 1⁄k) fraction of the agents receive utility at least OPT/k, for any integer k.

A Model for Optimal Path Planning for SelfReconfigurable Robots,
ICAR 2003.
[Toggle Abstract]
Modular, selfreconfigurable robots may have many means of locomotion, each suitable for different types of terrain. Given costs for each means of locomotion as a function of the terrain's local characteristics (e.g. slope, unevenness), and costs for the reconfigurations needed to switch between two means of locomotion, we seek to minimize the cost of the robot's path to its goal. In this paper, we focus on practical algorithms that are parallelizable, and hence suitable for distributed computing platforms common to modular selfreconfigurable robots such as the PARC PolyBot platform.
Coauthors

Konstantin Andreev,
Guy Blelloch,
Sarah Converse,
Federico Echenique,
Matthew Faulkner,
Beth Gardner,
Charlie Garrod,
Vineet Goyal,
Anupam Gupta,
Andreas Krause,
Amit Kumar,
Bruce Maggs,
Adam Meyerson,
Steve Morey,
Viswanath Nagarajan,
Florian Oprea,
R. Ravi,
Debajyoti Ray,
Michael Reiter,
Alex Roper,
Mohit Singh,
Stephen F. Smith,
Matthew Streeter,
Kanat Tangwongsan,
Virginia Vassilevska Williams,
Adam Wierman
Copyright Notices
The ACM copyright notice:The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Copyright for STACS submissions is held by SpringerVerlag. These submissions can also be found via the LNCS series homepage