Speakers
- Lap Chi Lau, University of Waterloo
- Elchanan Mossel, MIT
- Amnon Ta-Shma, Tel Aviv University
- Luca Trevisan, UC Berkeley
Program
| 9:30 - 10:00 | Coffee |
| 10:00 - 11:00 | Lap Chi Lau: Approximating Unique Games in Minor-Closed Graph Families |
| 11:00 - 12:00 | Elchanan Mossel: Reconstruction of Graphical Models: Algorithms, Information Theory and Complexity |
| 12:30 - 2:30 | Lunch |
| 2:30 - 3:30 | Amnon Ta-Shma: An Efficient Reduction from Non-malleable to Two-source Extractors: Achieving Near-logarithmic Min-entropy |
| 3:30 - 4:30 | Luca Trevisan: Know Your Place: Simple Distributed Graph-Partitioning Algorithms |
Information
- Venue
- ERB1009 William M. W. Mong Engineering Building, The Chinese University of Hong Kong
- Registration
- Please email itcsc@cuhk.edu.hk with your first name, last name, email, university and whether you will join the complementary lunch. To reserve car parking for the event, please let us know your car plate number by 13 Dec, 2016
- Contact
- For enquiry, please email us at itcsc@cuhk.edu.hk
Talks
We present approximation algorithms for the Unique Games Problem in minor-closed graph families. As a corollary, this implies an improved approximation algorithm for the min-uncut problem in these graphs. The algorithms are based on low diameter graph decomposition.
The talk will be self-contained. I will begin with an introduction of the Unique Games Conjecture and also low diameter graph decomposition.
Joint work with Vedat Alev.
TBA
The breakthrough result of Chattopadhyay and Zuckerman gives a reduction from the construction of explicit non-malleable extractors to the construction of explicit two-source extractors and bipartite Ramsey graphs. However, even assuming the existence of optimal explicit non-malleable extractors only gives a two-source extractor (or a Ramsey graph) for poly(log n) entropy, rather than the optimal O(log n).
In this paper we modify the construction to solve the above barrier. Using the currently best explicit non-malleable extractors we get an explicit bipartite Ramsey graphs for sets of size 2k, for k=O(log n loglog n). Any further improvement in the construction of non-malleable extractors would immediately yield a corresponding two-source extractor.
Intuitively, Chattopadhyay and Zuckerman use an extractor as a sampler, and we observe that one could use a weaker object — a somewhere-random condenser with a small entropy gap and a very short seed. We also show how to explicitly construct this weaker object using the error reduction technique of Raz et. al., and the constant degree dispersers of Zuckerman that also work against extremely small tests.
This is joint work with Avraham Ben-Aroya and Dean Doron
We study network distributed processes of the following type: each node, independently, picks an initial state according to a certain distribution, then nodes repeatedly exchange information about their states with some or all of their neighbors. At each iteration, each node, based on its state, assigns itself to a cluster.
We show that a synchronous discrete-time algorithm of this sort (in which, at each time step, all nodes communicate their state to all neighbors) converges to the partition found by a centralized spectral partitioning algorithms, and we discuss preliminary results concerning an asynchronous continuous-time version of the algorithm (in which, at Poisson intervals, two adjacent nodes along a random edge exchange information about their states).
(Joint work with Luca Becchetti, Andrea Clementi, Francesco Pasquale, Prasad Raghavendra, and Emanuele Natale)