Sham Kakade (University of Pennsylvania)

Deterministic Calibration and Nash Equilibrium

Eyal Even-Dar, Tel Aviv
Experts in a Markov Decision Process.

Active Learning :Theory and Practice

Seshadhri Comandur, Princeton University

In standard property testing, the task is to distinguish between
objects that have a property P and those that are \eps-far from P, for some
\eps > 0. In this setting, it is perfectly acceptable for the tester to
provide a negative answer for every input object that does not satisfy P.
This implies that property testing in and of itself cannot be expected to
yield any information whatsoever about the distance from the object to the
property. We address this problem in this paper, restricting our attention
to monotonicity testing. A function f:[1,n] -> R is at distance \eps_f from
being monotone if it can (and must) be modified at \eps_f*n places to become
monotone. For any fixed \delta>0, we compute, with probability at least 2/3,
an interval [(1/2 -\delta)\eps, \eps] that encloses \eps_f. The running time
of our algorithm is linear in log n and almost linear in 1/eps_f, which is a
substantial improvement over previous work.

Joint with with Nir Ailon, Bernard Chazelle and Ding Liu

Abstract:
A fundamental problem in combinatorial optimization is
the edge-disjoint paths problem. We are given a graph G=(V,E)
and set of pairs of vertices (s_1,t_1), (s_2,t_2), ..., (s_k,t_k).
The objective is to decide if all the pairs can be connected
by edge-disjoint paths. Generalizations include the unsplittable
flow problem and the maximum integer multicommodity flow problem.

All of the above problems are NP-hard and we focus on approximation
algorithms for the maximization versions where the goal is to
maximize the number of pairs that can be connected (routed).

In this talk we give an overview of some recent results and
techniques that give substantially improved results for these
problems in undirected planar graphs if two paths are allowed
on an edge. Along the way we introduce a previously unexplored
variant called the all-or-nothing multicommodity flow problem
and discuss results for this problem.


Joint work with Sanjeev Khanna (U. Penn) and Bruce Shepherd (Bell Labs).
 

Sampling to estimate arbitrary subset sums


Mikkel Thorup

(joint work with Nick Duffield and Carsten Lund)

Abstract

  Starting with a set of weighted items, we want to create a generic sample of
  a certain size that we can later use to estimate the total weight of
  arbitrary subsets. Applied in Internet traffic analysis, the items
  could be records summarizing the flows streaming by a router, with,
  say, a hundred records sampled each hour. A subset could be flow
  records of a worm attack identified later. Our past samples now
  allow us to trace the history of the attack even though the worm was
  unknown while the samples were made.
  
  Estimation from the samples must be accurate even with heavy-tailed
  distributions where most of the weight is concentrated on a few
  heavy items. We want the sample to be weight sensitive, giving
  priority to heavy items. At the same time, we want sampling without
  replacement in order to avoid selecting heavy items multiple times.
  To fulfill these requirements we introduce priority sampling, which
  is the first weight sensitive sampling scheme without replacement
  that is suitable for estimating subset sums.  Testing priority
  sampling on Internet traffic analysis, we found it to perform orders
  of magnitude better than previous schemes.

  Priority sampling is simple to define and implement: we consider a steam of 
  items i=0,...,n-1 with weights w_i. For each item i, we generate
  a random number r_i in (0,1) and create a priority q_i=w_i/r_i.
  The sample S consists of the k highest priority items. Let
  t be the (k+1)th highest priority. Each sampled item i in S
  gets a weight estimate W_i=max{w_i,t}, while non-sampled
  items get weight estimate W_i=0. 

  Magically, it turns out that the weight estimates are unbiased, that
  is, E[W_i]=w_i, and by linearity of expectation, we get unbiased
  estimators over any subset sum simply by adding the sampled weight
  estimates from the subset. Also, we can estimate the variance of the
  estimates, and surpricingly, there is no co-variance between different
  weight estimates W_i and W_j.

  We conjecture an extremely strong near-optimality; namely that for
  any weight sequence, there exists no specialized scheme for
  sampling k items with unbiased estimators that gets smaller
  total variance than priority sampling with k+1 items.

Experts in a Markov Decision Process


We consider an MDP setting in which the reward function is allowed to
change during each time step of play (possibly in an adversarial
manner), yet the dynamics remain fixed. Similar to the experts
setting, we address the question of how well can an agent do when
compared to the reward achieved under the best stationary policy over
time. We provide \emph{efficient} algorithms, which have regret bounds
with \emph{no dependence} on the size of state space. Instead, these
bounds depend only on a certain horizon time of the process and
logarithmically on the number of actions.  We also show that in the
case that the dynamics change over time, the problem becomes
computationally hard


Joint work with Sham Kakade and Yishay Mansour

  Hardness of Three Routing Problems
 Matt Andrews, Lucent Bell Labs.

In this talk we present hardness-of-approximation results for the undirected
edge-disjoint paths problem, the undirected congestion minimization problem
and the buy-at-bulk network design problem. We first show that the problems
are hard to approximate when each demand is constrained to follow one of a
small set of "canonical paths".  We then show how to embed our examples into
high-girth graphs in such a way that all good routings use many canonical
paths. These techniques allow us to derive hardness results for the general
problems.

Eli Berger, IAS. 

Active Learning â Theory and Practice

Ran Gilad-Bachrach, The Hebrew University

Abstract:

Passive learners only listen to their teachers whereas active learners
can direct questions to them. Both theory and practice confirm that
active learners can significantly outperform their passive contenders.
In this talk, we will review the latest results in this field. We will
look at different models for active learning and discuss their pros
and cons. We will show that when certain conditions apply, active
learners learn exponentially faster than passive learners do. We will
focus on our attempt to come up with an algorithm that has both
theoretical grounding and efficient implementation.

The talk will be self-contained.

Holographic Algorithms

Leslie G. Valiant

Harvard University

Using the notion of polynomial time reduction computer scientists have discovered an astonishingly rich web of interrelationships among the myriad natural computational problems that arise in diverse applications. These relationships have been used both to give evidence of intractability, such as that of NP-completeness, as well as some surprising new algorithms.

In this talk we discuss a notion of reduction, which we call a holographic reduction, that is more general than the traditional one. Instead of locally mapping solutions one-to-one it maps them many-to-many but preserves the sum of the solutions. One application is to finding new  polynomial time algorithms where none  was known before. We shall give some examples of such algorithms.

A more radical potential direction is that of revisiting the currently accepted conjectures  of computer science, such as that P does not equal NP, and seeing whether this new kind of reduction offers any new insights towards either positive or negative results. The talk will review complexity theory in this light.