Differentially Private Approximation Algorithms (2009)
Gupta, Anupam, Ligett, Katrina, McSherry, Frank, Roth, Aaron, Talwar, Kunal
Consider the following problem: given a metric space, some of whose points are "clients", open a set of at most $k$ facilities to minimize the average distance from the clients to these facilities....
Algorithms, Security, Theory (2008)
We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class...
Compressing Rectilinear Pictures and Minimizing Access Control Lists (2008)
Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
Avrim Blum, Mohammadtaghi Hajiaghayi, Aaron Roth, Katrina Ligett
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that selfinterested players will play according to a Nash equilibrium (which may even be...
The price of stochastic anarchy (2008)
Christine Chung, Katrina Ligett, Kirk Pruhs, Aaron Roth
Abstract. We consider the solution concept of stochastic stability, and propose the price of stochastic anarchy as an alternative to the price of (Nash) anarchy for quantifying the cost of...
The price of stochastic anarchy (2008)
Christine Chung, Katrina Ligett, Kirk Pruhs, Aaron Roth
Abstract. We consider the solution concept of stochastic stability, and propose the price of stochastic anarchy as an alternative to the price of (Nash) anarchy for quantifying the cost of...
Regret minimization and the price of total anarchy (2007)
Avrim Blum, Mohammadtaghi Hajiaghayi, Katrina Ligett, Aaron Roth
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium (which may even be...
Regret minimization and the price of total anarchy (2007)
Avrim Blum, Mohammadtaghi Hajiaghayi, Katrina Ligett, Aaron Roth
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium (which may even be...
David L. Applegate, Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
Compressing rectilinear pictures and minimizing access control lists (2007)
David A. Applegate, Gruia Calinescuy, David S. Johnsonz, Howard Karloffx, Katrina Ligett, Jia Wangk
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
David L. Applegate, Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
Compressing rectilinear pictures and minimizing access control lists (2007)
Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett, Jia Wang
We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in...
Regret minimization and the price of total anarchy (2007)
Avrim Blum, Mohammadtaghi Hajiaghayi, Aaron Roth, Katrina Ligett
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that selfinterested players will play according to a Nash equilibrium (which may even be...
Playing games with approximation algorithms (2007)
Sham M. Kakade, Adam Tauman Kalai, Katrina Ligett
Abstract. In an online linear optimization problem, on each period t, an online algorithm chooses st ∈ S from a fixed (possibly infinite) set S of feasible decisions. Nature (who may be...
Avrim Blum, Eyal Even-dar, Katrina Ligett
Abstract There has been substantial work developing simple, efficient no-regret algorithms for a wideclass of repeated decision-making problems including online routing. These are adaptive strategies...
Routing Without Regret: On Convergence To Nash . . . (2006)
Avrim Blum, Eyal Even-Dar, Katrina Ligett
There has been substantial work developing simple, efficient no-regret algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive strategies an...
Avrim Blum, Eyal Even-dar, Katrina Ligett
Abstract. There has been substantial work developing simple, efficient no-regret algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive...
Avrim Blum, Eyal Even-dar, Katrina Ligett
There has been substantial work developing simple, efficient no-regret algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive strategies an...