Capital Area Theory Seminar: Fall 2006
Capital Area Theory Seminar: Fall 2006
| 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 1:00pm-2:00pm CSIC 2120 but some talks may be at a different place and time.
| Date | Time | Location | Speaker | Title |
|---|---|---|---|---|
| Feb 2nd | 1:00 PM | CSIC 2120 | Aravind Srinivasan | Rounding Theorems for Column-Sparse Matrices |
| Feb 9th | 11:00 AM | CSIC 1115 | Nicole Immorlica | Online Advertising Auctions and the Threat of Click Fraud |
| Feb 16th | 1:00 PM | CSIC 2120 | Srinivas Kashyap | Noisy binary search and its applications |
| March 9th | 1:00 PM | CSIC 2120 | Thomas DuBois | skip graphs |
| March 16th | 1:00 PM | CSIC 2120 | Julian Mestre | Adaptive Local Ratio |
| March 29th(thursday) | 11:00 AM | AVW 4185 | Timothy H. McNicholl |
Models of computing over the reals |
| April 13th | 2:00 PM | CISC 2107 | Jessica Chang | Broadcast Scheduling: Algorithms and Complexity |
| April 20th | 2:00 PM | CSIC 2107 | Ed Reingold | Determining Plurality |
| May 31st | 9:30 AM | CSIC 1122 | Jared Saia | Attack-Resistant Algorithms for Massive Networks |
For additional information send email to Samir Khuller.
If you want to receive announcements of upcoming talks join the theory-local mailing list.
 |
