Capital Area Theory Seminar: Fall 2007
Capital Area Theory Seminar: Fall 2007
| The Capital Area Theory Symposia is an UMIACS sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department. |
CATS usually meets on Fridays 11:00pm-12:00pm AVW 4185 but some talks may be at a different place and time.
| Date | Time | Location | Speaker | Title |
|---|---|---|---|---|
| Sep 7th | 11:00 AM | AVW 4185 | Matt McCutchen | Optimality Criteria for Matching with One-Sided Preferences |
| Sep 14th | 11:00 AM | AVW 4185 | Julian Mestre | A Look at the Optimization Landscape of the Maximum Independent Set Problem |
| Sep 21st | 11:00 AM | AVW 4185 | Jian Li | More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding |
| Sep 28th | 11:15 AM | AVW 4185 | Azarakhsh Malekian |
Basic concepts in game Theory |
| Oct 05th | 11:00 AM | AVW 4185 | Azarakhsh Malekian | Basic Concepts in game Theory |
| Oct 26th | 11:00 AM | AVW 4185 | Andrea Olea | Windows Scheduling |
| Oct 30th | 2:00 PM | AVW 2460 | Jason Hartline | Optimal Mechanism Design |
| Nov 9th | 11:00 AM | AVW 4185 | Matt McCutchen | Approximation algorithms for streaming-model k-center clustering |
| Nov 16th | 11:00 AM | AVW 3258 | Sandra Zilles | A formal analysis of iterative machine learning methods |
| Nov 30th | 11:00 AM | AVW 4185 | Dov Gordon | A Survey of Private Approximation of Search Problems |
| Dec 7th | 11:00 AM | AVW 4185 | Mohammadreza Ghodsi | Max SAT Problem |
For additional information send email to Samir Khuller.
If you want to receive announcements of upcoming talks join the theory-local mailing list.
|
|
Given a set of people, a set of positions available
to them (e.g.,houses or jobs), and each person's preference ordering of the
positions, how shall we assign the people to the positions? Sincedifferent
matchings inevitably favor different people, it is not obvious which matching
should be considered best overall; many
different optimality criteria are possible. This talk covers three optimality
criteria that share a property that may help them resist manipulation by the
people. First, we introduce the criterion of ``popularity'' studied by Abraham
et al., under which an optimal matching might not exist but can be found
efficiently if it does. Then, we discuss two generalizations under which an
optimal matching always exists, namely ``least unpopularity factor'' and ``least
unpopularity margin''. Unfortunately, it is NP-hard to find a matching of least
unpopularity factor (as we show); the complexity of finding a matching of least
unpopularity margin is not yet known. This work represents a step toward the
goal of a computer program to automatically solve real-world matching problems
according to a good optimality criterion.
Julian Mestre
Local search is a widely-used heuristic that can be applied to many
optimization problems. The high-level idea is simple: Starting from a given
feasible solution, make small improvements until reaching a locally optimal
solution. Physics provides a nice analogy for this approach: Stating from a
given state, a physical system tries to minimize its potential energy until
finally settling on a stable (locally optimal) configuration. Needless to
say, this approach has an obvious pitfall: If the "optimization landscape"
of our problem is rugged then a local optimum may be far away from a
globally optimal solution.
While in practice local search algorithms tend to do very well, this
landscape ruggedness proves, more often than not, a big obstacle for worst
case analysis. In this talk I will survey some results from the literature
on local search algorithms for the Maximum Independent Set problem, which
show how sometimes these obstacles can be overcome... even in theory!
Jian Li
There is a large literature devoted to the
problem of finding an optimal (min-cost) prefix-free code with an unequal
letter-cost encoding alphabet of size. While there is no known polynomial
time algorithm for solving it optimally there are many good heuristics that
all provide additive errors to optimal. The additive error in these
algorithms usually depends linearly upon the largest encoding letter size.
This paper was motivated by the problem of finding optimal codes when the
encoding alphabet is infinite. Because the largest letter cost is infinite,
the previous analyses could give infinite error bounds. We provide a new
algorithm that works with infinite encoding alphabets. When restricted to
the finite alphabet case, our algorithm often provides better error bounds
than the best previous ones known.
(Joint work with Mordecai Golin)
Basic concepts in game Theory
Azarakhsh Malekian
We are going to go over the classical games, basic solution concepts and some computational issues. The goal is to introduce some preliminary concepts in game theory that are interesting for the people in Computer Science as well.
Windows Scheduling
Andrea Olea
Given n items (we can think of them as
information pages) and a sequence of numbers w_1, w_2, ...w_n (representing
window lengths), the goal is to
schedule all items on different time slots on broadcasting channels such
that the number of slots between consecutive occurrences of the i'th item
is at most w_i, and the number of channels is minimized. This problem is
called Windows Scheduling and has interesting connections to bin packing.
References: Bar-Noy A., Ladner R., Tamir T., "Windows Scheduling as a
Restricted
Version of Bin Packing" (SODA 04)
Bar-Noy A., Ladner R., Tamir T., VanDeGrift T., "Windows Scheduling of
Arbitratry Length Jobs on Parallel Machines" (SPAA 05)
Optimal Mechanism Design: from the 2007 Nobel Prize in Economics to the Foundations of Internet Algorithms
Jason Hartline
As the Internet has developed to become the
single most important arena for resource sharing among parties with diverse and
selfish interests, traditional algorithmic and distributed systems
approaches are insufficient. To prevent undesirable Internet phenomena such as
spam in email systems, bid-sniping in eBay's auction marketplace, free-loading
in file-sharing networks, and click-fraud in
Internet advertising; game-theoretic and economic considerations must be made.
This issue is addressed by the economics field of mechanism design. Consider a
mechanism to be a protocol in which selfish agentsinteract with a central server
that then chooses an outcome (e.g.,which agents are given access to which
Internet resources) and possible payments (sometimes it is necessary to make
agents pay for the resources they use).
The first half of this talk surveys the seminal 1981 work of economist Roger
Myerson who was recognized last Thursday with the 2007 Nobel Prize in Economics.
His work gave a characterization of the kinds of outcomes that are
implementable by a mechanism. From this characterization, he reduces the
problem of optimizing the total payments (i.e., the profit of the mechanism) to
the problem optimizing
the social welfare (i.e., total utility generated by the outcome selected).
This result has since directly and indirectly implied countless other
significant results in economics, hence the Nobel
recognition.
For the second part of this talk we discuss implications and extensions of this
result to the design of Internet algorithms. In particular, implementation of
good mechanisms often requires the
agents make payments. E.g., spam wound not exist in an email mechanism that
charged one cent for each email sent. Yet, many Internet protocols do not allow
payment to be made. Would you pay for
email? A computational approach to solve this problem is to use computational
payments instead of monetary payments. E.g., to send an email the sender's
computer must first solve a computational task that provably takes ten seconds
to solve; this would effectively stop email spam. Notice that in order to
obtain a desirable outcome (no spam) we have to waste the computational
resources of good agents (which is a loss to society). We show how Myerson's
characterization can be used to design a mechanism that optimizes the social
welfare when payments are not monetary but in instead in units of wasted
resources. These results apply in very general settings.
The *k-center clustering problem* is: given a
set of input points in some metric space, find a set of k spherical clusters
such that every input point lies in at least one cluster, and minimize the
radius of the largest cluster. This problem is easy to approximate with
factor 2 but NP-hard to approximate with any smaller constant factor. We
consider this problem in the *streaming model*: the algorithm is fed input
points one at a time and does not have enough memory to hold all of them.
Charikar et al. [1] present a streaming-model 8-approximation algorithm.
We use the results of Khuller et al. [2] to extend this algorithm to a
streaming-model 24-approximation for k-center clustering with a small constant
number of outliers. On two additional assumptions, we improve these
algorithms to (2 + epsilon)- and (3 + epsilon)-approximation schemes,
respectively, where the constant factor of memory usage increases as epsilon
decreases.
[1] M. Charikar, C. Chekuri, T. Feder, and R. Motwani. "Incremental Clustering
and Dynamic Infomation Retrieval." http://theory.stanford.edu/~tomas/cluster.ps.gz
[2] M. Charikar, S. Khuller, D. Mount, and G. Narasimhan. "Algorithms for
Facility Location Problems with Outliers." http://www.cs.umd.edu/users/samir/grant/outlier.ps
A formal analysis of iterative machine learning methods
Sandra Zilles
When trying
to learn classifiers from data streams, it is in general infeasible to
compute a completely new hypothesis from scratch for each data point, taking
all the data seen up to that moment into account. Iterative algorithms,
updating the previous hypothesis using only the current training example,
very often seem to be the better choice.
The talk will deal with the question whether we can impose certain intuitive
requirements on such iterative learning algorithms without reducing their
general capabilities. For that purpose, we analyse
iterative learning on the abstract level of Gold's identification in the
limit. The intuitive requirements we deal with are consistency (hypotheses
must never contradict known data) and conservativeness
(hypotheses must be maintained as long as they are consistent). Both are for
instance satisfied by Rosenblatt's perceptron algorithm (a classical example
of an iterative algorithm), but not necessarily by
every iterative learning method. The results obtained in a formal analysis
illustrate in which way different consistency and conservativeness demands
can affect the capabilities of iterative learners. Interestingly, some of
the results (and open questions) seem to relate to the open problem of how
to characterise the structure of typical classes learnable iteratively and
thus how to design uniform iterative learning methods.
In a setting where a server holds a private
instance x of some NP-hard problem f(), and wishes to provide an
approximation to one solution (of possibly many) in the set f(x), we ask
whether it's possible to ensure that the approximation reveals nothing more
about x than the optimal solution would reveal. We will prove that for
vertex cover the above is impossible; a similar approach rules out private
approximation for the k-center problem. We will then introduce a relaxation
of the definitions and prove some results, positive and negative, regarding
private approximations that reveal partial information about x.
Note that none of this work is my own. The references are here:
A. Beimel, P. Carmi, K. Nissim, and E. Weinreb. Private Approximation of
Search Problems. In Proc. of 38th Annu. ACM Symp. on the Theory of
Computing (STOC), pages 119-128, 2006
A. Beimel, R. Hallak, and K. Nissim. Private Approximation of Clustering
and Vertex Cover. In the Fourth Theory of Cryptography Conference,
volume 4932 of Lecture Notes in Computer Science, pages 338-403, 2007
found here:
http://www.cs.bgu.ac.il/
and here:
http://www.cs.bgu.ac.il/
Maximum satisfiability is a classical
problem in approximation algorithm. The unweighted MAX-SAT is: given a
boolean formula in CNF,
find an assignment to the variables that maximizes the number of satisfied
clauses. I will present a 3/4 approximation algorithm for
MAX-SAT. The algorithm is based on two simple randomized algorithms. This
algorithm appears in Vazirani's Approximation Algorithms book and is due to
Goemans and Williamson. Time permitting I will also show a hardness result:
there does not exists a PTAS for MAX-SAT assuming P!=NP. This result uses
the PCP theorem. Better bounds are known. a hardness result of 7/8=0.875 and
a 0.833-approximation.