CATS Seminar: Spring 2012
(Capital Area Theory Seminar (CATS))
CATS usually meets on Fridays 1:00pm- 2:00 pm CSIC3118 but some talks may be at a different place and time.
| Date | Time | Location | Speaker | Title |
|---|---|---|---|---|
| Jan 10 | 1-2PM | AVW3258 | Rohit Khandekar | Single Processor Scheduling with Monotone Penalties |
| Feb 3 | 1-2PM | CSIC3118 | (Available) | TBA |
| Feb 10 | 1-2PM | CSIC3118 | Dominique Schroeder | Provable Security and Beyond |
| Feb 17 | 1-2PM | CSIC3118 | David Kempe | TBA |
| Feb 24 | 1-2PM | CSIC3118 | Nicholas Mattei | Empirical Evaluation of Voting Rules with Strictly Ordered Preference Data. |
| Mar 2 | 1-2PM | CSIC3118 | Jeremy Fineman | TBA |
| Mar 9 | 1-2PM | CSIC3118 | Yi-Kai Liu | TBA |
| Mar 16 | 1-2PM | CSIC3118 | Stephen P. Jordan | Quantum Algorithms for Quantum Field Theories |
| Mar 23 | (spring break) | N/A | ||
| Mar 30 | 1-2PM | CSIC3118 | (Available) | TBA |
| Apr 6 | 1-2PM | CSIC3118 | (Available) | TBA |
| Apr 13 | 1-2PM | CSIC3118 | (Available) | TBA |
| Apr 20 | 1-2PM | CSIC3118 | (Available) | TBA |
| Apr 27 | 1-2PM | CSIC3118 | (Available) | TBA |
| May 4 | 1-2PM | CSIC3118 | (Available) | TBA |
| May 11 | 1-2PM | CSIC3118 | (Available) | TBA |
| May 18 | 1-2PM | CSIC3118 | (Available) | TBA |
| May 25 | 1-2PM | CSIC3118 | (Available) | TBA |
For additional information send email to Samir Khuller.
If you want to receive announcements of upcoming talks join the theory-local mailing list.
|
|
Title
Speaker
Affiliation
Abstract:
Abstract Body.
Single Processor Scheduling with Monotone Penalties
Rohit Khandekar
IBM T. J. Watson research center
Abstract:
We will consider single processor preemptive scheduling with
job-dependent setup times. In this model,
a job-dependent setup time is incurred when a job is started for the
.rst time, and each time it is restarted
after preemption. This model is a common generalization of preemptive
scheduling, and actually of non-
preemptive scheduling as well. The objective is to minimize the sum of
any general non-negative, non-
decreasing cost functions of the completion times of the jobs . this
generalizes objectives of minimizing
weighted .ow time, .ow-time squared, tardiness or the number of tardy
jobs among many others.
I will sketch a randomized polynomial time of.ine O(1)-speed
O(1)-approximation algorithm
for this problem. Without speedup, no polynomial time .nite
multiplicative approximation is possible
unless P = NP.
This is a joint work with Kirsten Hildrum, Deepak Rajan and Joel Wolf.
Provable Security and Beyond
Dominique Schroeder
University of Maryland
Abstract:
One of the cornerstones of modern cryptography is that new
constructions of cryptographic schemes should come with a proof of
security showing that the scheme satisfies a given definition of
security, under certain assumptions and in a specific model. While
techniques used to prove security are quite powerful, for some schemes
no security proofs are known. Interestingly, it is sometimes possible
to show the impossibility of proving security (subject to certain
constraints on the proof); this shows that our inability to find such
proofs is not a failure, but rather due to some fundamental
limitations. In the opposite direction, and somewhat surprisingly,
impossibility proofs can sometimes lead to positive results by guiding
cryptographers to new constructions.
I illustrate the above by discussing two recent results of my own. The
first result (Eurocrypt 2010) shows the impossibility of three-round
blind signature schemes based on non-interactive assumptions in the
standard model. This result implies, in particular, limitations on
provable security of the well-known blind signature schemes of Chaum
and Pointcheval-Stern. The second part of my talk discusses how to
bypass this impossibility result and construct a two-round blind
signature scheme based on non-interactive assumptions in the standard
model (Crypto '11).
Empirical Evaluation of Voting Rules with Strictly Ordered Preference Data.
Nicholas Mattei
University of Kentucky
Abstract:
The study of voting systems often takes place in the theoretical domain
due to a lack of large samples of sincere, strictly ordered voting data.We
derive several million elections (more than all the existing studies combined)
from a publicly available data, the Netflix Prize dataset. The Netflix data is
derived from millions of Netflix users, who have an incentive to report sincere
preferences, unlike random survey takers. We evaluate each of these elections
under the Plurality, Borda, k-Approval, and Repeated Alternative Vote (RAV)
voting rules.We examine the Condorcet Efficiency of each of the rules and the
probability of occurrence of Condorcet's Paradox. We compare our votes to
existing theories of domain restriction (e.g., single-peakedness) and
statistical models used to generate election data for testing (e.g., Impartial
Culture). We find a high consensus among the different voting rules; almost no
instances of Condorcet's Paradox; almost no support for restricted preference
profiles, and very little support for many of the statistical models currently
used to generate election data for testing.
Quantum Algorithms for Quantum Field Theories
Stephen P. Jordan
National Institute of Standards and Technology
Abstract:
Quantum field theory reconciles quantum mechanics and special relativity, and plays a central role in many areas of physics.
I will discuss a polynomial-time quantum algorithm for simulating a quantum field theory, which I developed in collaboration with Keith Lee and John Preskill. Such simulations are believed to require exponential time on classical computers.
No prior knowledge of quantum algorithms or quantum field theory will be assumed.