-
11:30-12:20:
Bernhard Haeupler:
How to Gossip
Gossip algorithms have gained attention as a powerful approach for achieving robust and message efficient multicast communication. This talk presents several ideas to improve the efficiency and applicability of these algorithms.
In particular, we provide the first gossip protocol whose efficiency does not rely on expansion properties of the network but which instead performs well on any topology. We also give a novel analysis that shows that a wide variety of natural gossip processes very robustly achieve the same (or even better efficiency) without using any randomization. The existence of such protocols is somewhat surprising because conventional wisdom suggested that both robustness and the efficient information dispersion of gossip protocols stem from their use of randomness.
We also show how combining gossip protocols with network coding can drastically improve the throughput in settings where the amount of data to be multicast is much larger than what can be transmitted at once. While the idea of using network coded gossip is not new analyzing its performance turned out to be very challenging even in the simplest setting. We introduce a novel, simple yet very powerful analysis that provides sharp convergence times.
-
12:20-1:00: Lunch
-
1:00-1:50:
Elette Boyle:
Secure Multi-Party Protocols Under a Modern Lens
Since its inception in the 1980s, secure multi-party computation (MPC) has served as a cornerstone of modern cryptography, enabling mutually distrusting parties to collectively compute on their secret inputs while guaranteeing that malicious parties learn nothing beyond the evaluated function outputs. However, to effectively use MPC today, we need protocols which both scale up and address adversarial settings dictated by current-day computing platforms.
I will address two lines of work toward this goal: hardening MPC protocols to resist a new, powerful class of physical attacks, and designing protocols whose communication requirements scale reasonably to the current regime of massive data. I will focus on recent work in the latter category, in which we devise MPC protocols which achieve communication locality: each party is required to communicate with only a small number of other parties.
-
1:50-2:40:
Eric Price:
Fourier Sampling and Beyond
The Fast Fourier Transform (FFT) is a
fundamental algorithm that computes the Discrete Fourier
Transform of an n-dimensional signal in O(n log n) time. It is
unknown whether the running time can be improved in general.
However, in applications such as image, audio, and video
compression where the output is "sparse" (i.e., k << n
coordinates are "large" and contain most of the energy), it is
possible to estimate the large coordinates in less than O(n
log n) time. We show the first algorithms that achieve this
The sparse Fourier transform problem lies in the broader area
of sparse recovery and compressive sensing. This area
considers the robust recovery of a sparse vector x from
relatively few linear measurements Ax, and has applications in
diverse settings such as streaming algorithms, camera design,
and genetic testing. We discuss multiple extensions to the
sparse recovery framework, including a proof that the number
of measurement can be improved -- in some cases exponentially
-- if the measurements are chosen adaptively.
-
2:40-3:10: Break
-
3:10-4:00:
Morteza
Zadimoghaddam:
Online Allocation Algorithms in Computational Advertising
Over the last few decades, a wide variety of allocation markets emerged from the Internet and introduced interesting algorithmic challenges, e.g., ad auctions, online dating markets, matching skilled workers to jobs, etc. Motivated by applications in online ad allocation, we study the problem of online budgeted allocation problem. This problem consists of a bipartite graph G = (X,Y,E), where the nodes of Y along with their corresponding budgets are known beforehand to the algorithm, and the nodes of X arrive online. When a node of X arrives, its incident edges, and their respective weights are revealed, and the algorithm can match it to a neighbor in Y . The objective is to maximize the weight of the final matching, while respecting the budgets.
The literature on this problem focus on two main settings for the arrival order of online nodes: adversarial, and stochastic arrival orders. Traffic spikes in patterns of online nodes' arrival challenges the stochastic assumption. On the other hand, adversarial setting is too pessimistic to model reality. This motivates us to study simultaneous competitive algorithms for the adversarial and stochastic. In other words, we look for algorithms that are robust to different types of online nodes arrivals, and achieve the best competitive ratio in each case.
When nodes arrive in an adversarial order, the best competitive ratio is known to be 1 - 1/e, and it can be achieved by the Ranking algorithm, and its generalizations (Balance Algorithm). On the other hand, if the nodes arrive through a random permutation, it is possible to achieve a competitive ratio of 1 - epsilon. In this work, for unweighted graphs, under some mild assumptions, we show that a natural greedy algorithm achieves the best competitive ratios in both settings. For weighted graphs, however, we show that this is not possible; we prove that no online algorithm that achieves a competitive ratio of 1 - 1/e for the worst-case inputs may achieve a competitive ratio better than 97.6% for stochastic inputs. In light of this hardness result, we aim to design algorithms with improved competitive ratios in the random arrival model while preserving the competitive ratio of 1 - 1/e in the worst case. To this end, we show an algorithm achieving a competitive ratio of 0.76 for the stochastic arrival model, while having a 1-1/e competitive ratio in the worst case.
-
4:00-4:50:
Yang Cai:
Mechanism Design: a new algorithmic framework
In his seminal paper, Myerson [1981] provides a revenue-optimal auction for a seller who is looking to sell a single item to multiple bidders. Extending this auction to simultaneously selling multiple heterogeneous items has been one of the central problems in Mathematical Economics. We provide such an extension that is also computationally efficient. Our solution proposes a novel framework for mechanism design by reducing mechanism design problems (where one optimizes an objective function on "rational inputs") to algorithm design problems (where one optimizes an objective function on "honest inputs"). Our reduction is generic and provides a framework for many other mechanism design problems.
This is joint work with Costis Daskalakis and Matt Weinberg.
