Date: 2007-10-16 3:30pm
Room: Wean 5409
Speaker: Michael Kearns (UPenn)
Title: Behavioral Games on Networks
Abstract: We have been conducting behavioral experiments in which human subjects attempt to solve challenging graph-theoretic optimization problems through only local interactions and incentives. The primary goal is to shed light on the relationships between network structure and the behavioral and computational difficulty of different problem types.
To date, we have conducted experiments in which subjects are incentivized to solve problems of graph coloring, consensus, independent set, and an exchange economy game. I will report on thought-provoking findings at both the collective and individual behavioral levels, and contrast them with theories from theoretical computer science, sociology, and economics.
This talk discusses joint work with Stephen Judd, Sid Suri, and Nick Montfort.
October 19, 2007
Elaine Shi
3:00 PM, 5409 Wean Hall
Thesis Proposal
Title: Evaluating Predicates over Encrypted Data
Abstract:
In predicate encryption systems, given a capability (i.e., a partial decryption key) and a ciphertext, one can evaluate one or more predicates on the plaintext encrypted, while all other information about the plaintext remains hidden.
An important goal in predicate encryption is to construct efficient schemes that support expressive query predicates. Previously, researchers have constructed efficient schemes where the predicates are equality tests. In this proposal, we extend the previously known result and construct a new encryption scheme supporting conjunctive queries, where the query predicates are conjunctions of equality tests. A direct extension of this result is a scheme supporting multi-dimensional range queries.
We also propose to add delegation to predicate encryption systems. To demonstrate why delegation may be interesting, imagine that Alice has a capability, and she wishes to delegate to Bob a more restrictive capability allowing him to decrypt a subset of the information Alice can learn about the plaintext encrypted. We formally define delegation in predicate encryption systems, propose a new security definition for delegation. The proposed work is to add delegation to a predicate encryption scheme supporting conjunctive queries.
Thesis Committee:
Adrian Perrig, Chair
Dawn Song
Manuel Blum
Brent Waters, Stanford Research Institute
Query Lower Bounds for Matroids via Group Representations
Nick Harvey, MIT
September 12, 2007, 3:30PM, Wean 7220
Abstract:
Finding an common independent set in two matroids is one of the classical problems of combinatorial optimization, including the well-known bipartite matching problem as a special case. In the early 1970s, algorithms for this problem were discovered that use O(n^3) queries for matroids on n elements. In 1976, Welsh asked the question of whether these algorithms are optimal. In the following thirty years, no non-trivial lower bounds were found.
In this talk, I will present some modest progress on this question. We show that (log_2 3)*n queries are necessary for certain matroids. The arguments are based on communication complexity and representation theory of the symmetric group.
When: Wednesday, October 17, 12:00 p.m.
Where: 1507 Newell-Simon Hall
Who: Michael Dinitz
Title: Compact Routing with Slack
Abstract:
Given a weighted graph G=(V,E), a compact routing scheme is a distributed algorithm for forwarding packets from any source to any destination. The fundamental tradeoff is between the space used at each node and the stretch of the total route, measured by the multiplicative factor between the actual distance traveled and the length of the shortest possible route. We extend the normal definition with a slack parameter epsilon, which allows us to ignore up to epsilon*n2 of the shortest pairwise routes and give stronger guarantees on the remaining ones. We give good epsilon-slack routing schemes in a variety of standard routing models, including the labeled model and the name-independent designer-port model. We also give a lower bound that proves that such schemes do not exist in the name-independent fixed-port model. In the labeled model we also give a gracefully degrading scheme which works simultaneously for all epsilon > 0 and guarantees constant average stretch with polylog space.
Name: Patrick Jalliet
University: MIT, School of Engineering
Date: Friday, October 19, 2007
Time: 1:30 pm to 3:00 pm
Location: Simon Auditorium
Title: Online Optimization for Routing Problems
Abstract:
We consider online routing optimization problems where the objective is to minimize the time needed to visit a set of locations under various constraints:; the problems are online because the set of locations are revealed incrementally over time. We consider two main problems: (2) the online Traveling Salesman Problem (TSP) with precedence and capacity constraints and (2) the online TSP with m salesmen. For both problems we propose online algorithms, each with a competitive ratio of 2; for the m-salesmen problem we show our result is best possible. We also consider polynomial-time online algorithms.
We then consider recourse augmentation, where we give the online servers additional resources to offset the powerful offline adversary advantage; in this way, we address a main criticism of competitive analysis. We consider the cases where the online algorithm has access to faster servers, servers with larger capacities, additional servers and/or advanced information. We derive improved competitive ratios. We also give lower bounds on the competitive ratios under resource augmentation, which in many cases are tight and lead to best-possible results.
Finally, we study online algorithms from an asymptotic point of view. We show that, under general stochastic structures for the problem stat, unknown and unused by the online player, the online algorithms are almost surely asymptotically optimal. Furthermore, we provide computational results that show that the convergence can be very fast.