ABSTRACT
I will present the rounding
theorems of Beck-Fiala and Karp-Leighton-Rivest-Thompson
(The general area here is called "discrepancy theory", which has played a
fruitful role in computational geometry, MST algorithms etc.)
ABSTRACT
Online advertising is a
booming industry and is developing into a major advertising outlet for millions
of firms. Given the real-time and fast-paced nature of the business, pricing
online advertisements is a difficult task. The major publishers in this market,
namely Google, Yahoo!, and MSN, sell advertisements almost exclusively on a
per-click basis through auctions. This talk will survey the mechanisms most
commonly used in the industry, and discuss some of the underlying design issues.
In particular, we consider the problem of click fraud - a major threat to
pay-per-click advertising. Click fraud happens when an advertiser or service
provider generates clicks on an ad with the sole intent of increasing the
payment of the advertiser. We observe that in auction mechanisms based on
estimating the click-through rates (or probability that an advertisement
receives a click), a fraudulent click causes not only a short-term loss, but
also a long-term gain due to an increase in the estimate of the click-through
rate. We prove that for a particular class of click-through rate learning
algorithms, these two effects cancel, thereby reducing click fraud to impression
fraud.
This is based on joint work with Jain, Mahdian, and Talwar.
Paper by Richard Karp and Robert Kleinberg, appeared in SODA 07.
Abstract:
We study a noisy version of the classic binary
search problem of inserting an element into its proper place within an ordered
sequence by comparing it with el-
ements of the sequence. In the noisy version we can not compare elements
directly. Instead we are given a coin corresponding to each element of the
sequence, such that as one goes through the ordered sequence the probability of
observing heads when tossing the corresponding coin increases. We design online
algorithms which adaptively choose a sequence of experiments, each consisting of
tossing a single coin, with the goal of identifying the highest-numbered coin in
the ordered sequence whose heads probability is less than some specied target
value. Possible applications of such algorithms include investment planning,
sponsored search advertising, admission control in queueing networks, college
admissions, and admitting new members into an organization ranked by ability,
such as a tennis ladder.
Skip graphs are a novel distributed data
structure, based on skip lists, that provide the full functionality of a
balanced tree in a distributed system where
elements are stored in separate nodes that may fall at any time. They are
designed for use in searching peer-to-peer networks, and by providing the
ability to
perform queries based on key ordering, they improve on existing search tools
that provide only hash table functionality. Unlike skip lists or other tree data
structures, skip graphs are highly resilient, tolerating a large fraction of
failed nodes without losing connectivity. In addition, constructing, inserting
new elements
into, searching a skip graph and detecting and repairing errors in the data
structure introduced by node failures can be done using simple and
straightforward
algorithms.
http://www.ic.unicamp.br/
Julian Mestre
Abstract:
Local Ratio and Primal-Dual are two well-studied
and equivalent paradigms for designing exact or approximation algorithms for
combinatorial optimization problems.
At the heart of every Local Ratio algorithm is the update step in which the
weight function is modified by subtracting a certain "model" function w_i.
Guided by this process, a solution S is constructed such that w_i(S) <= r *
w_i(A) for all A and i. Thus, S is r-approximate since the input weight function
can be written as w_1 + ... + w_k.
Typically, these model functions have a very simple structure that remains
"unchanged" throughout the execution of the algorithm. In this talk we will see
that adaptively choosing a model from a richer spectrum of functions can lead to
a better local ratio. Indeed, by turning the search for a good model into an
optimization problem of its own, we get improved approximations for the Data
Migration problem.
Note: Previous knowledge about Local-Ratio or Primal-Dual algorithms
is not necessary to follow this talk
Timothy H. McNicholl
Abstract:
In classical computability theory, all computations
are performed with finite strings or, equivalently, with natural numbers.
However, most scientific computation involves computations with real numbers
which can only be represented by infinite strings. In recent years, much
attention has been paid to the development of models of computing over the reals
for the sake of giving accurate predictions of what can and can not be computed
over the reals by modern digital
computers and related computing devices. We will present two such models: the
model developed by Blum, Cucker, Shub, and Smale (BCSS), and the Type-Two
Effectivity (TTE) model developed by Weihrauch, et. al. If time permits, we
will also discuss some work on developing a theory of complexity within TTE.
Jessica Chang
Abstract:
In the broadcast scheduling problem, we have n
pages of information that are being broadcast over a channel in response to
requests by clients. The key difference with traditional scheduling is that
requests can be overlapped when multiple clients request the same page. Once a
page is broadcast, all outstanding requests for that page are satisfied. We
study this problem with the objective function of minimizing the maximum
response time. This talk will focus on proving
that FIFO is a 2-competitive online algorithm, and we will show that no
(deterministic) algorithm can do better. The NP-completeness for minimizing the
maximum response time will also be presented, which settles the complexity of
this question.
(Joint work with T. Erlebach, R. Gailis and S. Khuller.)
Given a set of n elements, each of which is
colored one of c colors, we must determine an element of the plurality (most
frequently occurring) color by pairwise equal/unequal color comparisons of
elements. We focus on the expected number of color comparisons when the cn
colorings are equally probable. We derive lower bounds for the expected number
of color comparisons: a general lower bound of (c/3) n - O(
Ö n) for c
³ 2 and a stronger
particular bound of (7/6) n - O(Ö
n) for c=3. We analyze an obvious general algorithm, showing that its expected
performance is (c2 + c - 2)/(2c) n - O(c2). We give a
better algorithm for the case c=3 colors whose average complexity on the 3n
equally probable inputs is (7083/5425) n + O(Ö
n).
How can we create a reliable system out of
unreliable components? This question spans several disciplines including
engineering, computer science, economics, political science, and mathematics.
In this talk, we will describe new algorithms for building reliable
peer-to-peer networks out of unreliable peers. In particular, we assume that up
to a constant fraction of the peers in the network have been attacked and are
under the control of an omniscient and computationally unbounded adversary. We
present algorithms for leader election and Byzantine agreement that are provably
reliable under this attack scenario, and
describe a general framework that can be used to design similar algorithms for
other types of problems. Our algorithms are scalable in the sense that for
every peer, all major resource costs (e.g. latency, number of bits sent and
received, number of links to other peers) are polylogarithmic in the number of
peers in the network. Application areas include: collaborative worm and spam detection,
collaborative filtering, auction and mechanism enforcement, reputation
management, voting, web search, network tomography, and distributed data storage
and retrieval. The work makes use of several interesting mathematical tools
including: the probabilistic method; expander and extractor graphs to enable
robust computation; and novel algorithmic techniques to harden against denial of
service attacks. We also describe many areas for future work.
These results are joint with Valerie King (U. Victoria and MSR), Vishal
Sanwalani (UNM and MSR) and Erik Vee (IBM Labs and Yahoo), and describe work
recently published in the Symposium of Discrete Algorithms (SODA) and
Foundations of Computer Science (FOCS).
http://www.cs.umd.edu/areas/Theory/ / Webmaster: Azarakhsh Malekian