CATS Seminar: Spring 2012  (Capital Area Theory Seminar (CATS))

 

 

 

Schedule

CATS usually meets on Fridays 1:00pm- 2:00 pm  CSIC3118   but some talks may be at a different place and time.

For additional information send email to Samir Khuller.

If you want to receive announcements of upcoming talks join the theory-local mailing list.

CATS Talks from previous semesters

• 2011: Spring | Fall
• 2010: Spring | Fall
• 2009: Spring 
• 2008: Spring | Fall
• 2007 : Spring| Fall
• 2006 : Fall | Spring
• 2005 : Fall | Spring
• 2004 : Fall | Spring
• 2003 : Fall | Spring
• 2002 : Fall | Spring
• 2001 : Fall
• 2000 : Fall | Spring
• 1999 : Fall | Spring
• 1998 : Fall | Spring
• 1997 : Fall | Spring
• 1996 : Summer and Fall | Spring
• 1995 : Fall

Other cats

Combinatorial Algorithms Test Sets Collaborative Agent Technology System Computing: The Australasian Theory Symposium

Abstracts

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.