• Home
• Research
• Publications
• Useful Links

My esteemed coauthors

Selected Publications

1. Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization.
   Daniel Golovin and Andreas Krause. JAIR 2011.
   Winner of the 2013 IJCAI-JAIR 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.

2. 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 k-Coverage and Min-Sum 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 award-winning SAT solver, MetaProver 1.0.

3. Near-Optimal 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.

4. 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 worst-case 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.)

5. Strongly History-Independent 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 order-maintenance 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.

1. 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.)

2. 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 near-optimal 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.

3. 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 security-critical infrastructure? In this paper we take a game-theoretic 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 real-world sensing problems.

4. Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization.
   Daniel Golovin and Andreas Krause. JAIR 2011.
   Winner of the 2013 IJCAI-JAIR 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
   [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.

5. 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 p-independence system constraints. We show the 1/(p+1) approximation guarantee of the greedy algorithm for the non-adaptive case generalizes with this same ratio to the adaptive case. We illustrate the usefulness of our result on a complex adaptive match-making application.

6. Near-Optimal 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.

7. A Revealed Preference Approach to Computational Complexity in Economics. With Federico Echenique and Adam Wierman. Working Paper SSWP-1333, 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 worst-case 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.)

8. The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees. Working paper, 2010.
   Available as a preprint on arXiv. [BibTeX]. [Toggle Abstract]

   This is a companion paper to the B-treaps paper describing a uniquely represented B-tree analogue which has most of the performance guarantees of the B-treap, but is vastly simpler in design.

9. 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 no-regret guarantees that apply whenever the (unknown) utility function is submodular.

10. 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 no-regret model, and empirically evaluate it on two real-world online optimization problems on the web.

11. B-Treaps: A Uniquely Represented Alternative to B-Trees. 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 B-tree -- thus demonstrating the possibility of efficient strongly history-independent file-systems and databases. See also the companion paper on the B-Skip-List.

12. 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.

13. 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 k-Coverage and Min-Sum 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 award-winning SAT solver, MetaProver 1.0.

14. All-Norms and All-L_p-Norms 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 k-facility-location, TSP, and average flow-time minimization.

15. 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.

16. 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 History-Independent 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 strong-history independence, but the converse is false in some models of computation.)

17. Strongly History-Independent 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 order-maintenance data structure. We also improve the SHI hash table by incorporating a recent result of Pagh, Pagh, and Ruzic to show that 5-wise independence is good enough to yield expected constant time operations.

    
    Strongly History Independent Hashing with Deletion. With Guy Blelloch. Tech Report CMU-CS-06-156. [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.

18. 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 black-box techniques for learning how to interleave the execution of multiple heuristics in order to improve average-case running time when given a sequence of problems to solve.

19. 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.

20. 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.

21. Stochastic Packing-Market 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 Packing-Market Planning problem (SPMP), which is a stochastic generalization of the Maximum k-Set 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.

22. 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.

23. Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems. With Vineet Goyal and R. Ravi. STACS 2006. [BibTeX]. [Toggle Abstract]

    Demand-robust versions of common optimization problems were recently introduced (Dhamdhere et al., FOCS 2005) motivated by worst-case considerations of two-stage stochastic optimization models. We develop new techniques for demand-robust problems, and apply these techniques to demand-robust min-cut (improving the approximation factor from O(log(n)) to (1+\sqrt{2})), demand-robust shortest path (improving the approximation factor from 16 to 7.1), and some generalizations of these problems.

24. Approximating the k-Multicut Problem. With Viswanath Nagarajan and Mohit Singh. SODA 2006. [BibTeX]. [Toggle Abstract]

    We study the k-multicut 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 (1-epsilon)*k pairs at cost at most (2+epsilon)*OPT, where OPT is the optimal cost of separating k pairs.

25. Max-Min Fair Allocation of Indivisible Goods. Tech Report CMU-CS-05-144. [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.

26. A Model for Optimal Path Planning for Self-Reconfigurable Robots, ICAR 2003. [Toggle Abstract]

    Modular, self-reconfigurable 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 self-reconfigurable robots such as the PARC PolyBot platform.

© 2011 Daniel Golovin