Bureaucrats, editor, Administrators
373
edits
Changes
no edit summary
Line 1:
Line 1:
Nicole Immorlica, Microsoft Research +In 1969, economist Thomas Schelling introduced a landmark model of racial segregation in which individuals move out of neighborhoods where their ethnicity constitutes a minority. Simple simulations of Schelling's model suggest that this local behavior can cause global segregation effects. In this talk, we provide a rigorous analysis of Schelling's model on ring networks. Our results show that, in contrast to prior interpretations, the outcome is nearly integrated: the average size of an ethnically-homogenous region is independent of the size of the society and only polynomial in the size of a neighborhood. +Joint work with Christina Brandt, Gautam Kamath, and Robert D. Kleinberg.+
+
+
== Title ==
== Title ==
−The Degree of Segregation in Social Networks
+The Combinatorics of Hidden Diversity
== Speaker ==
== Speaker ==
−David Johnson is Head of the Algorithms and Optimization Department
+at AT&T Labs-Research in Florham Park, NJ, and has been a researcher
+at the Labs (in its many incarnations) since 1973, when he received his
+PhD from MIT. He is perhaps best known as the co-author of COMPUTERS
+AND INTRACTABILITY: A GUIDE TO THE THEORY OF NP-COMPLETENESS, for which
+he and his co-author M. R. Garey won the INFORMS Lanchester Prize.
+His research interests include approximation algorithms for combinatorial
+problems, a subject on which he had several of the first key papers,
+starting with his PhD thesis on the infamous "bin packing" problem.
+In recent years he has become a leader in the experimental analysis of
+algorithms, and has been the creator and lead organizer for the series
+of DIMACS Implementation Challenges, covering topics from Network Flows
+to the Traveling Salesman Problem. He also founded the ACM-SIAM
+Symposium on Discrete Algorithms (SODA), and served as its Steering
+Committee Chair for its first 23 years. He is an ACM Fellow, a SIAM
+Fellow, an AT&T Fellow, and the winner of the 2010 Knuth Prize for
+outstanding contributions to the foundations of computer science.
== Abstract ==
== Abstract ==
−Suppose we are given n buckets with varying integral sizes, and
+wish to fill some fraction alpha of them will balls, with a bucket
+of size k being filled as soon as it receives k balls. Our goal is
+to minimize the number of balls used.
−If we know the sizes of the buckets, this is a trivial problem:
+Just identify the (alpha)n smallest buckets, and fill them.
+But what if we do not know the sizes of the buckets in advance,
+and after each ball placement only find out whether the bucket
+is now full or not?
+This problem models a cryptographic question. Suppose an adversary
+wishes to prevent a multiparty protocol from succeeding. Typically
+with such protocols, the adversary need only corrupt half (or a third)
+of the parties to attain its goal. But suppose each party is protected
+by a sequence of some number of cryptographic walls, each of which
+requires a certain amount of computation to break through. If parties
+have differing numbers of walls, and the adversary does not know how
+many walls a given party has until it breaks through the last one,
+we get our balls-and-buckets problem.
+This cryptographic connection is formalized in a paper I've written
+with Juan Garay, Aggelos Kiayis, and Moti Yung. Here I will concentrate
+on the combinatorial side, giving algorithms for the adversary (bucket
+filler) in the presence various levels of partial information about the
+sizes, and near-matching lower bounds on what is possible, both for
+deterministic and randomized algorithms. I also address the question
+of how a system-designer can best spend his security dollars (in wall
+building) in the hidden diversity setting.