Jeremiah Blocki
Adaptive Regret Minimization in Bounded-Memory Games.
Tue, 11/15/2011 - 15:01 — SomNambulAuthors: Jeremiah Blocki, Anupam Datta, Nicolas Christin, Arunesh Sinha
Subjects: Computer Science and Game Theory
AbstractOnline learning algorithms that minimize regret provide strong guarantees in
situations that involve repeatedly making decisions in an uncertain
environment, e.g. a driver deciding what route to drive to work every day.
While regret minimization has been extensively studied in repeated games, we
study regret minimization for a richer class of games called bounded memory
games. In each round of a two-player bounded memory-m game, both players
simultaneously play an action, observe an outcome and receive a reward.Resolving the Complexity of Some Data Privacy Problems.
Fri, 04/23/2010 - 15:01 — SomNambulAuthors: Ryan Williams, Jeremiah Blocki
Subjects: Computational Complexity
AbstractWe formally study two methods for data sanitation that have been used
extensively in the database community: k-anonymity and l-diversity. We settle
several open problems concerning the difficulty of applying these methods
optimally, proving both positive and negative results:1. 2-anonymity is in P.
2. The problem of partitioning the edges of a triangle-free graph into
4-stars (degree-three vertices) is NP-hard. This yields an alternative proof
that 3-anonymity is NP-hard even when the database attributes are all binary.- Read more
- 5 comments
- login or register to post comments
User login
