Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
no edit summary
== Title ==
The Combinatorics of Hidden Diversity
== 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 ==
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.
The Combinatorics of Hidden Diversity
== 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 ==
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.
